栈(stack) 知识点讲解

🎯 先搞清楚它是什么

📌 考纲要求（NOI 大纲 · 数据结构基础 / 参考《cspNOI级大纲解读》）：考纲将栈列为线性结构的基本操作之一，在算法实现中常以“入栈 / 出栈 / 取栈顶”的形式出现，例如原文描述虚树构建时写道“将根结点入栈……弹出栈顶结点，直到栈为空为止”。本讲对齐“栈(stack)”这一考点：理解后进先出（LIFO）的特性，并能用数组或 STL stack 模拟进出栈过程。

栈（stack） 是一种“后进先出（LIFO, Last In First Out）”的线性结构。想象一摞盘子：你只能从最上面拿（取栈顶），也只能往最上面放（压栈），底下的是碰不到的。

支持三个核心动作：

• push（压栈）：把元素放到栈顶；
• pop（出栈）：把栈顶元素拿走；
• top（看栈顶）：看一眼栈顶是谁，但不拿走。

⚠️ 一句话区分：队列是“排队买票”（先进先出），栈是“叠盘子”（后进先出）。看到“撤销 / 配对 / 最近关系 / 嵌套”这类词，先想栈。

🧩 关键规则与结论

手写数组栈（最稳、最常考）：

int st[100005], top = 0;     // top 表示栈里元素个数（栈顶在 st[top-1]）
st[top++] = x;               // push：先放再 top++
int v = st[--top];           // pop：先 top-- 再取
int t = st[top - 1];         // top()：看栈顶不弹出
bool empty = (top == 0);     // 判空

STL 写法：

#include <stack>
stack<int> s;
s.push(x);          // 压栈
int t = s.top();    // 看栈顶
s.pop();            // 出栈（注意：pop 不返回值，要先 top 再 pop）
bool e = s.empty();

三条铁律：

1. pop / top 前必须判空，空栈访问会 RE；

2. STL 的 pop() 没有返回值，要取值得先 top()；

3. 进出只能在一端，所以“先压进去的后出来”。

🗺️ 知识用法地图

🔬 推演：为什么这些写法是对的（以及它们能用来干什么）

推演 1 · 为什么栈是“后进先出”

栈只在同一端操作：压栈把元素放在 top 位置，出栈也从 top 取。所以最后压进去的元素恰好在最上面，第一个被取走——这就是 LIFO。用数组实现时，top 始终指向“下一个可放位置”，st[top-1] 永远是当前最新的元素。

📌 用法：凡是“最近放进去的要先用”（如撤销操作、函数调用），栈天然合适——系统函数调用栈就是这个原理。

推演 2 · 为什么括号匹配用栈

括号要“最晚开的左括号，最先被右括号配对”（就近配对），这正好是栈的 LIFO：遇到左括号压栈；遇到右括号，它该和栈顶那个左括号配对。二者类型相同就弹栈，否则不合法。遍历完栈空 → 全部配对成功。

📌 用法：把“左”压栈、“右”弹栈比对，这是所有配对题（括号、HTML 标签、消消乐）的统一模板。

推演 3 · 出栈前为什么要判空

如果栈已经空了（top==0），st[top-1] 访问的是 st[-1]，越界 → RE。所以每次 pop/top 前都先 if (!empty)。验证栈序列题里，弹出时若栈空却还要弹，说明该序列不可能由合法进出栈得到。

📌 用法：任何“弹栈”动作前都加空判断，这是竞赛里栈题 RE 的头号原因。

🔧 编程题里怎么考、怎么用？

① 它在编程题里长什么样（考法总览）

② 识别信号清单：看到什么该想到栈

• “括号 / 标签 / 配对 / 对称” → 括号匹配模板；
• “计算器 / 表达式 / 中缀后缀” → 表达式求值；
• “撤销 / 回退 / 最近一次操作” → 栈；
• “合法序列 / 能否由某种进出规则得到” → 模拟栈；
• “每个元素找左边/右边第一个比它大/小的” → 单调栈（进阶）。

判断步骤：

① 是不是只在“一端”进出？→ 栈
② 是不是“配对”问题？→ 左压右弹
③ 是不是“合法顺序”问题？→ 模拟进出栈

③ 必背模板：括号匹配

bool ok(string s) {
    int top = 0; char st[1005];
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st[top++] = c;   // ⭐ 左括号压栈
        else {
            if (top == 0) return false;                         // ⭐ 空栈却遇到右括号 → 不合法
            char l = st[--top];                                 // ⭐ 弹出栈顶左括号
            if ((c == ')' && l != '(') || (c == ']' && l != '[') || (c == '}' && l != '{'))
                return false;
        }
    }
    return top == 0;   // ⭐ 全配对完栈必须空
}

④ 必背模板：验证栈序列（出栈顺序是否合法）

// 给定入栈序列 1..n 与出栈序列 out[]，判断是否可能
int st[1005], top = 0, j = 0;
for (int x = 1; x <= n; x++) {
    st[top++] = x;                       // ⭐ 依次入栈
    while (top && st[top-1] == out[j]) { top--; j++; }  // ⭐ 能弹就弹（匹配出栈序列）
}
return top == 0;                         // ⭐ 栈空说明全部合法弹出

⑤ 思路点拨：拿到题第一步想什么

1. 确认是“一端进出”还是“两端进出”——一端用栈，两端（队头队尾）用队列；

2. 配对题先想“左压右弹”，再想怎么判类型；

3. 表达式题先转后缀（数字直接输出，运算符按优先级压栈），再用运算栈算；

4. 弹栈前必判空，否则 RE；

5. 单调栈进阶：维护栈内单调性，遇到破坏顺序的就弹，是解决“第一个更大/更小”的利器。

📚 更多同类真题（来自真题库，点击展开）

🔍 看一个例子

例：判断括号串是否合法（P1241 思路）。

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s; cin >> s;
    char st[10005]; int top = 0;
    for (char c : s) {
        if (c == '(' || c == '[') st[top++] = c;        // 左括号压栈
        else {
            if (top == 0) { cout << "No\n"; return 0; } // 没左括号配 → 非法
            char l = st[--top];
            if ((c == ')' && l != '(') || (c == ']' && l != '[')) {
                cout << "No\n"; return 0;               // 类型不匹配 → 非法
            }
        }
    }
    cout << (top == 0 ? "Yes\n" : "No\n");              // 栈空才算全配对
    return 0;
}

下面对照一张图理解“后进先出”：

🪤 常见错误

1. 空栈弹栈/取栈顶：top 为 0 时 st[top-1] 越界 RE。务必先判 top>0。

2. STL pop() 当返回值用：int x = s.pop(); 是错的，pop 返回 void，要先 s.top() 再 s.pop()。

3. 下标写错：手写栈时 push 是 st[top++]=x（先放后加），pop 是 x=st[--top]（先减再取）；把顺序写反会丢元素或重复。

4. 忘记最后判栈空：括号匹配遍历完还要 return top==0，漏了会放过“左括号多出来”的非法串。

5. 类型不匹配：右括号要和栈顶左括号比，别和“任意一个”比。

6. 验证序列题在不能弹时还硬弹：应是 while(能弹就弹)，不是“必须弹”。

✅ 自测

1. 栈和队列最核心的区别是什么？各举一个生活例子。

2. 手写栈时，push 和 pop 的下标操作分别怎么写？为什么顺序很重要？

3. 为什么括号匹配用栈最自然？“就近配对”和 LIFO 有什么关系？

4. 用 STL 的 stack 取值，为什么不能写 int x = s.pop();？

5. 验证栈序列题里，为什么要“能弹就弹（while）”而不是“遇到就弹（if）”？

6. 栈空时调用 top() 或 pop() 会发生什么？怎么避免？

7. 表达式 3 + 4 * 2 如果转成后缀表达式是什么？用栈怎么算？

这个模型讲什么

栈的核心性质是“后进先出（LIFO）”：只能在栈顶一端压入和弹出。底层可以用数组模拟，也可以用 STL 的 stack。

// 手写数组栈
int st[100005], top = 0;
st[top++] = x;          // push：放到 top 位置，top 再 +1
int v = st[--top];      // pop：top 先 -1，再取栈顶
int t = st[top - 1];    // top()：只看栈顶不弹出
bool empty = (top == 0);

// STL 栈
#include <stack>
stack<int> s;
s.push(x);          // 压栈
int t = s.top();    // 看栈顶（不弹出）
s.pop();            // 出栈（无返回值！）

做题时怎么用

关键概念：

• 栈顶：唯一能操作的位置，top 指针指向“下一个空位”；
• 判空：任何 pop / top 前都要 if (top > 0) 或 !s.empty()，否则 RE；
• 与递归同源：函数调用本身就是系统帮你维护的栈（DFS 同理）。

易错：STL 的 pop() 不返回值，要先 top() 再 pop()；手写栈的 push/pop 下标顺序写反会丢数据。

练这几道（从易到难）

P1044 栈（进出栈方案数）→ P1996 约瑟夫问题（环形报数模拟）→ P1449 后缀表达式（运算符栈）。

这个模型讲什么

栈真正的价值在应用：把“配对、就近、撤销、合法顺序”类问题转化成进出栈操作。

① 括号匹配（最经典）：左括号压栈，右括号与栈顶左括号比对，类型相同就弹栈，最后栈空即合法。

for (char c : s) {
    if (c=='('||c=='[') st[top++]=c;
    else { if(top==0) return false; char l=st[--top];
           if((c==')'&&l!='(')||(c==']'&&l!='[')) return false; }
}
return top==0;

② 后缀表达式求值：遇到数字压栈；遇到运算符，弹出栈顶两个数运算，结果再压回。

if (isdigit(c)) st[top++] = c - '0';
else { int b = st[--top], a = st[--top];    // ⭐ 注意先弹的是右操作数
       st[top++] = cal(a, b, c); }

③ 验证栈序列：依次把 1..n 入栈，只要栈顶等于当前期望出栈值就弹出，最后栈空即合法。

关键提醒

• 配对题就近原则天然匹配 LIFO：左压右弹；
• 后缀表达式里先弹出的是右操作数（运算 a 运算符 b）；
• 验证序列用 while(能弹就弹)，不是 if——可能连续弹出多个。

练这几道（从易到难）

P1241 括号序列（配对）→ P1449 后缀表达式（运算栈）→ P4387 验证栈序列（深基模板）。