chapter4栈和队列

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

1、栈和队列是计算机科学和程序设计中应用非常广范的两种数据结构，主要用于临时性地缓存数据元素（把一些数据保存起来供后面的计算中使用）。栈也常称为堆栈。栈和队列可以方便地用线性表的基本结构实现，因此不少教科书把栈和队列看作是特殊的操作受限的线性表。第四章栈和队列从抽象数据类型的角度看，栈和队列是与线性表完全不同的数据结构，因为它们具有不同的操作集合。栈和队列都提供了元素存入、访问和删除操作，以及几个辅助操作，如创建、判断空等。数据结构课程这两种结构的特点在于访问和删除操作：任何时刻能访问、删裘宗燕除的元素是默认的且唯一确定

2、的。当时保存的其他元素都不能访问、删除。存入和删除操作将改变能访问的元素。栈和队列给元素使用规定了顺序，两者的不同也就在这里。124.1栈及其基本运算4.1栈及其基本运算栈（Stack）是一种容器，可存入数据元素、访问元素、删除4.2栈的实现元素。在这里没有位置的概念。4.3栈的应用*栈保证任何时刻可访问、删除的元素都是前面最后存入栈里的那个元素。因此确定了一种访问顺序。4.4队列基本操作是封闭集合（与表不同），通常包括：4.5队列的实现•创建空栈•判断栈是否为空4.6队列的应用——农夫过河问题*•向栈中插入（或称推

3、入/压入，push）一个元素4.7一些相关结构*•从栈中删除（或称弹出，pop）一个元素•取当前（最新）元素的值（并不删除）34抽象数据类型（代数描述）栈的特性：集合元素和栈：•保证任何时刻访问或删除的元素，一定是当时栈里所有元素运算中最后存入的那个元素（最新元素）•这种性质称为后进先出（LastInFirstOut,LIFO）•栈确定了元素的访问顺序，是一种与“时间”有关的结构进出栈可看作（可实现为）只栈栈在一端插入和删除的表代数满足这组规范的系统法则（无论抽象的或具体的）因此有人把栈称为后进先栈顶Kn-1出（LI

4、FO）表。都是栈（的模型）...进行插入或删除操作的一满足这组规范的程序都k端称为栈顶，另一端称为1是栈的实现（无论采用限制什么技术）栈底。见图。栈底k0图4.1栈5614.2.1顺序表示4.2　栈的实现顺序表示的栈数据结构的类型定义：¾4.2.1顺序表示#defineMAXNUM100/*栈的最大容量*/采用类似线性表的结构实现栈typedefintDataType;/*栈元素的数据类型*/typedeftypedefstructSeqStack{/*顺序栈类型定义*/¾4.2.2链接表示intt;/*栈顶*/Da

5、taTypes[MAXNUM];采用类似链接表的结构实现栈}SeqStack,*PSeqStack;PSeqStackpsstack;/*指向顺序栈的指针*/完全可以采用动态顺序表的方式（技术）实现栈，创建时确定初始大小，必要时进行扩充。78顺序表示的栈基本运算的实现设st是个栈，现在计划在st.s里保存数据元素，用st.t记录元素的有关信息，支持栈的各种操作。问题：ò算法4.1创建空栈怎样保证栈的各操作形成一个有机整体，共同实现了一种良好PSeqStackcreateEmptyStack_seq(void)结构的栈

6、？因为这些操作都是独立的函数，互不依赖，执行中ò算法4.2判断栈是否为空栈可以按任何顺序调用。intisEmptyStack_seq(PSeqStackpsstack)需要确定一套所有操作都必须遵守的行为准则。ò算法4.3进栈（压入）实现一种数据结构时，相关操作都必须遵守的一套准则称为这voidpush_seq(PSeqStackpsstack,DataTypex)种数据结构数据不变式（DataInvariant）：ò算法4.4出栈（弹出）•创建操作建立的结构应满足不变式（合法的初始状态）voidpop_seq(PS

7、eqStackpsstack)•其他操作都保证：只要操作前结构处于合法状态（满足不变ò算法4.5取栈顶元素式），操作结束时结构仍将处于合法状态DataTypetop_seq(PSeqStackpsstack)•这样，无论执行多少次操作，顺序如何，数据结构总处于合法的状态（可以用归纳法证明）910typedefstructSeqStack{/*顺序栈类型定义*//*创建一个空栈*/intt;DataTypes[MAXNUM];PSeqStackcreateEmptyStack_seq(void){}SeqStack,*

8、PSeqStack;PSeqStackpsstack=(PSeqStack)malloc(sizeof(SeqStack));对栈的顺序实现，我们确定如下不变式：if(psstack==NULL)•栈中所有元素在数组s下标较小的一端（低端）连续存放，printf("Outofspace!!");按进栈顺序排列，最新元素的位置最高（下标最大）