堆栈的实现

堆栈，是一种数据结构，其插入和删除操作都在同一端进行，其中一端称作栈顶，另外一端称作栈底。其中，堆栈是一种先进后出的数据结构，既可以使用公式化描述实现，也可以使用链表描述进行实现。

例如，我们向栈中插入元素10,20.30，则从栈顶向栈底排列分别为30,20,10，则弹出的时候，分别以30,20,10的顺序弹出，在这篇中，先使用公式化描述和链表实现堆栈，在后面将学习几个使用堆栈的比较典型的例子，其中包括括号匹配，汉诺塔，火车重排，离线等价类，迷宫等问题。

好了，话不多说，堆栈的实现还是比较简单的，下面附上我的代码：

首先使用公式化描述实现的堆栈：

/**
 * 堆栈是一个线性表，其插入和删除操作都在同一端进行
 * 其中一端成为栈顶，另一端成为栈底
 *
 * 堆栈是一种先进后出或者是后进先出的数据结构
 * 可以使用公式化描述实现堆栈，也可以使用链表实现堆栈
 *
 */
#include "Exception.h"
#include <iostream>

using namespace std;

/**
 * 适用公式化描述实现LinearStack
 */
template<class T>
class LinearStack{
public:
    LinearStack(int MaxLinearStackSize = 10);
    ~LinearStack(){delete [] stack;}
    bool isEmpty() const{return top == -1;}    //返回栈是否为空
    bool isFull() const{return top == MaxTop;} //栈是否已满
    T Top() const;  //获取栈顶元素
    LinearStack<T>& Add(const T& x);    //向栈中添加一个元素
    LinearStack<T>& Delete(T& x);   //从栈中删除一个元素
    int Size() const;   //获取堆栈的大小
    LinearStack<T>& Add(T array[],int addedSize);  //输入一个堆栈
    void print(); //输出堆栈中的数据

private:
    int top;  //栈顶
    int MaxTop; //栈的最大容量
    T *stack;
};

template <class T>
LinearStack<T>::LinearStack(int MaxLinearStackSize){
    MaxTop = MaxLinearStackSize - 1;
    top = -1;
    stack = new T[MaxLinearStackSize];
}

template<class T>
T LinearStack<T>::Top() const{
    if(isEmpty()) throw OutOfBounds();

    else return stack[top];
}

template<class T>
LinearStack<T>& LinearStack<T>::Add(const T& x){
    if(isFull()) throw OutOfBounds();

    top ++;
    stack[top] = x;

    return *this;
}

template<class T>
LinearStack<T>& LinearStack<T>::Delete(T& x){
    if(isEmpty()) throw OutOfBounds();

    x = stack[top--];

    return *this;
}

template<class T>
int LinearStack<T>::Size() const{

    int size = top+1;

    return size;
}

template<class T>
LinearStack<T>& LinearStack<T>::Add(T array[],int addedSize){
    int size = this->Size();

    int left = MaxTop + 1 - size;

    if(left < addedSize)
        throw OutOfBounds();

    for(int i = 0;i < addedSize;i++){
        this->Add(array[i]);
    }

    return *this;
}

template<class T>
void LinearStack<T>::print(){
    int size = this->Size();

    for(int i = size-1;i >= 0;i--){
        cout << stack[i] << " ";
    }

    cout << endl;
}

下面一个是使用链表实现的堆栈：

/*
 * LinkedStack.cpp
 *
 *  Created on: 2015年5月7日
 *      Author: 洪波
 */

#include "Exception.h"
#include <iostream>

using namespace std;

template<class T>
class LinkedStack;

template<class T>
class Node{
friend class LinkedStack<T>;

private:
    T data;
    Node<T> *link;
};

template<class T>
class LinkedStack{
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 print();

private:
    Node<T> *top;  //指向栈顶节点
};

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 &nm){
        return true;
    }
}

template<class T>
T LinkedStack<T>::Top() const{

    return top->data;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x){

    Node<T> *node = new Node<T>();
    node->data = x;
    node->link = top;

    top = node;

    return *this;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x){
    if(IsEmpty()) throw OutOfBounds();

    Node<T> *p = top;
    x = top->data;
    top = top->link;

    delete p;

    return *this;
}

template<class T>
void LinkedStack<T>::print(){
    Node<T> *p = top;

    while(p){
        cout << p->data << " ";
        p = p->link;
    }

    cout << endl;
}

下面是我的测试类：

/*
 * Test.cpp
 *
 *  Created on: 2015年5月7日
 *      Author: 洪波
 */
#include "LinearStack.cpp"
#include "LinkedStack.cpp"

int main(){

    /**********************************************
     *          测试 LinearStack                    *
     **********************************************/
//  LinearStack<int> ls(10);
//
//  ls.Add(10);
//  ls.Add(20);
//
//
//  ls.print();
//
//  int array[3] = {30,40,50};
//
//  ls.Add(array,3);
//
//  ls.print();

    /*====================================================*/

    /**********************************************
     *          测试 LinkedStack                    *
     **********************************************/

    LinkedStack<int> linkedS;
    linkedS.Add(10);
    linkedS.Add(20);

    linkedS.print();

    int n;
    linkedS.Delete(n);
    cout << n << endl;
    return 0;
}

其中，头文件”Exception.h”在我之前数据结构和算法的代码中有。堆栈在平常使用中用的还是挺多的。但相对来说其实现方式还是比较简单的，其插入和删除操作的时间复杂度都是O(1),即压栈和弹出的时间复杂度都是O(1)。效率还是蛮高的。

向程序运行过程中，函数的调用，在保存状态点的时候，都是保存到栈中的。其中比较典型的应用实例就是火车重排问题，离线等价类问题，汉诺塔问题，迷宫求解问题，括号匹配问题等。我会将在下面一章节中学习这些实例的实现。