数据结构-02：栈

栈的抽象类

template <class elemType>
class stack
{
public:
    virtual bool isEmpty() const = 0;
    virtual void push(const elemType &x) = 0;
    virtual elemType pop() = 0;
    virtual elemType top() const = 0;
    virtual ~stack() {}
};

栈的规则简单总结为：只能在同一端操作。push、pop、top 都围绕“栈顶”进行，调用者不应该关心栈底或中间元素。这个限制看似简单，却能把括号匹配、函数调用、表达式求值等“最近打开的东西要最先关闭”的问题自然建模出来。

顺序栈

顺序栈用数组保存元素，逻辑上的栈顶对应数组中的一个下标。它的优点是结构紧凑、访问栈顶非常快，缺点是容量来自数组，满了就必须扩容。实现时最重要的变量是 top_p：它既表示栈顶位置，也间接表示当前栈内元素个数。

顺序栈适合元素数量上界较容易估计、并且希望获得较好缓存局部性的场景。由于所有元素连续存储，访问和扩容时复制都很直接。

代码实现

//类定义
template <class elemType>
class seqStack: public stack<elemType>
{
private:
    elemType *elem;  // 存放栈元素的动态数组
    int top_p;       // 栈顶下标，-1表示空栈
    int maxSize;     // 当前数组容量
    void doubleSpace(); // 栈满时扩容
public:
    seqStack(int initSize = 10);
    ~seqStack();
    bool isEmpty() const;
    void push(const elemType &x);
    elemType pop();
    elemType top() const;
};

//构造函数
template <class elemType>
seqStack<elemType>::seqStack(int initSize) {
    elem = new elemType[initSize];
    maxSize = initSize;
    top_p = -1; // 空栈时没有有效栈顶
}

//析构函数
template <class elemType>
seqStack<elemType>:: ~seqStack()
{ delete [] elem; }

//判栈空
template <class elemType>
bool seqStack<elemType>:: isEmpty() const
{ return top_p == -1; }

//入栈
template <class elemType>
void seqStack<elemType>::push(const elemType &x)
{
    if (top_p == maxSize - 1) doubleSpace(); // 栈满则先扩容
    elem[++top_p] = x; // 先移动栈顶，再写入新元素
}

//出栈
template <class elemType>
elemType seqStack<elemType>::pop()
{ return elem[top_p--]; } // 返回旧栈顶，再将栈顶下移

//读栈顶
template <class elemType>
elemType seqStack<elemType>::top() const
{ return elem[top_p]; } // 只读栈顶，不改变栈结构

//扩充空间
template <class elemType>
void seqStack<elemType>::doubleSpace(){
    elemType *tmp = elem; // 暂存旧数组地址
    elem = new elemType[2 * maxSize];
    for (int i = 0; i < maxSize; ++i) elem[i] = tmp[i];
    maxSize *= 2;
    delete [] tmp;
}

顺序栈的状态完全由 top_p 决定：top_p == -1 表示空栈，top_p 指向数组中最后一个有效元素。入栈时先让 top_p 加一，再写入元素；出栈时先返回 elem[top_p]，再让 top_p 减一。读代码时只要盯住 top_p 的移动方向，就能判断每一步是否改变了栈结构。

这里的 pop() 和 top() 都默认调用前栈非空。实际工程实现通常会在这两个函数中增加空栈检查，否则对空栈执行 pop() 会访问无效数组位置。

性能分析

除进栈操作外，由于只在栈顶进行一次操作，所有实现的时间复杂度均为 $O(1)$ 。

进栈运算最坏情况下需要 $O(n)$ 的时间复杂度（进行了一次 doubleSpace 操作）。但是将每一次扩充数组的操作均摊到前 $n$ 次进栈操作上，平均每次进栈操作的时间复杂度仍然为 $O(1)$ ，即插入运算的均摊时间复杂度仍然为 $O(1)$ 。

链栈

链栈把栈顶放在链表头部。这样入栈就是在头部插入新结点，出栈就是删除头结点，两者都只改常数条指针。它不需要扩容，但每个元素都要额外保存一个 next 指针，并且动态分配结点会比数组下标操作更重。

如果栈的规模变化很大，或者无法预先分配足够数组空间，链栈会更灵活。它的边界条件也很清晰：top_p == nullptr 表示没有任何元素。

代码实现

template <class elemType>
class linkStack: public stack<elemType>
{
private:
    struct node {
        elemType data; // 当前结点保存的栈元素
        node *next;    // 指向下一个结点，即更靠近栈底的元素
        node(const elemType &x, node *n = nullptr) : data(x), next(n) {}
        node() : next(nullptr) {}
        ~node() {}
    };
    node *top_p; // 链栈栈顶指针
public:
    linkStack();
    ~linkStack();
    bool isEmpty() const;
    void push(const elemType &x);
    elemType pop();
    elemType top() const;
};

template <class elemType>
linkStack<elemType>::linkStack() : top_p(nullptr) {}

template <class elemType>
linkStack<elemType>::~linkStack() {
    node* tmp;
    while (top_p != nullptr) {
        tmp = top_p;        // 保存当前栈顶
        top_p = top_p->next; // 栈顶后移，避免释放后无法继续遍历
        delete tmp;
    };
}

其余的读栈顶，弹出，入栈操作均与链表类似

链栈与顺序栈的区别在于：链栈不需要预先知道容量，每次 push 都新建一个结点并让它成为新的 top_p。因此链栈不会触发数组扩容，但每个元素都多存一个指针，并且频繁 new/delete 会带来额外开销。读链栈时可以把 top_p 理解为“链表头指针”，栈顶就是链表第一个结点。

栈的应用

栈适合处理具有“嵌套”“回退”“最近未完成任务”特征的问题。括号匹配中，最近出现的左括号必须最先被右括号匹配；表达式求值中，最近读到但尚未参与运算的操作数或运算符需要暂存；函数调用中，最近进入的函数也会最先返回。这些问题都天然符合后进先出的约束。

括号配对检查

首先创建一个空栈。
从源程序中读入符号。
如果读入的符号是开符号，那末就将其进栈。
如果读入的符号是一个闭符号但栈是空的，出错。否则，将栈中的符号出栈。
如果出栈的符号和和读入的闭符号不匹配，出错。
继续从文件中读入下一个符号，非空则转向 3，否则执行 7。
如果栈非空，报告出错，否则括号配对成功。

括号匹配之所以适合用栈，是因为它满足“后打开的括号必须先关闭”。例如读到 ([{}]) 时，最晚入栈的是 {，它也必须最先遇到 }。如果遇到闭括号时栈为空，说明它没有对应的左括号；如果弹出的左括号类型不匹配，说明嵌套顺序错误；扫描结束后栈不为空，则说明还有左括号没有被关闭。

简单计算器的实现

计算机中的算术运算常用后缀表达式（逆波兰式），其优点是在求值阶段不需要再处理运算符优先级和括号。

中缀表达式符合人类书写习惯，例如 3 + 4 * 5，但计算机直接扫描时必须不断判断优先级和括号范围。后缀表达式把这些优先级关系提前转化为顺序，例如 3 4 5 * +，求值阶段只需要从左到右扫描。因此简单计算器通常分成两步：先把中缀转后缀，再用栈计算后缀表达式。

中缀表达式转后缀表达式的步骤

若读入的是操作数，立即输出。
若读入的是闭括号，则将栈中的运算符依次出栈，并将其放在操作数序列之后。出栈操作一直进行到遇到相应的开括号为止。将开括号出栈。
若读入的是开括号，则进栈。
若读入的是运算符，如果栈顶运算符优先级高于或等于当前运算符，则栈顶运算符出栈；出栈操作一直要进行到栈顶运算符优先级低于当前运算符为止，然后将新读入的运算符进栈保存。

关于优先级相关概念的解释：当你读取到一个运算符时（比如 +、-、*、/ 等），需要决定是直接将其压入栈中，还是先弹出栈顶的运算符。这个决定基于当前读取的运算符与栈顶运算符的优先级比较：如果栈顶运算符的优先级高于或等于当前运算符，那么栈顶运算符应该先被弹出并输出到后缀表达式中。然后继续比较新的栈顶运算符，直到栈顶运算符优先级低于当前运算符，或者栈为空。最后，将当前读取的运算符压入栈中。

在读入操作结束时，将栈中所有的剩余运算符依次出栈，并放在操作数序列之后，直至栈空为止。

后缀表达式的求解方法

简单而言就是从左到右扫描后缀表达式，遇到操作数就进栈，遇到运算符就出栈两个操作数进行计算，然后将结果进栈，直到栈中只有最后一个结果为止。

求后缀表达式时，栈中保存的是“还没有被更高层运算合并的中间结果”。例如 3 4 + 5 * 的过程是：3、4 入栈，遇到 + 后弹出两个数得到 7 再入栈；读到 5 入栈；遇到 * 后弹出 7 和 5 得到 35。后缀表达式把优先级已经编码进了顺序，所以求值阶段只需要机械地按栈规则执行。

一些注意事项

依次扫描表达式 expression 直到表达式结束，每次取一个符号。
很多程序员在写算术表达式时都习惯在运算符的前后插入一些空格，使表达式看上去更加清晰。这些空格对表达式的计算是没有意义的，在扫描过程中要忽略这些空格。
当遇到了一个有意义的语法单位时，需要判断是否遇到的是运算数，如果是运算数，则转换成整型数存入参数 value，返回符号 VALUE。如果不是运算数，则根据不同的运算符返回不同的 token 类型的值。