张乃孝全套配套课件算法与数据结构 第4章 栈与队列.ppt

《张乃孝全套配套课件算法与数据结构 第4章 栈与队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、stInFirstOut表，简称LIFO表）或下推表，如图所示4.1.2抽象数据类型ADTStackisoperationsStackcreateEmptyStack(void)创建一个空栈。intisEmptyStack(Stackst)判断栈st是否为空栈。voidpush(Stackst,DataTypex)往栈st的栈顶插入一个值为x的元素。voidpop(Stackst)从栈st的栈顶删除一个元素。DataTypetop(Stackst)求栈顶元素的值。endADTStack4.2栈的

3、实现4.2.1顺序表示用顺序的方式表示栈时，栈的类型可定义如下：structSeqStack{/*顺序栈类型定义*/intMAXNUM;/*栈中最大元素个数*/intt;/*t

4、出，通常称为上溢（Overflow）；而对空栈进行出栈运算时也会产生溢出，通常称为下溢（Underflow）。基本运算的实现1.创建一个空栈PSeqStackcreateEmptyStack_seq(intm)具体实现与算法2.1类似，需要为栈结构申请空间，不同之处是将栈顶变量赋值为-1。请自己给出。2.判断栈是否为空栈intisEmptyStack_seq(PSeqStackpastack)当pastack所指的栈为空栈时，则返回1，否则返回0。3.进栈运算voidpush_seq(PSeqS

5、tackpastack,DataTypex)往pastack所指的栈中插入（或称推入）一个值为ｘ的元素。当栈不满时，先修改栈顶变量，将其值加1，然后把元素x放入栈顶变量所指的位置中。程序实现4.出栈运算voidpop_seq(PSeqStackpastack)从pastack所指的栈中删除（或称弹出）一个元素。 当栈不空时，通过将栈顶变量减1达到元素删除的目的。程序实现5.取栈顶元素运算DataTypetop_seq(PSeqStackpastack)当pastack所指的栈不为空栈时，将栈

6、顶元素取出，而栈本身未发生任何变化。程序实现4.2.2链接表示栈也可以采用链接方式表示，在链接栈中，每个结点的结构可如下定义：structNode;/*单链表结点*/typedefstructNode*PNode;/*指向结点的指针类型*/structNode{/*单链表结点定义*/DataTypeinfo;PNodelink;};为了强调栈顶是栈的一个属性，这里对栈增加了一层封装（后面将会看到：经过这样封装使得栈与队列的链表表示在形式上更加一致），引入LinkStack结构的定义。struct

7、LinkStack/*链接栈类型定义*/{PNodetop;/*指向栈顶结点*/};typedefstructLinkStack*PLinkStack;/*链接栈类型的指针类型*/假设plstack是PLinkStack类型的变量，则plstack->top就是栈顶指针，plstack->top->info是栈顶元素，运算的实现1.创建空链接栈PLinkStackcreateEmptyStack_link(void)创建一空链接栈，需要申请链接栈结构(structLinkStack)空间，将其中

8、top置为NULL,返回该结构的地址。程序实现2.判断栈是否为空栈intisEmptyStack_link(PLinkStackplstack)判断plstack所指的栈是否为空栈，当plstack所指的栈为空栈时，则返回1，否则返回0。程序实现3.进栈运算voidpush_link(PLinkStackplstack,DataTypex)往plstack所指的栈中插入（或称压入）一个值为x的元素。首先申请结点空间，然后通过指针修改，将结点插在栈顶。程序实现4.出栈运算voidpop_link(