资源描述：
《CH3栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i,&e)Delete(S,n,&e)Delete(Q,1,&e)1≤i≤n栈和队列是两种常用的数据类型3.1栈的类型定义3.2栈的应用举例3.3栈类型的实现3.4队列的类型定义3.5队列类型的实现一、栈的概念栈（stack）是插入和删除操作限定在表尾进行的线性表。栈的逻辑表示为：S=（a1,a2,…,an）表尾元素an称为栈顶(top)
2、表头元素a1称为栈底(bottom)不含元素的空表称为空栈栈的概念栈是限定在表的同一端进行插入或删除操作的线性表。进行插入或删除操作的一端称为栈顶，另一端称为栈底。栈的运算特性是后进先出(LastInFirstOut--LIFO)或先进后出(FirstInLastOut--FILO)k0k1...Kn-1栈顶栈底进栈出栈栈3.1栈的类型定义ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a
5、1端为栈底。基本操作：}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。StackLe
6、ngth(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。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……3.2栈的表示和实现顺序栈链栈//-----栈的顺序存储表示-----#
7、defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。顺序栈示意图*base*topstacksize......a1...aian*base*topstacksize初始空栈*top=*base;stacksize=STACK_INIT_SIZE顺序栈StatusInitStack(SqStack
8、&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}顺序栈的操作实现(GetTop)栈S非空,则用e返回栈S中栈顶元素的值， 并返回OK,则返回ERROR。StatusGetTop(SqStacks,SElemType&e){if(s.top==s.base)return
9、ERROR;e=*(s.top-1);returnOK;}/*GetTop*/*base*topstacksize......a1...aianse*e=*(s.top-1);StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;//--S.top;e=*S.top;returnOK;}*base*topstacksize......a1...aians
10、ee=*(--s->top);StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacks
