资源描述：
《数据构造-桟与队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列栈和队列是限定插入和删除只能在表的“端点”进行的线性表。栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的类型定义ADTStack{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。
4、基本操作：}ADTStackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度
5、。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……#defineMAX100Typedefstruct{SElemTypeitem[MAX];//栈元素存储空间inttop;//栈顶指针}SqStack；栈的数组存储表示—顺序栈top(栈空)01234567
6、89MAX-1elements栈顶指针top,指向实际栈顶后的空位置，初值为top=basetop进栈Atop出栈栈满BCDEFtop=base,栈空，此时出栈，则下溢（underflow)top-base>=stacksize,栈满，此时入栈，需重新分配空间，如空间分配失败则上溢（overflow)toptoptoptoptoptoptoptoptoptoptop栈空base=0123450栈空top=0123450base123450ABCDEFbaseTypedefstruct{SElemType*base;//栈元素数组的首地址SElemType*top;//栈顶指针intstac
7、ksize;//栈最大容量}SqStack；栈的数组存储表示—顺序栈top(栈空)0123456789stacksize-1elements＃defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10;top空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈ctopc退栈b退栈abaa退栈空栈topabdd退栈ctopabctoptopStatusInitStack（SqStack&S)//构造空栈S{S.base=(SElemtype*)malloc(STACK_INIT_SIZE*sizeof(SE
8、lemType));if(!S.base)exit(OVERFLOW);//存储失败S=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusGetTop(SqStack&S，SElemType&e)//若栈不为空,则用e返回S的栈顶元素并返回OK;否则返回ERROR{if(S==S.base)returnERROR;e=*(S-1);returnOK;}//GetTopStatusPush(SqStack&S，SElemTypee)//插入元素e为新的栈顶元素{if(S-S.base>＝S.stacksize){//栈
9、满，追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S=S.base+S.stacksize;S.stacksize＋＝STACKINCREMENT;}//endif*S++=e;returnOK;}//PushStatusPo
