第章堆栈与队列.docVIP

第4章 栈和队列 本章讨论栈、队列和它们的应用实例。栈、队列是线性表的特殊情况，即限制存取位置的线性表。将它们的定义和实现放在头文件”stackqueue.h”中。优先级队列将在第6章“树”中再介绍。 § 4.1 栈 堆栈或栈（stack）是一种最常用和最重要的数据结构，它的用途非常广泛，例如，汇编程序中的句法识别和表达式计算就是基于栈实现的。栈还经常使用在函数调用时的参数传递和函数值的返回方面。 § 4.1.1 栈的特征和抽象数据类型 1．栈可定义为只允许在顶端进行插人和删除的线性表。 允许插人和删除的一端叫做栈顶（top )，不允许插人和删除的另一端叫做栈底（bottom）。当栈中没有任何元素时则成为空栈。 设给定栈S = （a 0, a 1,…，a n-1），则称a 0 为栈底，a n-1为栈顶。栈中按a0, a1,…，a n-1的顺序进栈。而退栈  的顺序必须反过来，a n -1先退出，然后a n-2才能退出，最后退出a0。因此，栈又叫做后进先出（LIFO, Last In First Out）的线性表，参看图4.1。 请注意：栈的后进先出是有条件的。其确切的含义是指：同时在栈中的元素，较后压入堆栈者必然会较先弹出堆栈。请看习题： 4-3 铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问： (1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入栈式结构的站台，可能的出栈序列有多少种？ (2)若进站的六辆列车顺序如上所述，那么是否能够得到435612, 325641, 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进栈”或“出栈”的序列）。 435612，不可能，4先出，说明1-4曾同在栈内，1不可能先于2弹出。序列为1进，2进，3进，4进，4出，3出，5进，5出，6进，6出，此时栈顶为2，不可能先弹出1。 325641，可能。序列为1进，2进，3进，3出，2出，4进，5进，5出，6进，6出，4出，1出。 154623，不可能，5先出，说明2-5曾同在栈内，2不可能先于3弹出。序列为1进，1出，2进，3进，4进，5进，5出，4出，6进，6出，此时栈顶为3，不可能先弹出2。 135426，可能。序列为1进，1出，2进，3进，3出，4进，5进，5出，4出，2出，6进，6出。 4-4试证明：若借助栈可由输入序列1, 2, 3,…，n得到一个输出序列P1, P2, …,Pn（它是输入序列的某一种排列），则在输出序列中不可能出现以下情况，即存在ijk，使得Pj Pk Pi（提示：用反证法）。 证明：若存在ijk，使得Pj Pk Pi， 因为Pj Pk Pi，则Pi后于Pj和Pk入栈，而因为ijk，Pi先于Pj和Pk出栈，所以Pj、Pk、Pi，曾同在栈中。且由于Pj Pk ，Pj应先于Pk入栈而被Pk压在下面，之后弹出的次序只能是先k后j即jk，与题设jk矛盾，证毕。 这用通俗的语言可表达为：对于曾同在栈中的元素而言，如果后进栈的元素先出栈了，那么在其之前已先进栈的另两个元素出栈的相对次序只能与其进栈的相对次序相反，而不能相同。 2．栈可以用向量（连续存储）或链表（链式存储）来实现，分别称为向量栈和链表栈。 向量栈和链表栈均应具有压栈、弹出、读栈顶元素、清空栈、判栈空、判栈满等运算。为此，可以先定义一个栈的抽象数据类型：堆栈类。向量栈和链表栈都作为堆栈抽象类的子类。 3．栈的抽象数据类型定义。 在此定义中，所有栈的成员函数都是纯虚函数，因而是一个抽象类或框架类，只能作为父类来派生子类，不能直接生成对象。 //”stackqueue.h” template class Type class stack { //栈的抽象数据类型 public: virtual void push(const Type＆item)=0； //将参数压人到栈的栈顶 virtual Type pop()=0； //弹出栈顶元素的值 virtual Type getTop()=0； //读出栈顶元素的值 virtual void makeEmpty()=0； //清空栈 virtual int isEmpty()=0 const; //判栈空 }; § 4.1.2 向量栈 1．向量栈的类定义 在连续内存方式下，通常采用一维向量作为栈抽象数据类型的存储表示和实现。我们简称在这种方式下实现的栈为向量栈。栈的存储结构封装在类的私有部分，向量成员为elements，该向量的最大允许存放元素个数为elem