【精品数据结构】栈与队列.ppt

《【精品数据结构】栈与队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第3章栈与队列目录1.栈2.栈的应用举例3.栈与递归4.队列5.应用实例3.1栈3.1.1栈的定义及其运算栈（Stack）是限定插入和删除运算只能在表尾进行的线性表。通常称允许插入、删除的这一端为栈顶，另一端称为栈底。当表中没有元素时称为空栈。其中数据元素的个数n定义为表的长度。图3.1是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。图3.1所示的栈中，元素是以a1，a2，…，an的顺序进栈，而出栈的次序却是an，an-1，…，a1。也就

2、是说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（LastInFirstOut）的线性表，简称为LIFO表。ADTStack{TypedefstructStackS;InitStack(S,maxSize);说明：构造空栈S，即栈的初始化StackSize(S);说明：求栈中元素的数目isEmpty(S);说明：判栈S是否为空栈isFull(S);说明：判栈S是否已“满”栈的ADT声明如下：GetTop(S,e);说明：取栈顶元素Push(S,e);说明：值为e的数据元素进栈（插入、压栈）

3、Pop(S);说明：栈顶元素出栈（删除、退栈）};栈的顺序存储结构称为顺序栈，是用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。3.1.2栈的顺序存储结构因为栈底位置是固定不变的，栈顶位置是随着进栈和退栈操作而变化的，故需用一个变量top来指示当前栈顶位置，通常称top为栈顶指针，参看图3.2。Typedefstruct{int*elem;//elem是数据元素数组inttop;//栈顶指针intmaxSize;//栈容量}sqStack;我们先以整数元素为例，给出顺序栈的基本算法，在下一节，将

4、给出顺序栈的模板类接口定义以及基本运算的实现代码和应用实例。voidInitStack(S,maxSize)//栈初始化{S.top=-1;S.elem=newint[maxSize];}boolisEmpty(S)//判栈空否？{returnS.top==-1;}boolisFull(S)//判栈满否？{returntop==S.maxSize-1;}boolPush(sqStackS,inte)//值为e的数据元素进栈(插入、压栈){if(isFull(S))//栈满（溢出）无法进栈,返回false

5、{cout<<"ERROR:overflow!!";returnfalse;}S.elem[++S.top]=e;returntrue;//栈顶指针增1元素进栈,返回true}boolPop(sqStackS)//栈顶元素出栈(删除){if(isEmpty(S))//栈空无法删除,返回false{cout<<“ERROR:underflow!!”;returnfalse;}S.top--;returntrue;//元素出栈}boolGetTop(sqStackS,int&e)//取栈S的栈顶元/

6、/素{if(isEmpty(S))//栈空（下溢）{cout<<“ERROR:underflow!!”;returnfalse;}e=S.elem[S.top];returntrue;//元素存e,栈顶指针不变(元素没出栈)}栈的使用非常广泛，常常会出现在一个程序中需要同时使用多个栈的情形。为了不因栈上溢而产生错误中断，要给每个栈预分较大空间，但各个栈实际所用最大空间很难估计。而且各个栈的实际容量在使用期间是变化的，往往会出现某个栈发生上溢，而另一个栈还是空的。试设想，若令多个栈共享空间，则将提高空

7、间的使用效率，并减少发生栈上溢的可能性。假设在程序中需设两个栈，并共享一维数组空间v[m]。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图3.3所示），仅当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺，使得每个栈实际可利用的最大空间大于m/2。显然，两个栈顶的初值分别为-1和m。栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。3.1.3栈的链式存储结构由于只能在链表头部进行操作，故链栈没有必要象单

8、链表那样附加上头结点。栈顶指针就是链表的头指针，如图3.4所示，链栈就是无头结点的单链表（头指针改称栈顶指针），因此不再重新讨论。3.2栈的应用举例栈的应用非常广泛，只要问题满足LIFO原则，均可使用栈做数据结构。//顺序栈的模板类接口定义以及基本运算的实现代码templateclasssqStack{protected:int*elem;//指向存放数据元素的数组指针inttop;//栈顶指针intmaxSize;//栈容