《内蒙古大学《算法与数据结构》讲义05堆栈》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义05堆栈（28页珍藏版）》请在金锄头文库上搜索。
1、下载第5章堆栈堆栈和队列可能是使用频率最高的数据结构，二者都来自于第3章中的线性表数据结构（经过某种限制以后） 。本章将研究堆栈，下一章研究队列。堆栈数据结构是通过对线性表的插入和删除操作进行限制而得到的（插入和删除操作都必须在表的同一端完成） ，因此，堆栈是一个后进先出（last-in-first-out, LIFO）的数据结构。由于堆栈是一种特殊的线性表，因此可以很自然地从相应的线性表类中派生出堆栈类。我们可以从程序3 - 1的L i n e a r L i s t类派生出基于公式描述的堆栈类，也可以从程序 3 - 8的C h a i n类派生出基于链表结构的堆栈类。通过类的派生，可以大大
2、简化程序设计的任务，但同时代码的执行效率有明显损失。由于堆栈是一个很基本的数据结构，许多程序都要用到堆栈，本章中也直接给出了基于公式描述和基于链表结构的堆栈类（而不是从其他类派生而来） 。这两种类与对应的派生类相比，在执行效率上将有很大提高。本章还给出六个使用堆栈的应用程序。第一个应用是一个用来匹配表达式中左、右括号的简单程序；第二个应用是一个经典的汉诺塔问题求解程序。汉诺塔问题要求把一个塔上的所有碟子按照一定的规则搬到另一个塔上，每次只能搬动一个碟子，其间可以借助于第 3个塔的帮助。在汉诺塔问题的求解过程中，每个塔都被视为一个堆栈；第三个应用使用堆栈来解决火车车厢重排问题，其目标是把火车车厢
3、按所希望的次序重新排列；第四个应用是关于电子布线的问题，在这个应用中，用堆栈来确定一个电路是否可以成功布线；第五个应用用于解决 3 . 8 . 3节所介绍的离线等价类问题。采用堆栈可以帮助我们在线性时间内确定等价类；最后一个应用用来解决经典的迷宫问题，即寻找一条从入口到出口的迷宫路径。应该仔细地研究这个应用，因为它体现了许多软件工程的原理和思想。本章中所用到的C + +语言的新的特性是派生类和继承。5.1 抽象数据类型定义堆栈 堆栈（s t a c k）是一个线性表，其插入（也称为添加）和删除操作都在表的同一端进行。其中一端被称为栈顶（t o p） ，另一端被称为栈底（b o t t o m）
4、 。图5-1a 给出了一个四元素的堆栈。假定希望在5-1a 的堆栈中添加一个元素E，这个元素将被放到元素D的顶部，所得到的结果如图5-1b 所示。如果想从5-1b 的堆栈中删除一个元素，那么元素E将被删除，删除E之后又将得到5-1a 的结果。如果对5-1b 的堆栈连续执行三次删除操作，则将得到图5-1c 所示的堆栈。E t o pD t o pDCCBBBt o pAb o t t o mAb o t t o mAb o t t o ma )b )c )图5-1 堆栈结构1 6 2第二部分数 据 结 构下载从上面的讨论中可以看出，堆栈是一个后进先出表。这种类型的表在计算过程中将频繁使用。A D
5、 T堆栈的描述见ADT 5-1。ADT5-1 堆栈的抽象数据类型描述抽象数据类型S t a c k实例元素线性表，栈底，栈顶操作C re a t e( )：创建一个空的堆栈I s E m p t y( )：如果堆栈为空，则返回t r u e，否则返回f a l s eI s F u l l( )：如果堆栈满，则返回t r u e，否则返回f a l s eTo p( )：返回栈顶元素A d d(x)：向堆栈中添加元素xD e l e t e(x)：删除栈顶元素，并将它传递给x5.2 派生类和继承我们经常会处理这样一类新的数据对象，它是某种更通用的数据对象的特殊版本或限制版本。例如，本章中的堆栈
6、数据对象就是更通用的线性表对象的限制版本。堆栈数据对象的实例也是线性表数据对象的实例，而且，所有的堆栈操作都可以利用线性表操作来实现。例如，如果把表的左端定义为栈底，右端定义为栈顶，那么堆栈的添加操作等价于在表的右端进行插入操作，删除操作等价于在表的右端进行删除操作。根据上述观察，我们期望如果能够明确地把堆栈表示成特殊的线性表，那么可以简化 C + +堆栈类的实现，而且，可以参照线性表的操作来定义堆栈操作。若类B是另一个类A的限制版本，那么可以从A派生出B。我们称A为基类，B为派生类。从类A派生出的类B继承了基类A的所有成员共享成员、保护成员和私有成员。类型为 B的每个对象都与A所有的数据成员
7、和函数相关联。类B可以采用如下三种基本方式之一来继承类A的成员：共享成员、保护成员和私有成员。比如，对于共享成员方式，可以采用如下语法形式：class B: public A一个类可以从多个类派生而来。若类 B从A和C派生而来，并且以共享成员方式继承 A的属性，以私有成员方式继承C的属性，相应的语法形式如下：class B: public A, private C在所有继承方式中，基类A的私有成员仍是A的私有成员，类B的成员不能够访问它们。不同的继承方式仅影响对基类的保护成员和共享成员的访问。当B按共享成员方式从A派生而来时，A的保护成员成为B的保护成员，A的共享成员成为B的共享成员。所以在编
8、写 B的成员代码时，可以直接访问 A的共享成员和保护成员，而不能够访问A的私有成员。如果X的类型为B，那么，仅当F是B或A的共享成员时，用户才可以使用语句X . F（）来执行X中的F函数。如果继承方式为保护成员，那么A中的共享成员和保护成员均成为B的保护成员。如果X和F如上所述，那么仅当函数F是B的共享成员时，用户才可以执行X . . F ( )操作。如果继承方式为私有成员，那么A中的共享成员和保护成员均成为B的私有成员。第5章堆栈1 6 3下载所有的继承方式都可以加上一个前缀v i r t u a l，第1 2章将介绍这个前缀的含义。5.3 公式化描述由于堆栈是一个受限的线性表（插入和删除操
9、作仅能在表的同一端进行） ，因此可以参考3 . 3节的线性表描述，令栈顶元素存储在e l e m e n t l e n g t h - 1 中，栈底元素存储在e l e m e n t 0 中。程序5 - 1中定义的S t a c k类是从程序3 - 1的L i n e a r L i s t类派生而来。由于继承方式为私有成员，因此L i n e a r L i s t的共享成员和保护成员都可以被S t a c k的类成员访问，而L i n e a r L i s t的私有成员不可以被S t a c k的类成员访问。程序5-1 公式化描述的堆栈类templateclass Stack : p
10、rivate LinearList / LIFO 对象p u b l i c :Stack(int MaxStackSize = 10) ：L i n e a r L i s t ( M a x S t a c k S i z e ) bool IsEmpty() constreturn LinearList:IsEmpty();bool IsFull() constreturn (Length() = GetMaxSize();T Top() constif (IsEmpty() throw OutOfBounds();T x; Find(Length(), x); return x;Sta
11、ck& Add(const T& x)Insert(Length(), x); return *this;Stack& Delete(T& x) L i n e a r L i s t : : D e l e t e (Length(), x);return *this; ;S t a c k的构造函数简单地调用线性表的构造函数，提供的参数为堆栈的大小 M a x S t a c k S i z e。没有为S t a c k类定义析构函数，因此当S t a c k类型的对象被删除时，将自动调用L i n e a r L i s t的析构函数。I s E m p t y ( )函数是对线性表相应
12、函数的简单调用。使用操作符 : 来区分基类和派生类中的同名成员。在实现函数I s F u l l时，由于S t a c k的成员不能访问L i n e a r L i s t的私有成员，因此有一定的困难。为了实现这个函数，必须知道 L i n e a r L i s t : : M a x S i z e的值。可以通过把 M a x S i z e定义成L i n e a r L i s t的保护成员来克服这个问题。然而，假如我们在稍后又修改了 L i n e a r L i s t的定义并删除了成员 M a x S i z e，那么就不得不同时修改 S t a c k的定义。一个比较好的解决
13、方法是为类L i n e a r L i s t增加一个保护成员G e t M a x S i z e ( )，语法如下：p r o t e c t e d :int GetMaxSize() const return MaxSize;这个函数可以被 S t a c k的成员所访问。如果 L i n e a r L i s t的实现发生变化，那么只需修改G e t M a x S i z e的实现，而不必修改它的任何派生类。另一种解决办法是为类 L i n e a r L i s t定义一个I s F u l l成员函数。在程序5 - 1的S t a c k : : I s F u l l代码
14、中，没有使用语法L i n e a r L i s t : : L e n g t h ( )，因为在S t a c k中没有定义L e n g t h ( )函数。函数To p首先判断堆栈是否为空，如果为空，则不存在栈顶元素，引发一个 O u t O f B o u n d s异常。当堆栈不为空时，调用线性表的F i n d函数来查找最右端的元素。函数A d d在栈顶添加一个元素x，做法是在线性表的最右端插入元素 x。D e l e t e函数删除栈顶元素，并把该元素赋予x。堆栈的删除操作是通过在线性表的最右端执行删除操作而完成的。A d d函数和D e l e t e函数均返回变化后的堆栈
15、。 A d d函数和D e l e t e函数都不能捕获可能由 I n s e r t或L i n e a r L i s t : : D e l e t e引发的异常。它们把异常留给调用它们的函数来处理。假定X是一个类型为S t a c k的对象，当F 是S t a c k的任一个共享函数时，X 的使用者可以执行语句X . F。然而，对于L i n e a r L i s t中的函数（如L e n g t h） ，不可以使用语句X . F，因为L i n e a r L i s t中的函数都不是S t a c k的共享成员（因继承方式为私有成员） 。5.3.1 Stack的效率当T是一个内部
16、数据类型时，堆栈的构造函数和析构函数的复杂性均为( 1 )，当是用户自定义的类时，构造函数和析构函数的复杂性均为 O ( M a x S t a c k S i z e )。其余每个堆栈操作的复杂性均为( 1 )。注意通过从L i n e a r L i s t派生S t a c k，一方面大大减少了编码量，另一方面也使程序的可靠性得到很大提高，因为 L i n e a r L i s t经过测试并被认为是正确的。然而，不幸的是，代码编写的简化带来了运行效率的损失。例如，为了向堆栈中添加一个元素，首先要确定堆栈的长度l e n g t h ( )，然后调用函数I n s e r t ( )。I n s e r t函数首先必须判断插入操作是否会越界，然后需要付出一个f o r循环的开销来执行0个元素的移动。为了消除额外的开销，可以把 S t a c k定义成一个基类，而不是派生类。另一种潜在的问题是派生类 S t a c k也会受到L i n e a r L i s t本身所受限制的影响。例如，必须为数据类型为T的成员定义操作符 和= =，因为前者用于对线性表操作 的重载，后者用于对L
