资源描述：
《数据结构课件-栈和队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、3.1栈3.1.1抽象数据类型栈的定义 3.1.2栈的表示与实现3.2栈的应用举例3.2.1数制转换 3.2.4迷宫求解 3.2.5表达式求值*3.3栈和递归的实现3.4队列3.4.1抽象数据类型队列的定义 3.4.2链队列--队列的链式表示与实现 3.4.3循环队列--队列的顺序表示与实现第三章栈和队列栈（stack）:先进后出(FILO）的线性表。或后进先出（LIFO）的线性表。或仅在表尾进行插入和删除操作的线性表。栈顶（top）:线性表的表尾端，即可操作端。栈底（bottom）:线性表的表头。3.1栈3.1.1抽象
2、数据类型栈的定义栈底栈顶......a1a2a3an-1an入栈(push)出栈(pop)栈的抽象数据类型ADTStack{数据对象：D={ai
3、ai属于Elemset,(i=1,2,…,n,n≥0)}数据关系：R1={＜ai-1,ai＞
4、ai-1,ai属于D,(i=2,3,…,n)}约定an为栈顶,a1为栈底。基本操作：InitStack(&S);DestroyStack(&S);ClearStack(&S);StackEmpty(S);StackLength(S);GetTop(S,&e);Push(&S,e);Po
5、p(&S,&e);StackTraverse(S,visit())}ADTStack栈的基本操作(之一)InitStack(&S)操作结果:构造一个空的栈S。DestroyStack(&S)初始条件:栈S已经存在。操作结果:销毁栈S。ClearStack(&S)初始条件:栈S已经存在。操作结果:将栈S重置为空栈。栈的基本操作(之二)StackEmpty(S)初始条件:栈S已经存在。操作结果:若栈S为空栈，则返回TURE;否则返回FALSE。StackLength(S)初始条件:栈S已经存在。操作结果:返回栈S中的数据元素
6、个数。GetTop(S,&e)初始条件:栈S已经存在且非空。操作结果:用e返回栈S中栈顶元素的值。栈的基本操作(之三)Push(&S,e)初始条件:栈S已经存在。操作结果:插入元素e为新的栈顶元素。Pop(&S,&e)初始条件:栈S已经存在且非空。操作结果:删除S的栈顶元素并用e返回其值。StackTraverse(S,visit())初始条件:栈S已经存在且非空。操作结果:从栈底到栈顶依次对S的每个元素调用函数visit()。一旦visit()失败，则操作失败。3.1.2栈的顺序表示与实现--- (顺序栈)typede
7、fstruct{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineOVERFLOW-1#defineERROR0顺序栈示意图*base*topstacksize......a1...aian*base*topstacksize初始空
8、栈*top=*base;stacksize=STACK_INIT_SIZE顺序栈顺序栈的操作实现举例InitStack/*构造一个空的栈S*/StatusInitStack(SqStack*s){s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s->base)return(OVERFLOW);s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}/*InitStack*/顺序栈的操作实
9、现(GetTop)栈S非空,则用e返回栈S中栈顶元素的值， 并返回OK,则返回ERROR。StatusGetTop(SqStacks,SElemType*e){if(s.top==s.base)returnERROR;*e=*(s.top-1);returnOK;}/*GetTop*/*base*topstacksize......a1...aianse*e=*(s.top-1);顺序栈的操作实现（Push）插入元素e为新的栈顶元素。StatusPush(SqStack*s,SElemTypee){if(s->top–s
10、->base>=s->stacksize)/*栈满，追加存储空间*/{l_temp=(SElemType*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!l_temp)return(OVERFLOW);s->base=l_te
