栈（Stack）

🧩 子任务 1：LIFO——预测"谁先出"

规则只有一条：pop 永远弹出当前栈顶。跟着下面的操作，在纸上画便当盒，预测输出：

// 初始：栈空
push 1
push 2
push 3
pop   // → 输出 ?
pop   // → 输出 ?
push 4
pop   // → 输出 ?

自己先推一遍，再对答案。

🧩 子任务 2：数组实现栈——top 指针与四操作

用数组存栈，只需要一个变量 top 记住"栈顶在第几格"：

• push(x)：top 先加 1，再存 a[top] = x。像"把便当盒放上最顶"。
• pop()：先拿走 a[top]，再 top 减 1。
• top()（看栈顶）：直接读 a[top]，不拿走。
• empty()：top == -1 说明一个都没有。

注意：栈底永远在 a[0]，数组不用搬，每次只改 top 这个数字——所以 push、pop 都是 O(1)，飞快。

// 数组实现栈（top = 栈顶元素的下标；top == -1 表示空）
int a[100];
int top = -1;

// 入栈：顶 +1，再放
void push(int x) { a[++top] = x; }

// 出栈：拿走，顶 -1
int pop() { return a[top--]; }

// 看栈顶（不拿走）
int topVal() { return a[top]; }

// 判空
bool empty() { return top == -1; }

手推一遍下面的操作，每步写下 top 和数组：

push 10
push 20
pop        // 输出 ?
topVal()   // 得到 ?

🧩 子任务 3：应用①——括号匹配

看一段代码里的括号：(a + (b * c))——每个 ( 都要找到"自己那个" )。为什么正好用栈？因为最后打开的括号，必须最先关上——这就是 LIFO！

算法三步走：

• 遇到 (：压栈（记一笔"有个括号还没关"）。
• 遇到 )：栈空 → 失败（没开的括号先关了）；否则 弹一个（配上一对）。
• 走完：栈空 → 成功；栈不空 → 失败（还有括号没关）。

// 括号匹配
#include <iostream>
using namespace std;

bool match(string s) {
    int st[100], top = -1;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') top++;              // 压栈
        else if (s[i] == ')') {
            if (top == -1) return false;     // 没有可配的
            top--;                           // 弹一个，配一对
        }
    }
    return top == -1;                        // 最后必须全配完
}

🧩 子任务 4：应用②——用栈算"逆波兰式"

平常我们写 3 + 4（运算符在中间）。如果把运算符挪到最后：3 4 + 就表示 3+4。这叫逆波兰式（后缀式）。妙处：不需要括号、不需要优先级——从左往右读，见到运算符，它前面的两个数就是它的操作数。

用栈算它，规则只有两条：

• 遇到数字：压栈（"先存着，等运算符来"）。
• 遇到运算符：弹两个数——先弹的是右操作数，后弹的是左操作数（注意顺序！），算完把结果压回去。

为什么弹的顺序是"先右后左"？因为减和除不满足交换律：栈顶是最后来的数，它正好是运算符右边的数。

手推一道：5 1 2 + 4 * + 3 -（它 = (5 + (1+2)×4) − 3）。