什么是栈？

我们先回顾一下我们对于队列的学习。我们对于队列的理解，是一个队伍，在队尾进入，先进先出。
那么我们应该通过什么来理解栈呢？
你可以想象一堆叠在一起的书构成“书塔”，由下往上叠放。每次放书都放在最上面那层书的上面，如果你想取书，由于书的重力你很难从“书塔”的中间取出来书，所以你只能从这一叠书的最上面取书。所以我们每次取书都是取得最上面得一本。你可以理解为一个单头的队列，只有队首，插入元素和删除元素都是针对队首进行的。
这种性质使得栈中先插入的元素会在后插入元素的“下方”,但是出栈是从所谓“上面”出栈，所以这就使得先插入的元素的出栈顺序在后插入的元素之后，所以栈具有先进后出的性质。

栈的代码实现

1
2
3

const int MAXN = 10000007;
int stk[MAXN];
int p; //栈中元素个数，也是下一次插入的位置

不难理解，依然类似于队列，我们通过数组和指针实现栈。这里的MAXN指的是栈最大支持的大小;
接下来是操作代码的实现

void push(int x) {
    if (p >= MAXN) cout << "Stack overflow（栈溢出）\n";
    else stk[p++] = x;
}

void pop() {
    if (p == 0) cout << "Stack is empty（栈为空）\n";
    else p--;
}

你可以把下一次插入的位置理解为 stk[p]。弹出时执行 p–，下一次插入就会覆盖原来的栈顶位置。
比如栈中依次放入 3 5 1 7，此时 $p=4$。弹出一次后 $p=3$，原来的 stk[3] 不再属于有效区间；下一次插入会直接覆盖它。
所以这就是为什么MAXN在队列中表示最大插入次数，因为他的元素没有经过实际意义上数组中的删除，只是滚动过去实现队列的模拟。
但在栈中是实际上通过删除来实现的，所以在栈中MAXN指的是栈的大小。

接着给出访问栈顶的代码

int top() {
    if (p == 0) {
        cout << "Stack is empty（栈为空）\n";
        return -1; //指的是栈为空这个概念
    }
    return stk[p - 1];
}

这样我们就实现了栈的基本操作。和队列一样，栈也有对应的STL中的栈，接下来给出通过STL操作的栈的用法。

#include <stack>    // 栈所需要的头文件
stack<int> s;      // 建立一个内部元素类型为 int 的栈
s.push(x);         // 将 x 压入栈
s.pop();           // 弹出栈顶元素
s.top();           // 访问栈顶元素
s.size();          // 查询元素个数
s.empty();         // 查询栈是否为空

总结与常见问题

常见问题

为什么 p 同时能表示栈的大小？ 有效元素存放在下标 $[0,p-1]$ 中，因此恰好有 $p$ 个元素。
弹出后为什么不用清空原位置？ 只要把有效区间缩短，原位置就已经不可访问；下一次入栈还会覆盖它。
调用 STL 的 top 或 pop 前要注意什么？ 必须先判断栈非空，否则行为未定义。
栈适合处理什么问题？ 只关心最近加入状态的问题，例如括号匹配、表达式求值、DFS、撤销操作和单调栈。

复杂度分析

入栈、出栈、访问栈顶：时间复杂度均为 $O(1)$。
查询元素个数和判空：时间复杂度均为 $O(1)$。
数组模拟栈与 STL 栈：空间复杂度均为 $O(n)$。

栈（stack）

什么是栈？

栈的代码实现

总结与常见问题

常见问题

复杂度分析

系列文章