栈

一句话算法

栈只在同一端进出元素，最后放进去的元素最先被取出来。

问题模型

我们需要维护一段线性数据，并支持这些操作：

• 在栈顶加入一个元素。
• 删除栈顶元素。
• 查询当前栈顶元素。
• 判断栈是否为空。

栈的关键限制是：只能操作栈顶，不能直接访问中间元素。

核心直觉

把栈想成一摞盘子。

新盘子只能放在最上面，拿盘子也只能先拿最上面那一个。所以栈天然适合处理“后出现的东西要先解决”的问题，例如括号匹配、递归调用、后缀表达式求值。

算法步骤

用数组实现栈时，维护一个变量 top_pos：

• top_pos 表示栈顶元素后面的第一个空位置。
• 当前栈内元素区间是 [0, top_pos)。
• 入栈时先写入 sta[top_pos]，再让 top_pos++。
• 出栈时让 top_pos--。
• 栈顶元素是 sta[top_pos - 1]。

这种写法把空栈自然表示为 top_pos == 0，不需要特殊处理 -1 下标。

算法证明

关键不变量： 数组区间 [0, top_pos) 存放当前栈内元素，并且 sta[top_pos - 1] 是栈顶。

1. 初始时 top_pos = 0，区间为空，表示空栈，不变量成立。
2. 入栈 x 时，把 x 放到 sta[top_pos]，再移动到下一个空位。新元素处在所有旧元素之后，所以它成为新的栈顶。
3. 出栈时只删除 sta[top_pos - 1] 这个最后加入的元素，剩下的区间仍然是 [0, top_pos)。

因此每次操作后都保持“最后加入的元素在栈顶”，栈满足后进先出。

复杂度分析

• 入栈、出栈、查询栈顶、判断空栈：$O(1)$。
• 空间复杂度：$O(n)$，其中 $n$ 是栈容量。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

        const int maxn = 100000 + 5;

template <typename T = int, int siz = maxn>
struct MyStack {
    T sta[siz + 5];
    int top_pos = 0;  // 指向栈顶元素后面的一个位置

    void clear() { top_pos = 0; }

    void push(const T& x) { sta[top_pos++] = x; }

    void pop() { --top_pos; }

    T& top() { return sta[top_pos - 1]; }

    const T& top() const { return sta[top_pos - 1]; }

    bool empty() const { return top_pos == 0; }

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

测试用例

输入一组操作：

push 3
push 5
top
pop
top

执行过程：

应用分类详解

栈的本质是维护“最近还没有被解决的对象”。

一、匹配与消除

典型模式： 题目中有成对符号、相邻抵消、最近元素配对。

识别信号： 括号匹配、相邻重复删除、碰撞、撤销最近操作。

核心建模： 遇到新的待匹配对象就入栈，遇到能和栈顶配对的对象就弹栈。

二、表达式求值

典型模式： 题目要求计算中缀、后缀或前缀表达式。

识别信号： 运算符优先级、括号、逆波兰表达式。

核心建模： 数字栈保存待计算值，符号栈保存暂时不能计算的运算符。

三、递归与搜索状态

典型模式： 过程总是先处理最新展开的分支。

识别信号： DFS、回溯、函数调用、撤销现场。

核心建模： 每个栈元素表示一个尚未完成的状态，弹出后继续展开它。

经典例题

• leetcodecn-20 有效的括号：最直接的匹配模型。
• luogu-P1449 后缀表达式：练习“遇到运算符就结算”的栈模型。
• luogu-P4387 验证栈序列：考察能否把抽象的进出栈顺序转成模拟。

参考

• 本书相关章节：表达式求值