内蒙古大学《算法与数据结构》讲义05堆栈

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 . 8 . 3节所介绍的离线等价类问题。采用堆栈可以帮助我们在线性时间内确定等价类；最后一个应用用来解决经典的迷宫问题，即寻找一条从入口到出口的迷宫路径。应该仔细地研究这个应用，因为它体现了许多软件工程的原理和思想。本章中所用到的C + +语言的新的特性是派生类和继承。5.1 抽象数据类型定义堆栈 堆栈（s t a c k）是一个线性表，其插入（也称为添加）和删除操作都在表的同一端进行。其中一端被称为栈顶（t o p） ，另一端被称为栈底（b o t t o m） 。图5-1a 给出了一个四元素的堆栈。假定希望在5-1a 的堆栈中添加一个元素E，这个元素将被放到元素D的顶部，所得到的结果如图5-1b 所示。如果想从5-1b 的堆栈中删除一个元素，那么元素E将被

3、删除，删除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 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 派生类和继承我们经常会处理这样一类新的数据对象，它是某种更通用的数据对象的特殊版本或限制版本。例如，本章中的堆栈

4、数据对象就是更通用的线性表对象的限制版本。堆栈数据对象的实例也是线性表数据对象的实例，而且，所有的堆栈操作都可以利用线性表操作来实现。例如，如果把表的左端定义为栈底，右端定义为栈顶，那么堆栈的添加操作等价于在表的右端进行插入操作，删除操作等价于在表的右端进行删除操作。根据上述观察，我们期望如果能够明确地把堆栈表示成特殊的线性表，那么可以简化 C + +堆栈类的实现，而且，可以参照线性表的操作来定义堆栈操作。若类B是另一个类A的限制版本，那么可以从A派生出B。我们称A为基类，B为派生类。从类A派生出的类B继承了基类A的所有成员共享成员、保护成员和私有成员。类型为 B的每个对象都与A所有的数据成员和函数相关联。类B可以采用如下三种基本方式之一来继承类A的成员：共享成员、保护成员和私有成员。比如，对于共享成员方式，可以采用如下语法形式：class B: public A一个类可以从多个类派生而来。若类 B从A和C派生而来，并且以共享成员方式继承 A的属性，以私有成员方式继承C的属性，相应的语法形式如下：class B: public A, private C在所有继承方式中，基类A的私有成员

5、仍是A的私有成员，类B的成员不能够访问它们。不同的继承方式仅影响对基类的保护成员和共享成员的访问。当B按共享成员方式从A派生而来时，A的保护成员成为B的保护成员，A的共享成员成为B的共享成员。所以在编写 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 公式化描述由于堆栈是一个受限的线性表（插入和删除操作仅能在表的同一端进行） ，因此可以参考3 . 3节的线性表描述，令栈顶元素存储在e l e m e n t l e n g t h - 1 中，栈底元素存储在e l e m e n t 0 中。程序

6、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 : private 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

7、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 ( )函数是对线性表相应函数的简单调用。使用操作符 : 来区分基类和派生类中的同名成员。在实现函数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的保护

8、成员来克服这个问题。然而，假如我们在稍后又修改了 L i n e a r L i s t的定义并删除了成员 M a x S i z e，那么就不得不同时修改 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 ( )，语法如下：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代码中，没有使用语法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首先判断堆栈是否为空，

9、如果为空，则不存在栈顶元素，引发一个 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函数均返回变化后的堆栈。 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是一个内部

10、数据类型时，堆栈的构造函数和析构函数的复杂性均为( 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

《内蒙古大学《算法与数据结构》讲义05堆栈》由会员东***分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义05堆栈》请在金锄头文库上搜索。