第 3.5 章：栈、队列与双端队列

3.5.0 从一道题出发：括号串是否合法

先看一道经典题（LeetCode 20 / USACO Bronze 风格）：

🧩 题目：合法括号串 给定一个由 (、)、[、]、{、} 组成的字符串 s（|s| ≤ 10⁶），判断它是否正确嵌套——每个闭括号都与最近的未匹配开括号类型一致。

"()[]{}"   → 合法
"([)]"     → 不合法（')' 的最近开括号是 '['）
"{[]}"     → 合法

先试试你会的方法

思路 1：计数？ 「左括号数 = 右括号数」远远不够——")(" 计数平衡却不合法，而且必须检查类型匹配。

思路 2：数组记录每个开括号的位置？ 可以，但遇到闭括号时，你需要知道最近那个还没配对的开括号是谁——数组从头找是 O(N²)，而且 ([)] 这种交错必须靠「最近的先配对」来排除。

关键观察： 括号匹配天然满足「后开的先关」——最新未匹配的开括号必须最先被闭合。这正是 后进先出（LIFO） 的顺序：开括号压入，闭括号弹出并检查。装这种顺序的容器就是栈。

改变「处理的顺序」，就得到不同容器、不同问题：

• 栈（Stack）： 后进先出（像一叠盘子）——括号匹配、DFS、撤销
• 队列（Queue）： 先进先出（像商店排队）——BFS、按到达顺序处理
• 双端队列（Deque）： 两端均可插入/删除——滑动窗口最大值

这三种数据结构控制的正是元素被处理的顺序——本章的主角。

3.5.1 栈深度解析

我们在第 3.1 章介绍过 stack，现在用它解决实际问题。

图示：栈的操作

上图通过逐步压入和弹出操作展示了 LIFO（后进先出）性质。注意 pop() 总是移除最近压入的元素——这正是栈在括号匹配、DFS 和撤销操作中无可替代的原因。

以下是三种容器的对比——访问模式决定了各自适合不同的问题：

括号匹配问题

题目： 给定括号字符串 ()[]{}, 判断是否正确嵌套。

数据规模： 1 ≤ 字符串长度 ≤ 10⁵。

#include <bits/stdc++.h>
using namespace std;

bool isBalanced(const string &s) {
    stack<char> st;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);   // 开括号：压栈
        } else {
            // 闭括号：必须与最近的开括号匹配
            if (st.empty()) return false;   // 没有对应的开括号

            char top = st.top();
            st.pop();

            // 检查是否匹配
            if (ch == ')' && top != '(') return false;
            if (ch == ']' && top != '[') return false;
            if (ch == '}' && top != '{') return false;
        }
    }

    return st.empty();  // 栈为空说明所有括号都匹配了
}

int main() {
    cout << isBalanced("()[]{}") << "\n";    // 1（真）
    cout << isBalanced("([]){}") << "\n";    // 1（真）
    cout << isBalanced("([)]")   << "\n";    // 0（假）
    cout << isBalanced("(()")    << "\n";    // 0（假——未匹配的 '('）
    return 0;
}

💡 进阶预告： 栈还有一种强大的变体——单调栈，能在 O(N) 内解决「下一个/上一个更大更小元素」这类问题；双端队列配合单调性可以 O(N) 求滑动窗口最值。这些内容统一放在第 3.6 章：单调栈与单调队列深入讲解，本章先掌握三种容器本身。

3.5.2 队列与 BFS 准备

队列的 FIFO 性质使它非常适合广度优先搜索（BFS），我们在第 5.2 章详细讲解。这里先聚焦队列本身及相关模式。

图示：队列操作

队列按到达顺序处理元素：队首元素始终最先出队，新元素从队尾加入。FIFO 性质保证 BFS 按层级访问节点，从而保证最短路径距离的正确性。

用队列模拟

题目： 游乐场过山车共有 N 组游客，每组人数为 size[i]，每次运行最多容纳 M 人。模拟需要多少次运行才能送完所有人。

数据规模： 1 ≤ N ≤ 10⁵，1 ≤ M ≤ 10⁹，1 ≤ size[i] ≤ M（保证每组都能坐下）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    queue<int> groups;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        groups.push(x);
    }

    int runs = 0;
    while (!groups.empty()) {
        int capacity = m;   // 本次运行的剩余容量
        runs++;

        while (!groups.empty() && groups.front() <= capacity) {
            capacity -= groups.front();  // 这组能坐下
            groups.pop();
        }
    }

    cout << runs << "\n";
    return 0;
}

3.5.3 双端队列——两端都能操作

deque（发音「deck」）支持 O(1) 的两端插入和删除。

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> dq;

    dq.push_back(1);    // [1]
    dq.push_back(2);    // [1, 2]
    dq.push_front(0);   // [0, 1, 2]
    dq.push_front(-1);  // [-1, 0, 1, 2]

    cout << dq.front() << "\n";  // -1
    cout << dq.back() << "\n";   // 2

    dq.pop_front();  // [-1 移除] → [0, 1, 2]
    dq.pop_back();   // [2 移除]  → [0, 1]

    cout << dq.front() << "\n";  // 0
    cout << dq.size() << "\n";   // 2

    // 随机访问（像向量一样）
    cout << dq[0] << "\n";  // 0
    cout << dq[1] << "\n";  // 1

    return 0;
}

⚠️ 第 3.5 章常见错误

本章总结

📌 核心要点

单调栈与单调双端队列（下一个更大元素、滑动窗口极值等）见第 3.6 章。

❓ 常见问题

Q1：什么时候用 stack vs deque？

A：只需要 LIFO（单端访问），用 stack；需要两端操作（如滑动窗口需要队首删除 + 队尾添加），用 deque。stack 内部其实是以 deque 实现的，只是把接口限制为只暴露顶部。

Q2：BFS 一定要用 queue 吗？能用 vector 吗？

A：技术上可以用 vector + 下标模拟，但 queue 更清晰不易出错。竞赛中直接用 queue。唯一例外是 0-1 BFS（边权只有 0 和 1 的最短路），需要用 deque。

Q3：括号匹配为什么必须用栈，数组不行吗？

A：闭括号必须与最近的未匹配开括号配对——「最近」意味着后进先出。数组从头找是 O(N²)，且交错嵌套（([)]）只有靠「最近的先配对」才能正确排除。

🔗 与后续章节的联系

• 第 5.2 章（图 BFS/DFS）：queue 是 BFS 的核心容器，stack 可用于迭代式 DFS
• 第 3.6 章（单调栈与单调队列）：把单调性约束加到本章的栈和双端队列上，得到 O(N) 解决「最近更大/更小元素」和「滑动窗口极值」的强大工具——USACO Silver 高频考点
• 第 3.4 章（双指针）：滑动窗口技术与本章的双端队列完美结合
• 第 6.1–6.3 章（DP）：某些优化技术（如 DP 的滑动窗口极值优化）直接使用单调双端队列

练习题

题目 3.5.1 — 循环队列 🟡 中等 实现大小为 K 的循环队列，处理 PUSH/POP 操作并检测 OVERFLOW/UNDERFLOW。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int K, Q; cin >> K >> Q;
    deque<int> q;
    while (Q--) {
        string op; cin >> op;
        if (op == "PUSH") {
            int x; cin >> x;
            if ((int)q.size() == K) cout << "OVERFLOW\n";
            else q.push_back(x);
        } else {
            if (q.empty()) cout << "UNDERFLOW\n";
            else { cout << q.front() << "\n"; q.pop_front(); }
        }
    }
}

复杂度： O(Q)。

题目 3.5.2 — 表达式求值 🟡 中等 计算只含整数和 +、- 运算符（无括号）的简单表达式。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string expr; cin >> expr;
    stack<long long> nums;
    long long cur = 0; bool neg = false;
    for (int i = 0; i < (int)expr.size(); i++) {
        if (isdigit(expr[i])) cur = cur*10 + (expr[i]-'0');
        else {
            nums.push(neg ? -cur : cur);
            cur = 0; neg = (expr[i] == '-');
        }
    }
    nums.push(neg ? -cur : cur);
    long long ans = 0;
    while (!nums.empty()) { ans += nums.top(); nums.pop(); }
    cout << ans << "\n";
}

题目 3.5.3 — 干草堆模拟 🟡 中等 N 堆干草，每天从最高的那堆取走一捆。D 天后打印剩余捆数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, D; cin >> n >> D;
    multiset<long long, greater<long long>> ms;
    for (int i = 0; i < n; i++) { long long x; cin >> x; ms.insert(x); }
    for (int d = 0; d < D && !ms.empty(); d++) {
        auto it = ms.begin();
        long long v = *it; ms.erase(it);
        if (v > 1) ms.insert(v-1);
    }
    long long rem = 0;
    for (long long x : ms) rem += x;
    cout << rem << "\n";
}