堆栈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

小结

本小节主要是介绍了堆栈的基本实现方法，分为数组实现和链表实现，实现的代码也是比较简单的。下面一节会介绍堆栈的一些应用，包括括号匹配，汉诺塔等。