栈

栈是限定仅在一端进行插入或删除操作的线性表。虽然这个限制减小了栈的灵活性，但是也使得栈更有效，更容易实现。栈还有一个名字，称为LIFO（后进先出）线性表，意味着栈存储和删除元素的顺序与元素到达的顺序相反。习惯上我们称栈的可访问元素为栈顶元素(top)，元素插入栈称为入栈(push)，删除元素称为出栈(pop)。由于栈是一种特殊的线性表，所以栈的实现形式也有以下两种：顺序栈和链式栈，下文将对这两种实现分别论述。

栈ADT

根据前面栈的简介，我们很方便定义出栈的ADT：

template <typename E> class Stack
{
private:
    void operator =(const Stack&) {}
    Stack(const Stack&) {}

public:
    Stack() {}
    virtual ~Stack() {}
    virtual void clear() = 0;
    virtual void push(const E& it) = 0;
    virtual E pop() = 0;
    virtual const E& topValue() const = 0;
    virtual int length() const = 0;
};

顺序栈

顺序栈的实现，本质上是顺序表实现的简化。唯一重要的是，确定应该用数组的哪一端表示栈顶，显然，为了减少栈操作的时间消耗，我们应该当栈中有n个元素时把位置n-1作为栈顶，即选用线性表的末尾作为栈顶。具体实现中，我们将top定义为表示栈中的第一个空闲位置，因此，空栈的top为0。根据top的定义，我们的push首先把一个值插入到栈顶位置，然后把top加1，同样，pop首先把top减1，然后删除栈顶元素。

下面给出顺序栈类的实现：

template <typename E> class AStack: public Stack<E>
{
private:
    int maxSize;
    int top;
    E *listArray;

public:
    AStack(int size=defaultSize)
    { maxSize = size; top = 0; listArray = new E[size]; }

    ~AStack() { delete [] listArray; }

    void clear() { top = 0; }

    void push(const E& it)
    {
        Assert(top != maxSize, "Stack is full");
        listArray[top++] = it;
    }

    E pop()
    {
        Assert(top != 0, "Stack is empty");
        return listArray[--top];
    }

    const E& topValue() const
    {
        Assert(top != 0, "Stack is empty");
        return listArray[top-1];
    }

    int length() const { return top; }
};

如何类比顺序栈和顺序表呢？我们可以发现，顺序栈中的top简直和顺序表中的curr一毛一样，元素的增删查都要通过它。事实上，这是因为top和curr的定义均为当前元素指针，理所当然我们要当前位置指针来进行对象操作了。由于数组是固定大小的，我们的增删查操作进行前要分别进行判满和判空处理。还有一点需要注意，由于是顺序栈，所以在对象的销毁和表的复原操作上非常简单，销毁我们只需要delete掉给listArray分配的数组空间，clear我们仅需要将top指针指向0号位置即可。包括删除操作，我们并不需要真正去修改要删除结点的存储内容，反正我们有栈顶封着，上面那些元素只是单纯的内存单元，存储的是啥不干我们的顺序栈的事。

顺便一提，当需要实现多个栈时，可以充分利用顺序栈单向延伸的特性。因此，可以使用一个数组来存储两个栈，每个栈从各自的端点向中间延伸，如下图，这样浪费的空间就会减少。但是，只有当两个栈的空间需求有相反的关系时，这种方法才奏效。即最好一个栈增长时另一个栈缩短。当需要从一个栈中取出元素放入另一个栈中时，这种方法非常有效。

线性表（四）栈、队列-LMLPHP

链式栈

相应的，链式栈的实现是对链表实现的简化。我们之前介绍过的可利用空间表实际上就是一个链式栈的实例。其元素只能在表头进行插入和删除。由于空栈或只有一个元素的栈都不需要特殊情形的结点，所以它不需要表头结点。

下面我们给出链式栈的实现：

template <typename E> class LStack: public Stack<E>
{
private:
    Link<E>* top;
    int size;

public:
    LStack(int sz=defaultSize)
    { top = NULL; size = 0 }

    ~LStack() { clear(); }

    void clear() // 这里本人有些不解，咋复原和销毁成一样了呢？
    {
        while(top != NULL)
        {
            Link<E>* temp = top;
            top = top->next;
            delete temp;
        }
        size = 0;
    }

    void push(const E& it)
    {
        top = new Link<E>(it, top);
        size++;
    }

    E pop()
    {
        Assert(top != NULL, "Stack is empty");
        E it = top->element;
        Link<E>* ltemp = top->next;
        delete top;
        top = ltemp;
        size--;
        return it;
    }

    const E& topValue() const
    {
        Assert(top != 0, "Stack is empty");
        return top->element;
    }

    int length() const { return size; }
};

这里我们做一个小小的总结：类的形式实现数据结构极大的方便了我们将数据结构进行类比以及对数据结构组件的统一管理，我们编写每一个操作时只要思考private修饰符下方的成员属性如何维护以及判空和判满即可，十分方便记忆和编写。我们同时采用继承ADT类的形式，规范了数据结构的接口，使得编写的代码既不会遗漏什么关键操作，又符合一定的规范，方便用户使用。

另外我们可以看到，链式栈的增删查操作的具体代码简直就是链表的复刻，对此我们可以对比学习，统一记忆。

注：我们本例代码中使用到的Link类沿用了之前我们在单链表定义时Link类的定义，如果读者有疑问请点击这里

栈的应用

大多数情况下，我们看不到栈的最广泛应用，这就是大多数程序设计语言运行环境都有的子程序调用。子程序调用是通过把有关子程序的必要信息(包括返回地址、参数、局部变量)存储到一个栈中实现的，这块信息称为活动记录(activation record)；子程序调用把活动记录压入栈，每次从子程序中返回时，就从栈中弹出一个活动记录。下面从编译器的角度，以递归阶乘函数为例解释这一过程。（如果学过汇编或者计算机组成原理PC指针与寄存器这块，下面这段话将不难理解）

考虑用4来调用fact：用来表示程序调用fact的指令所在的地址。因此，在第一次调用fact时，必须把地址存放到栈中，并且把4传递给fact。程序接下来再对fact进行一次递归调用，这次参数值变为3。把做这次调用的指令地址记为，该地址连同n的当前值(4)被保存到栈中，此时调用函数fact所用的输入参数3。

利用类似的方式，程序递归调用直至到达了fact的初始状态(n=1)，此时将不会有活动记录入栈，将开始展开递归：每一次从fact返回都将弹出栈所保存的n的当前值，以及函数调用所返回的地址。通过存储n的当前值，使得fact的返回值逐次累积，并且返回最后结果。（对这一问题的深刻理解有助于递归程序的设计，因为递归程序设计中最难的部分就是思考如何保存和返回结果——刘汝佳紫书）

线性表（四）栈、队列-LMLPHP

从上述过程可以看出，由于需要生成一个活动记录，并把它压入栈中，一个递归程序的时空开销是十分巨大的，所以多数情况下，我们在享用递归程序带来的代码简洁性清晰性的同时，还要思考这种递归的设计与我们设计程序的目标是否相符。

ps：最后附上两道比较经典的栈的基础题铁轨矩阵链乘，分别考察了栈的后进先出特性，以及栈在解析表达式中的应用。

队列

同栈一样，队列也是一种受限的线性表。它又被称作FIFO(先进先出)线性表，对应的基本操作为入队(enqueue)和出队(dequeue)，这一点我们可以很直观的和真实生活中的排队现象做类比，话不多说，上ADT定义：

template <typename E> class Queue
{
private:
    void operator =(const Queue&) {}
    Queue(const Queue&) {}

public:
    Queue() {}
    virtual ~Queue() {}
    virtual void clear() = 0;
    virtual void enqueue(const E&) = 0;
    virtual E dequeue() = 0;
    virtual const E& frontValue() const = 0;
    virtual int length() const = 0;
};

同样的对于队列，我们也有顺序队列和链式队列。出于操作方便，对于队列我们需要两个指针front和rear分别指示队列和队尾。

顺序队列

顺序队列的实现我们与常规的线性结构略微有些不同。物理上，其存储仍为一个数组，逻辑上则体现为环形队列（其具体原因涉及到队列的移动问题，为了减少每次入队出队时带来的不必要的移动时间成本，故我们采用这种形式）。

所幸的是，有些数论基础的人会发现，环形队列的数组下标的循环可以对应到数的循环问题，在数论中就是将数取模。所以我们使用取模操作，可以很容易实现顺序队列逻辑上的循环。（在这种方法中，数组中的位置编号从0到size-1，size-1被定义为位置0，即等价于位置size%size的前驱）

和所有顺序线性表类似，我们还需要考虑的是顺序队列的判空和判满问题。我们不妨假设front存储队列中队首元素的位置号，rear存储队尾元素的位置号。如果front和rear位置相同，则表示队列中只有一个元素；当rear比front小1则表示队列为空。那么我们在来考虑队满的情况，当一个有n个可用位置的队列含有n个元素，如果队首元素在位置0，则队尾元素一定在位置size-1。我们发现，这种定义下我们并不能区分队满和队空的情况。那么是不是修改定义就可以解决问题呢？我们吃惊的发现，无论我们如何修改front和rear的定义，都不能解决这一问题。这就涉及到鸽笼原理了，如果数组有n个位置，则队列中最多可以存储n个元素(可以定义为front和rear之差)，但队列却可以有n+1种不同的状态(有0到n个元素)。也就是说，如果我们用front的rear的相对值来定义队列的状态，则必然有两种不能区分。

ps：这一问题让博主联想到动态规划问题求解中状态的定义问题，求解一个动态规划问题的关键首先在于能不能设计出一种能不重不漏描述解状态空间的状态定义。

对于环形队列的矛盾，我们可以采用以下两种解决方案：

1.用一个布尔变量来指示队列是否为空

2.设置数组的大小为n+1，但是只需存储n个元素。

本篇给出的代码示例采用第二种形式。

template <typename E> class AQueue: public Queue<E>
{
private:
    int maxSize;
    int front;
    int rear;
    E *listArray;

public:
    AQueue(int size=defaultSize)
    {
        maxSize = size+1;
        // 输入是用户想要的队列最大长度size，maxSize则是实际开的数组大小，十分人性化
        rear = 0; front = 1;
        listArray = new E[maxSize];
    }

    ~AQueue() { delete [] listArray; }

    void clear() { rear = 0; front = 1; }

    void enqueue(const E& it)
    {
        Assert(((rear+2) % maxSize) != front, "Queue is full");
        rear = (rear+1) % maxSize;
        listArray[rear] = it;
    }

    E dequeue()
    {
        Assert(length() != 0, "Queue is empty");
        E it = listArray[front];
        front = (front+1) % maxSize;
        return it;
    }

    const E& frontValue() const
    {
        Assert(length() != 0, "Queue is empty");
        return listArray[front];
    }

    int length() const
    { return ((rear+maxSize) - front + 1) % maxSize; }
};

注意：顺序队列的指针移动不是简单的加1，还要取模，因为它是环状的。（rear = (rear+1) % maxSize; front = (front+1) % maxSize;）;我们还需注意，enqueue中判满的方法是(rear+2) % maxSize ?= front;

链式队列

链式队列的实现不过是对链表实现做了简单的修改，为了简化实现方式和相关操作，我们同样可以使用一个头结点。在初始化的时候，front和rear同时指向头结点，之后front总是指向头结点，而rear指向队列的尾结点。enqueue和dequeue分别使用的是rear和front指针(脑补一下排队场景就不会弄混)。下面是代码是实现：

template <typename E> class LQueue: public Queue<E>
{
private:
    Link<E>* front;
    Link<E>* rear;
    int size;

public:
    LQueue(int sz = defaultSize)
    { front = rear = new Link<E>(); size = 0; }

    ~LQueue()
    { clear(); delete front; }

    void clear()
    {
        while(front->next != NULL) // 这样之后队列为空，只剩下一个头结点，里面内容为啥不重要
        {
            rear = front;
            delete rear;
            front = front->next;
        }
        rear = front;
        size = 0;
    }

    void enqueue(const E& it)
    {
        rear->next = new Link<E>(it, NULL);
        rear = rear->next;
        size++;
    }


    E dequeue()
    {
        Assert(size != 0, "Queue is empty");
        E it = front->next->element;
        Link<E>* ltemp = front->next;
        front->next = ltemp->next; // 此处要特别注意，别写成front = front->next;
                                   // 删除的是第一个队列元素，而front是头结点，不为任何元素
        if(rear == ltemp) rear = front; // 删除的时候一般都要特别判断删除末尾元素（类比链表）
        delete ltemp;
        size--;
        return it;
    }


    const E& frontValue() const
    {
        Assert(size != 0, "Queue is empty");
        return front->next->element;
    }

    int length() const { return size; } // 源代码此处有一个virtual，我不是很理解
};

注：链式队列的实现中，clear和dequeue函数可以关注一下，略微有些不同寻常。

ps：对于队列及其应用还想加深一下的读者可以看一下并行程序模拟这道题，用到了双端队列以及队列在管理进程方面的作用。

小蜜蜂

线性表（四） 栈、队列

栈

栈ADT

顺序栈

链式栈

栈的应用

队列

顺序队列

链式队列

线性表（四）栈、队列