转载

堆栈 1-- 基本概念及实现方法

继续是《数据结构算法与应用：C++语言描述》的笔记，这次是新的一章内容，第五章堆栈。

堆栈数据结构是通过对线性表的插入和删除操作进行限制而得到的，即插入和删除操作都必须在表的同一端完成，因此堆栈是一个 后进先出(last-in-first-out,LIFO) 的数据结构。

由于堆栈是一种特殊的线性表，所以可以很自然地从相应的线性表类中派生出堆栈类，既可以从基于公式描述的类 LinearList 类派生，也可以从基于链表结构的类 Chain 派生出堆栈类。

抽象数据类型

这里给出堆栈的抽象数据类型描述

抽象数据类型Stack{ 实例     元素线性表，栈底，栈顶 操作     Create(): 创建一个空的堆栈     IsEmpty(): 如果堆栈为空，则返回true，否则返回false     IsFull(): 如果堆栈满，则返回true，否则返回false     Top(): 返回栈顶元素     Add(x): 向堆栈中添加元素x     Delete(x): 删除栈顶元素，并将它传递给x }

派生类和继承

若类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的私有成员仍是A的私有成员，类B的成员不能够访问它们。不同的继承方式仅影响对基类的保护成员和共享成员的访问。

当B按照共享成员方式从A派生出来，A的保护成员成为B的保护成员，A的共享成员成为B的共享成员。

如果继承方式是保护成员，那么A的共享成员和保护成员均成为B的保护成员。

如果继承方式是私有成员，那么A的共享成员和保护成员均成为B的私有成员。

公式化描述

由于堆栈是一个受限的线性表，因此可以参考数据描述1-线性表中的公式化描述，令栈顶元素存储在 element[length-1] ，栈底元素存储在 element[0] 中。下列程序定义的Stack类将使用私有成员方法继承数据描述1-线性表中定义的类LinearList。

#ifndef INHERITSTACK_H_ #define INHERITSTACK_H_ #include<iostream>  template<class T> class Stack : private LinearList<T> { public:     Stack(int MaxStackSize = 10) : LinearList<T>(MaxStackSize){}     bool IsEmpty() const{         return LinearList<T>::isEmpty();     }     bool IsFull() const{         return (Length() == GetMaxSize());     }     T Top() const;     Stack<T>& Add(const T& x);     Stack<T>& Delete(T& x);     void Output(std::ostream& out)const; };  template<class T> T Stack<T>::Top() const{     if (IsEmpty())         throw OutOfBounds();     T x;     Find(Length(), x);     return x; }  template<class T> Stack<T>& Stack<T>::Add(const T& x){     Insert(Length(), x);     return *this; }  template<class T> Stack<T>& Stack<T>::Delete(T& x){     LinearList<T>::Delete(Length(), x);     return *this; }  template<class T> void Stack<T>::Output(std::ostream& out)const{          for (int i = 0; i < length; i++)         out << element[i] << " ";     out << "/n"; }  // 重载 << template<class T> std::ostream& operator<<(std::ostream&out, const Stack<T>& x){     x.Output(out);     return out; } #endif

这里，Stack的构造函数简单调用线性表的构造函数，提供的参数为堆栈的大小 MaxStackSize 。这里使用操作符 :: 来区分基类和派生类的同名成员。

在实现函数 IsFull 时，由于Stack的成员不能直接访问基类的私有成员，因此可以在基类LinearList中增加一个保护成员的函数 GetMaxSize ，其实现如下:

protected:     int GetMaxSize() const{         return MaxSize;     }

Stack的效率

当T是一个内部数据类型时，堆栈的构造函数和析构函数的复杂性均为$/theta(1)$,当T时用户自定义的类时，构造函数和析构函数的复杂性均为$O(MaxStackSize)$。其余每个堆栈操作的复杂性均为$/theta(1)$。

这里通过从 LinearList 派生 Stack ，一方面大大减少了编码量，另一方面也使得程序的可靠性得到很大提高，因为 LinearList 经过测试被认为是正确的。

当然，继承有利的一方面，也有弊端。代码编写的简化带来了运行效率的损失。比如，为了向堆栈中添加一个元素，首先要确定堆栈的长度 Length() ，然后调用函数 Insert() 。 Insert() 函数首先会判断插入操作是否会越界，然后需要付出一个for循环的开销来执行0个元素的移动。为了消除额外的开销，可以把 Stack 定义为一个基类，而不是一个派生类。

另一个潜在问题是派生类 Stack 也会受到 LinearList 本身所受限制的影响。比如，必须为数据类型为T的成员定义操作符<<和==，因为前者用于对线性表操作<<的重载，后者用于对 LinearList::Search 的重载。

自定义Stack

下面是自定义Stack的类定义实现。

#ifndef STACK_H_ #define STACK_H_ #include<iostream>  template<class T> class Stack{ private:     // 栈顶     int top;     // 最大的栈顶值     int MaxTop;     // 堆栈元素数组     T* stack; public:     Stack(int MaxStackSize = 10);     ~Stack(){ delete[] stack; }     bool IsEmpty() const{ return top == -1; }     bool IsFull() const { return top == MaxTop; }     T Top() const;     Stack<T>& Add(const T& x);     Stack<T>& Delete(T& x);     template<class T>     friend std::ostream& operator<<(std::ostream&, const Stack<T>&); }; #endif

下面是类成员函数的定义实现

template<class T> Stack<T>::Stack(int MaxStackSize){     // 构造函数     MaxTop = MaxStackSize - 1;     stack = new T[MaxStackSize];     top = -1; }  template<class T> T Stack<T>::Top()const{     // 返回栈顶元素     if (IsEmpty())         throw OutOfBounds();     else         return stack[top]; }  template<class T> Stack<T>& Stack<T>::Add(const T& x){     // 添加元素     if (IsFull())         throw NoMem();     stack[++top] = x;     return *this; }  template<class T> Stack<T>& Stack<T>::Delete(T& x){     // 删除栈顶元素，并将其传送入x     if (IsEmpty())         throw OutOfBounds();     x = stack[top--];     return *this; }  template<class T> std::ostream& operator<<(std::ostream& out, const Stack<T>& x){     int pos = x.top;     if (x.IsEmpty())         std::cout << "There is no elements in stack";     while (pos != -1){         std::cout << x.stack[pos] << " ";         pos--;     }     std::cout << "/n";     return out; }

通过测试，自定义Stack在添加和删除操作要比通过继承而得到的类Stack的相应操作要更快。

链表描述

上一节给出用数组实现堆栈的方法即优雅又高效，但是若同时使用多个堆栈，这种方法将浪费大量的空间。

这里可以使用链表描述，下面给出自定义链表类 LinkedStack 的类定义声明。

#ifndef LINKEDSTACK_H_ #define LINKEDSTACK_H_ #include<iostream> using std::ostream; template<class T> class LinkedStack;  template<class T> class Node{     friend LinkedStack<T>; private:     T data;     Node<T>* link; };  template<class T> class LinkedStack{ private:     Node<T>* top; public:     LinkedStack(){ top = 0; }     ~LinkedStack();     bool IsEmpty() const{ return top == 0; }     bool IsFull() const;     T Top()const;     LinkedStack<T>& Add(const T& x);     LinkedStack<T>& Delete(T& x);     void Output(ostream&); }; #endif

其类成员函数实现如下所示：

 // 析构函数 template<class T> LinkedStack<T>::~LinkedStack(){     Node<T>* next;     while (top){         next = top->link;         delete top;         top = next;     } }  template<class T> bool LinkedStack<T>::IsFull()const{     try{         Node<T>* p = new Node<T>;         delete p;         return false;     }     catch (NoMem){         return true;     } }  template<class T> T LinkedStack<T>::Top()const{     if (IsEmpty())         throw OutOfBounds();     return top->data; }  template<class T> LinkedStack<T>& LinkedStack<T>::Add(const T& x){     // 添加元素x     Node<T>* p = new Node<T>;     p->data = x;     p->link = top;     top = p;     return *this; }  template<class T> LinkedStack<T>& LinkedStack<T>::Delete(T& x){     // 删除元素，并传给x返回     if (IsEmpty())         throw OutOfBounds();     x = top->data;     Node<T>* p = top;     top = top->link;     delete p;     return *this; }  template<class T> void LinkedStack<T>::Output(ostream& out){     if (IsEmpty())         out << "There is no elements in LinkedStack";     Node<T>* p = top;     while (p){         out << p->data << " ";         p = p->link;     }     out << "/n"; }  template<class T> ostream& operator<<(ostream& out,LinkedStack<T>& x){     x.Output(out);     return out; }

这里仅给出自定义链栈 LinkedStack ，同样可以通过继承线性表的链表实现类来派生出链栈，但是 LinkedStack 在添加和删除操作上的效率要更加高点。

代码实现可以查看我的 Github