栈
栈（Stack）是一种后进先出的线性表，只能在一端（栈顶）进出。
它和链表一样都是线性表，区别在于：链表可以随意插入删除，栈只能"从顶上"操作。
一、栈的概念
1.1 什么是栈
栈：一种 限定性 的线性表——只能在一端(栈顶) 进行插入和删除。
| 术语 | 含义 |
|---|---|
| 栈顶（top） | 允许插入、删除的那一端 |
| 入栈（push） | 在栈顶放入一个元素 |
| 出栈（pop） | 从栈顶取走一个元素 |
1.2 核心规则：后进先出（LIFO）
LIFO（Last In First Out）：最后放进去的，最先被取出来。
栈顶 ↑（只能从这端进出）
┌───┐
│ 3 │ ← 最后进，最先出
│ 2 │
│ 1 │ ← 最先进，最后出
└───┘
按 1 → 2 → 3 的顺序入栈，出栈顺序就变成 3 → 2 → 1（反过来）。
💡 口诀：栈是"后进先出"，先进去的被压在底下，最后才能出来。
1.3 生活中的例子
| 例子 | 说明 |
|---|---|
| 一摞盘子 | 只能从最上面拿、最上面放 |
| 弹夹 | 后压入的子弹先射出 |
| 浏览器后退 | 最后访问的页面先返回 |
| 撤销操作 Ctrl+Z | 撤销最后一步操作 |
二、数组模拟栈
2.1 为什么用数组模拟
C++ 的 STL 有现成的 stack，但竞赛里更常用数组模拟——更快、更好控制、方便配合单调栈等技巧。
2.2 栈的结构
用一个数组 q[] 存元素，一个变量 top 标记栈顶位置。
const int N = 100005;
int q[N]; // 存栈里的元素
int top = 0; // 栈顶指针：top 就是元素个数，空栈时 top == 0
栈（下标从 1 开始用）：
q[1] q[2] q[3] q[4] ... ↓ ↓ ↓┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ │ │
└───┴───┴───┴───┴───┘
↑ top = 3（指向栈顶元素 q[3]）
约定：
top指向栈顶元素，所以top的值就是元素个数；空栈时top == 0。
2.3 基本操作
q[++top] = x; // 入栈：top 先加 1，再把 x 放进 q[top]
q[top]; // 栈顶元素
top--; // 出栈：top 减 1，原栈顶就被"丢弃"了
top == 0; // 判空：top 为 0 就是空栈
while (top) cout << q[top--] << " "; // 清空栈（从栈顶到栈底输出）
💡 记住这五句：
- 入栈
q[++top] = x（先++再赋值）- 栈顶
q[top]- 出栈
top--- 元素数量
top- 空栈
top == 0- 清空
while (top) cout << q[top--] << " ";
2.4 用 STL 的 stack（对比）
#include <stack>
stack<int> st;
st.push(x); // 入栈
st.pop(); // 出栈（注意：不返回值）
st.top(); // 取栈顶（不弹出）
st.size(); // 元素数量
st.empty(); // 判空
st.size(); // 元素个数
💡 竞赛里数组模拟栈更常用
三、栈解决的问题概括
栈"后进先出"的特性，天然适合下面几类问题：
| 场景 | 为什么用栈 |
|---|---|
| 括号匹配 | 左括号入栈，右括号和栈顶配对 |
| 表达式求值 | 存操作数，按优先级计算 |
| 函数调用 / 递归 | 系统底层用栈保存返回地址 |
| 回溯 / DFS | 走不通时回退到上一步（栈顶） |
| 单调栈 | 快速找每个元素左右第一个比它大/小的数 |
💡 一句话判断"该不该用栈"：如果问题的处理顺序是"后进先出"（先处理最近发生的），就可以考虑栈。
四、前中后缀表达式 ——计算机如何解决数学算式问题
4.1 概念介绍
按运算符的位置，表达式分三种：
| 名称 | 别称 | 形式 | 例子（中缀 a + b） |
|---|---|---|---|
| 前缀表达式 | 波兰式 | 运算符在前 | + a b |
| 中缀表达式 | 普通写法 | 运算符在中间 | a + b |
| 后缀表达式 | 逆波兰式 | 运算符在后 | a b + |
- 中缀：我们习惯的写法，但要靠括号 + 优先级才能确定运算顺序，计算机不好直接算。
- 前缀 / 后缀：不需要括号，运算顺序由位置唯一确定，计算机用栈就能直接算。
4.2 栈求后缀表达式的值
规则（从左往右扫）：
- 遇到操作数 → 入栈；
- 遇到运算符 → 弹出两个操作数，先弹的是右操作数，后弹的是左操作数，运算后把结果入栈；
- 扫完，栈里剩下的就是结果。
例：求 3 4 2 * + 5 -
读 3 入栈 栈：3
读 4 入栈 栈：3 4
读 2 入栈 栈：3 4 2
读 * 弹 2、4 4 * 2 = 8 栈：3 8
读 + 弹 8、3 3 + 8 = 11 栈：11
读 5 入栈 栈：11 5
读 - 弹 5、11 11 - 5 = 6 栈：6
结果 = 6
⚠️ 减法和除法顺序要注意：
a b -表示a - b。弹栈时先弹出来的是 b（右操作数），别算反了。
4.3 栈求前缀表达式的值
规则（从右往左扫）：
- 遇到操作数 → 入栈；
- 遇到运算符 → 弹出两个操作数，先弹的是左操作数，后弹的是右操作数，运算后把结果入栈。
例：求 - + 3 * 4 2 5
读 5 入栈 栈：5
读 2 入栈 栈：5 2
读 4 入栈 栈：5 2 4
读 * 弹 4、2 4 * 2 = 8 栈：5 8
读 3 入栈 栈：5 8 3
读 + 弹 3、8 3 + 8 = 11 栈：5 11
读 - 弹 11、5 11 - 5 = 6 栈：6
结果 = 6
💡 记牢两个方向：
- 后缀：从左往右扫，先弹的是右操作数；
- 前缀：从右往左扫，先弹的是左操作数。
4.4 中缀转前后缀：加括号法
（1）中缀 → 后缀
步骤：
- 按优先级给中缀表达式加满括号；
- 把每个运算符移到它对应的右括号外面；
- 去掉所有括号。
例：a + b * c
① 加满括号： (a + (b * c))
② 运算符移到右括号后： (a + (b * c)) → a (b c * ) +
③ 去掉括号： a b c * +
结果：a b c * +
（2）中缀 → 前缀
步骤：
- 加满括号；
- 运算符移到左括号外面；
- 去掉括号。
例：a + b * c
① 加满括号： (a + (b * c))
② 运算符移到左括号前： (a + (b * c)) → + a * b c
③ 去掉括号： + a * b c
结果：+ a * b c
（3）综合例子
中缀：(a + b) * c - d
加满括号： (((a + b) * c) - d)
转后缀（运算符移右括号后）： a b + c * d -
转前缀（运算符移左括号前）： - * + a b c d
💡 加括号法核心：先按优先级加满括号，再把运算符挪到括号外，最后去括号。后缀挪到"右括号后"，前缀挪到"左括号前"。
4.5 前后缀转回中缀
转中缀是"加括号法"的逆过程：看到运算符，就把它的两个操作数用括号括起来。笔试手算即可，不需要栈。
（1）后缀 → 中缀
从左往右看，遇到运算符，把它和前面两个操作数括起来。
例：a b + c * d -
① 扫到 + ，前面两个是 a、b → 括成 (a + b) 式子变成：(a+b) c * d -
② 扫到 * ，前面两个是 (a+b)、c → 括成 ((a+b) * c) 式子变成：((a+b)*c) d -
③ 扫到 - ，前面两个是 ((a+b)*c)、d → 括成 (((a+b)*c) - d)
结果：(a + b) * c - d
（2）前缀 → 中缀
从右往左看，遇到运算符，把它和后面两个操作数括起来。
例：- * + a b c d
① 从右往左，扫到 + ，后面两个是 a、b → (a + b)
式子变成：- * (a+b) c d
② 扫到 * ，后面两个是 (a+b)、c → ((a+b) * c)
式子变成：- ((a+b)*c) d
③ 扫到 - ，后面两个是 ((a+b)*c)、d → (((a+b)*c) - d)
结果：(a + b) * c - d