第三章 栈和队列内容概述从数据结构角度来看，栈和队列是两种特殊的线性表，其特殊性体现在它们的基本操作是线性表操作的子集，因此它们是限定性的数据结构。从抽象数据类型角度来看，它们是不同于线性表的两类重要的抽象数据类型。由于栈和队列在实际应用中的广泛性和其操作的特殊性，本章从栈和队列的抽象数据类型定义、栈和队列的顺序表示与实现、栈和队列的链式表示与实现、栈和队列的应用等几个方面进行专门讨论。重点与难点重点为栈和队列的运算，循环队列。难点为栈与递归的关系，栈与队列的应用。思考1栈是具有什么特性的线性表？2队列是具有什么特性的线性表？3分析栈与递归的关系。4若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1,p2,p3,pn，若p1=n，则pi=?5设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？6为什么要循环队列？在循环队列中队列空、满的评定标准是什么？7利用两个栈模拟一个队列的入队、出队、判断队空等运算。第一节栈栈是一种具有“后进先出”特性的线性表。这种特性对其操作有何影响呢？其存储结构相对于一般线性表又会有哪些变化？本节将从栈的定义、抽象类型定义、栈的顺序与链式存储结构等方面入手解答上述问题。1、栈的定义1、栈的定义栈（Stack）又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问只能在某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈顶的第一个元素被称为栈顶元素。不含数据元素的空表称为空栈。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。堆栈的性质决定它的数据是按“先进后出”的顺序被访问，即最先存储的元素最后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为“LIFO”（Last_In,First_Out）。栈的模型在日常生活中是普遍存在的，如铁路列车调度系统等，在计算机科学中，栈是一种非常有用的数据结构。实际上，TurboC在将参数传递给函数时，就使用堆栈。我们应该注意到：栈是一种动态的数据结构，也就是说，随着对栈进行插入和删除等不同的操作，其结点个数、内容等将会不断发生变化。假设栈S=(a1,a2,an)，则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,an的次序进栈，如图3.1所示。2、栈的抽象类型定义2、栈的抽象类型定义在栈的抽象数据类型定义中，用Stack标识符来表示栈对象类型，操作部分应包括初始化、元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。下面给出栈的抽象数据类型的具体定义。ADTStack数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R=|ai-1,aiD,i=2,n约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。StackTraverse(S，visit()初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ADTStack3、顺序栈的数据类型描述3、顺序栈的数据类型描述栈的顺序存储结构，即顺序栈，和线性表的顺序存储结构类似，是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时通过指针top指示栈顶元素在顺序栈中的位置。由于很难估计栈在使用过程中所需要的最大空间的大小，所以通常利用C语言中动态分配的一组连续的存储单元作为顺序栈所需要的存储空间。首先定义一个指针表示存储空间的基地址，且定义一个指针指示栈顶元素的位置，此外还需要定义一个整型变量指示顺序栈当前分配的存储空间大小，即当前顺序栈的最大容量。在应用过程中，当栈的空间不够用而需要继续扩大分配其空间时，通过定义一个整型变量表示栈的动态分配增量。顺序栈所需要的具体数据类型描述如下：#defineMAXLEN100#defineSTACK_INCREASE10/顺序栈存储空间的动态分配增量typedefstructElemType*base;/栈的存储空间的基地址，即栈底指针ElemType*top;/栈顶指针intmaxsize;/栈当前分配的存储容量SqStack;其中，maxsize指示栈当前可使用的最大容量；base为栈底指针，在顺序栈中，它始终指向栈底的位置，若base=NULL，则表明栈结构不存在；top为栈顶指针，起初值为栈底指针值，即top=base，这也可作为栈空的标记。栈插入新元素时，将新元素插入到栈顶指针所指向的位置，同时指针top增1，删除栈顶元素时，指针top减1。因此，如图3.2所示，栈顶指针始终指向栈顶元素的下一个位置。4、顺序栈的操作4、顺序栈的操作（顺序栈的生成算法、顺序栈的入栈算法、顺序栈的出栈算法、顺序栈求栈顶元素算法、顺序栈的遍历算法）生成栈S顺序栈的生成算法主要是为其准备所需要的存储空间（这可通过malloc函数动态申请空间来实现），同时为参数S的成员S.base、S.top、S.maxsize赋以相应的值。StatusInitStack(SqStack&S)/构造一个空栈SS.base=(ElemType*)malloc(MAXLEN*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;/栈顶指针也指向栈底，意味着栈为空S.maxsize=MAXLEN;returnOK;/InitStack算法3-1顺序栈的生成算法元素e进栈，即插入到栈顶插入栈顶元素前首先检查是否栈满（判断S.top-S.base=S.maxsize是否成立），如果栈满，动态追加存储空间。插入栈顶元素时，在栈顶指针top指示的位置插入元素e，即*S.top=e，然后top加1。本算法的时间复杂度为O(1)。StatusPush(SqStack&S,ElemTypee)/插入元素e为新的栈顶元素if(S.top-S.base=S.maxsize)/栈满，追加存储空间newbase=(ElemType*)realloc(S.base,(S.maxsize+STACK_INCREASE)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败S.base=newbase;S.top=S.base+S.maxsize;/确定新栈的栈顶指针的位置S.maxsize+=STACK_INCREASE;/栈的最大容量增加*S.top+=e;/插入栈顶元素，且栈顶指针增加returnOK;/Push算法3-2顺序栈的入栈算法删除栈顶元素，并返回删除元素的值删除栈顶元素时，首先检查栈是否为空，如果为空，则返回错误。若栈不为空，则栈顶指针top减1，返回此时top指向的元素的值。本算法的时间复杂度为O(1)。StatusPop(SqStack&S,ElemType&e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERRORif(S.top=S.base)returnERROR;e=*-S.top;/e返回栈顶元素值，-S.top表示删除栈顶元素returnOK;/Pop算法3-3顺序栈的出栈算法返回栈顶元素的值与删除栈顶元素算法中的返回栈顶元素类似，返回(top1)指向的元素即为栈顶元素的值。本算法的时间复杂度为O(1)。StatusGetTop(SqStackS,ElemType&e)/若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERRORif(S.top=S.base)returnERROR;e=*(S.top-1);/e返回栈顶元素值returnOK;/GetTop算法3-4顺序栈求栈顶元素算法栈的遍历遍历栈S时，首先检查栈是否为空，如果为空，则返回错误。若栈不为空，使p指向栈顶，即p=S.top，利用循环操作，p减1后，对p所指向的元素使用visit函数访问，循环的条件为pS.base，即直到遍历完栈底元素为止。该算法的主要操作和影响算法效率的步骤为循环遍历栈的元素，频数和栈的元素个数相同，所以本算法的时间复杂度为O(n)。StatusStackTraverse(SqStackS,Status(*visit)(ElemType)/若栈不空，则使用visit函数遍历栈的元素并返回OK，否则返回ERRORif(S.top=S.base)returnERROR;p=S.top;/p指向栈顶while(pS.base)visit(*-p);/通过循环对栈的元素遍历returnOK;/StackTraverse算法3-5顺序栈的遍历算法从上述若干对栈操作的实现算法可以看出，由于对栈操作的特殊限制（LIFO），我们主要通过栈顶指针即可完成相应操作，这大大简化了我们考虑问题的思路。现实当中有许多问题可归结为这类操作，实际上，凡是符合LIFO特性的数据操作，我们都应当充分利用栈的优点来实现其简便的操作，从这个角度来看，栈是十分有用的。5、链栈的数据类型描述5、链栈的数据类型描述栈的链式存储结构，即链栈，与线性表的链式存储结构类似，是通过由结点构成的单链表实现的，但每个结点的指针指向其前驱结点（在其之前进栈的结点）。此时，表头指针称为栈顶指针，其指向的结点即为栈顶结点。所需要的具体数据类型描述如下：typedefstructSNodeElemTypedata;structSNode*prior;/prior将指向其前一次入栈的元素SNode,*SLink;当栈插入新元素时，是把新元素插入到栈顶，即把新元素结点的指针指向原来栈