08 栈与队列应用

GESP 6 级CSP-J 高频

级别标注：GESP 6 级（考级要求）/ CSP-J 高频（竞赛进阶：单调栈、单调队列、表达式求值）。

一、栈（Stack）：后进先出 LIFO

只允许在一端（栈顶）插入与删除。可用数组模拟或 std::stack。

数组模拟栈（理解原理，掌握手写）

C++ 实例

#include <iostream>
using namespace std;
const int N = 100005;
int st[N], top = -1;      // 用数组模拟栈：top 指向栈顶下标，-1 表示空

void push(int x) { st[++top] = x; }   // 入栈：top 先 +1 再写入
void pop() { if (top >= 0) top--; }   // 出栈：top -1 即"逻辑删除"
int peek() { return st[top]; }        // 取栈顶：只看不弹
bool empty() { return top == -1; }    // 判空

int main() {
    push(1); push(2); push(3);
    cout << peek() << endl;   // 3（后进先出）
    pop();
    cout << peek() << endl;   // 2
    return 0;
}

形象理解栈像一摞书：最后放上去的书最先被拿走。数组模拟时 top 是“最高那本书的编号”，top = -1 表示一本书都没有。

易错点数组模拟栈要统一约定：top = -1 起步配 st[++top]；top = 0 起步配 st[top++]。两种写法都行，但混用必错。访问栈顶前先判空。

二、栈经典应用：括号匹配

C++ 实例

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 括号匹配：用栈记录"最近未匹配的左括号"
bool check(const string &s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);              // 左括号入栈
        } else {                     // 遇到右括号
            if (st.empty()) return false;         // 右括号多余 → 不合法
            char top = st.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) return false;  // 类型不匹配
            st.pop();                // 匹配成功，弹出
        }
    }
    return st.empty();   // 最后栈必须为空（没有未匹配的左括号）
}
int main() {
    cout << check("(()[{}])") << endl;   // 1 合法
    cout << check("([)]") << endl;       // 0 交叉嵌套不合法
    cout << check("(())(") << endl;      // 0 左括号多余
    return 0;
}

形象理解括号匹配像检查书包拉链：遇到左括号就像“拉开一层”压栈，遇到右括号就像“拉回一层”弹栈。最后拉链全部拉好（栈空）才叫匹配。

易错点三种括号嵌套时，不仅数量要配对，类型也要匹配：([)] 数量对但类型错，必须判 false。右括号到来时栈已空 = 右括号多余，同样 false。

三、栈经典应用：表达式求值

后缀表达式（逆波兰）求值：数字入栈，遇到运算符取栈顶两个数运算后压回。

C++ 实例

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
// 后缀表达式求值，如输入 "3 4 + 5 *"，输出 35
// 规则：遇到数字入栈，遇到运算符弹两个数运算后结果入栈
int main() {
    string tok;
    stack<int> st;
    while (cin >> tok) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            int b = st.top(); st.pop();   // 注意顺序：先弹的是右操作数 b
            int a = st.top(); st.pop();   // 再弹左操作数 a
            int r;
            if (tok == "+") r = a + b;
            else if (tok == "-") r = a - b;   // 是 a-b 不是 b-a
            else if (tok == "*") r = a * b;
            else r = a / b;
            st.push(r);               // 结果压回栈
        } else {
            st.push(stoi(tok));       // 数字字符串转 int 入栈
        }
    }
    cout << st.top() << endl;         // 栈底最后只剩结果
    return 0;
}

中缀转后缀（用栈处理运算符优先级）是进阶考点，考级一般只要求后缀求值或直接模拟。另一经典应用：表达式括号层数/计算器。

形象理解后缀表达式像按菜谱一步步操作：看到数字先“备料入锅”（入栈），看到运算符就“取两份料翻炒”（弹两个数运算再压回）。

易错点减法和除法操作数顺序很关键：先弹出的是右操作数 b，再弹出的是左操作数 a，必须算 a - b、a / b，写反结果全错。

四、单调栈（竞赛进阶，O(n)）

维护栈内元素单调（递增或递减），常用于"找每个元素左边/右边第一个比它大/小的元素"。

C++ 实例

// 单调栈应用：求每个元素右边第一个比它大的元素下标（没有则 -1）
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    int a[] = {2, 1, 4, 3, 5};
    int n = 5;
    vector<int> ans(n, -1);
    stack<int> st;               // 存下标，栈内对应的值保持递减
    for (int i = n - 1; i >= 0; i--) {   // 从右往左扫
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();  // 弹出不够大的
        if (!st.empty()) ans[i] = st.top();  // 栈顶就是右边第一个更大的
        st.push(i);              // 当前下标入栈
    }
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << endl;                // 2 2 4 4 -1
    return 0;
}

形象理解单调栈像叠盘子时只留越来越大的盘子：新盘子比栈顶大就压上，比栈顶小就把栈顶“挤掉”（pop），保证栈内单调。这样每个元素入栈出栈各一次，总复杂度 O(n)。

考级视角“右边第一个比它大的元素”是 CSP-J 提高组经典模板题。核心口诀：从右往左扫，弹掉所有不比它大的，栈顶就是答案。练熟这一题能迁移到矩形最大面积、接雨水等题。

五、队列（Queue）：先进先出 FIFO

数组模拟队列（循环队列）

C++ 实例

#include <iostream>
using namespace std;
const int N = 100005;
int q[N], head = 0, tail = 0;    // 数组模拟队列：[head, tail) 左闭右开

void enqueue(int x) { q[tail++] = x; }  // 入队：tail 位置写入并后移
int dequeue() { return q[head++]; }     // 出队：取 head 并后移
bool empty() { return head == tail; }   // 头尾相遇即为空

int main() {
    enqueue(1); enqueue(2); enqueue(3);
    cout << dequeue() << endl;   // 1（先进先出）
    cout << dequeue() << endl;   // 2
    cout << dequeue() << endl;   // 3
    cout << "空? " << empty() << endl;
    return 0;
}

形象理解队列像火车站安检通道：先到的旅客先安检通过。数组模拟用 head、tail 两个指针夹住“正在排队的区间”。

易错点普通数组模拟队列有“假溢出”：head 一直往后走，前面的空间浪费了。工程上用循环队列回绕，竞赛简单场景直接用 STL queue 更省心。

六、队列经典应用：约瑟夫环

C++ 实例

// 约瑟夫环：n 个人围一圈报数，报到 m 的人出列，输出出列顺序
#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;               // 如 n=5, m=3
    queue<int> q;                // 队列模拟围成一圈的人
    for (int i = 1; i <= n; i++) q.push(i);
    while (!q.empty()) {
        for (int i = 1; i < m; i++) {   // 前 m-1 个人：从队首移到队尾
            q.push(q.front());          // 相当于"继续报数但不淘汰"
            q.pop();
        }
        cout << q.front() << " ";       // 第 m 个人出列
        q.pop();
    }
    cout << endl;
    return 0;
}

形象理解约瑟夫环像击鼓传花：鼓声停（报到 m）时花在谁手里谁出局。队列模拟就是“把花往前传 m-1 次，每次都把队首挪到队尾”。

考级视角GESP 6 级常考约瑟夫环手推过程（如 n=5, m=2 的出列顺序）。先用纸笔推一遍，再对照代码验证，理解“报数-出列-继续”的循环。

七、单调队列 / 滑动窗口（竞赛进阶）

求每个长度为 k 的窗口内的最大值，用单调递减队列 O(n)。

C++ 实例

// 滑动窗口最大值：输出每个长度为 k 的窗口内的最大值
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main() {
    int a[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = 8, k = 3;
    vector<int> ans;
    deque<int> dq;               // 存下标，对应值单调递减（队首永远是窗口最大）
    for (int i = 0; i < n; i++) {
        // 1) 队尾弹出所有 <= a[i] 的下标（它们不可能再是最大值）
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);         // 2) 当前下标入队
        // 3) 队首若已滑出窗口左边界则弹出
        if (dq.front() <= i - k) dq.pop_front();
        // 4) 窗口凑满 k 个时记录答案
        if (i >= k - 1) ans.push_back(a[dq.front()]);
    }
    for (int x : ans) cout << x << " ";   // 3 3 5 5 6 7
    cout << endl;
    return 0;
}

形象理解滑动窗口像列车窗外的风景：窗口每前进一格，右边进一个新元素、左边出一个旧元素。单调队列保证队首永远是当前窗口的最大值。

易错点三步顺序别乱：① 弹掉队尾不比新元素大的（维护单调）；② 新元素入队；③ 弹出窗口外的队首（dq.front() <= i - k）。漏掉第③步，窗口外的大值会一直“赖”在队首。

八、易错点 / 常见坑点

⚠️ 弹出/访问前必须先判空 !st.empty()，否则访问空栈顶是未定义行为。
⚠️ 数组模拟栈 top 的初始值与增减时机要统一（-1 起步 vs 0 起步）。
⚠️ 循环队列要预留空间、注意 head/tail 回绕（简单场景用 STL 更省心）。
⚠️ 表达式求值中减法和除法要注意左右顺序（先弹的是右操作数）。
⚠️ 单调栈/队列里存下标而非值，便于判断窗口边界。
⚠️ while(cin >> tok) 迭代器/流式读入结束条件：文件末尾或输入非数字。
⚠️ 栈递归深度的"爆栈"风险；队列 BFS 的入队去重要防重复入队。

九、考级要求 vs 竞赛进阶

考级要求（GESP 6 级）：栈与队列的原理理解 + 数组模拟/代码填空、括号匹配、后缀表达式求值、约瑟夫环。
竞赛进阶（CSP-J/NOIP）：单调栈/单调队列O(n) 优化、表达式树、中缀转后缀、滑动窗口最值；理解"栈=递归的底层实现"。

十、课内练习建议

手写栈和队列各做 5 次插入删除，验证正确性。
括号匹配升级：允许三种括号并带嵌套。
用栈实现"简单计算器"（中缀表达式含 + - * / 和括号）。
手写滑动窗口最大值（单调队列）。
用队列解约瑟夫环并手推 n=5, m=2 过程。