第4章 栈与队列

《第4章 栈与队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章栈与队列对栈和队列上的插入、删除操作是受某种限制的。因此，栈和队列也称作操作受限的表，或者限制存取点的表。本章讨论栈和队列的概念、抽象数据类型、表示方法和实现算法，并给出一些应用的例子。4.1栈及其抽象数据类型4.1.1基本概念栈是一种特殊的线性表，它所有的插入和删除都限制在表的同一端进行。表中允许进行插入、删除操作的一端叫做栈的顶。表的另一端则叫做栈的底。当栈中没有元素时，称之为空栈。栈的插入运算通常称为进栈或入栈，栈的删除运算通常称为退栈或出栈。栈又称为后进先出表（LastInFirstOut表，简称LIFO表）或下推表，如

2、图所示4.1.2抽象数据类型ADTStackisoperationsStackcreateEmptyStack(void)创建一个空栈。intisEmptyStack(Stackst)判断栈st是否为空栈。voidpush(Stackst,DataTypex)往栈st的栈顶插入一个值为x的元素。voidpop(Stackst)从栈st的栈顶删除一个元素。DataTypetop(Stackst)求栈顶元素的值。endADTStack4.2栈的实现4.2.1顺序表示用顺序的方式表示栈时，栈的类型可定义如下：structSeqStack{i

3、ntMAXNUM;/*栈中最大元素个数*/intt;/*t

4、qStackcreateEmptyStack_seq(intm)具体实现与算法2.1类似，需要为栈结构申请内存空间，然后给MAXNUM和t赋初值，不同之处是将栈顶变量t赋值为-1。请同学们自己写出程序代码。2.判断栈是否为空栈intisEmptyStack_seq(PSeqStackpastack)当pastack所指的栈为空栈时，则返回1，否则返回0。提示：return(pastack->t==-1)3.进栈运算voidpush_seq(PSeqStackpastack,DataTypex)向pastack所指的栈中插入（或称推入）

5、一个值为ｘ的元素。当栈不满时，先修改栈顶位置变量，将其值加1，然后把元素x放入栈顶变量所指的位置中。程序实现4.出栈运算voidpop_seq(PSeqStackpastack)从pastack所指的栈中删除（或称弹出）一个元素。 当栈不空时，将栈顶变量减1，即可达到元素删除的目的。程序实现5.取栈顶元素运算DataTypetop_seq(PSeqStackpastack)当pastack所指的栈不为空栈时，将栈顶元素取出。提示：栈顶元素就是pastack->s[pastack->t]程序实现4.2.2链接表示在链接表示的栈中，每

6、个结点的结构可如下定义：structNode;/*单链表结点*/typedefstructNode*PNode;/*指向结点的指针类型*/structNode{/*单链表结点定义*/DataTypeinfo;PNodelink;};栈类型的定义：栈顶是栈的一个重要属性，因此，对栈类型的定义增加了一层封装引入LinkStack结构的定义。structLinkStack/*链接栈类型定义*/{PNodetop;/*指向栈顶结点*/};typedefstructLinkStack*PLinkStack;/*链接栈类型的指针类型*/有关表示：

7、设plstack是PLinkStack类型的变量，则：栈顶指针的表示为：plstack->top。栈顶元素是：plstack->top->info，运算的实现1.创建空链接栈PLinkStackcreateEmptyStack_link(void)创建一空链接栈，需要申请链接栈结构(structLinkStack)空间，将其中top置为NULL,返回该结构的地址。程序实现2.判断栈是否为空栈intisEmptyStack_link(PLinkStackplstack)判断plstack所指的栈是否为空栈，当plstack所指的栈为空栈

8、时，则返回1，否则返回0。提示：栈顶指针为：plstack->top程序实现3.进栈运算voidpush_link(PLinkStackplstack,DataTypex)往plstack所指的栈中插入（或称压入）一个值