📖 第 3.6 章 ⏱️ 约 50 分钟 🎯 中级

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

📝 前置条件： 了解基本的 C++ 数组和循环（第 2.1–2.2 章）。无进阶前提——这些是竞赛编程中随处可见的基础构件。

这三种数据结构控制着元素被处理的顺序。各自独特的「个性」使它们在特定类型的问题中表现出色。

  • 栈（Stack）： 后进先出（像一叠盘子）
  • 队列（Queue）： 先进先出（像商店排队）
  • 双端队列（Deque）： 两端均可插入/删除

3.6.1 栈深度解析

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

图示：栈的操作

Stack Operations

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

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

Stack vs Queue vs Deque

括号匹配问题

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

📄 C++ 完整代码 
#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;
}

下一个更大元素

题目： 对数组中每个元素，找其右侧第一个严格更大的元素，不存在则输出 -1。

这是经典的单调栈问题（第 3.5 章有详细讲解）。

📄 这是经典的**单调栈**问题（第 3.5 章有详细讲解）。 
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> answer(n, -1);  // 默认 -1（没有更大元素）
    stack<int> st;              // 存储等待答案的元素的下标

    for (int i = 0; i < n; i++) {
        // 当栈非空且当前元素 > 栈顶下标处的元素时
        while (!st.empty() && A[i] > A[st.top()]) {
            answer[st.top()] = A[i];  // A[i] 是 st.top() 的下一个更大元素
            st.pop();
        }
        st.push(i);  // 压入当前下标（等待后续更大的元素）
    }

    for (int x : answer) cout << x << " ";
    cout << "\n";

    return 0;
}

对 [3, 1, 4, 1, 5, 9, 2, 6] 的追踪：

  • i=0：压入 0。栈：[0]
  • i=1：A[1]=1 ≤ A[0]=3，压入 1。栈：[0,1]
  • i=2：A[2]=4 > A[1]=1 → answer[1]=4，弹出。A[2]=4 > A[0]=3 → answer[0]=4，弹出。压入 2。
  • i=3：压入 3。栈：[2,3]
  • i=4：A[4]=5 > A[3]=1 → answer[3]=5。A[4]=5 > A[2]=4 → answer[2]=5。压入 4。
  • i=5：A[5]=9 > A[4]=5 → answer[4]=9。压入 5。栈：[5]
  • i=6：压入 6。栈：[5,6]
  • i=7：A[7]=6 > A[6]=2 → answer[6]=6。压入 7。
  • 栈中剩余（5, 7）：answer 保持 -1。

输出：4 4 5 5 9 -1 6 -1

核心思路： 单调栈维护严格递增或递减顺序的元素。当新元素破坏该顺序时，它「解决了」所有它更大的元素。每个元素最多被压入和弹出一次，因此是 O(N)。

3.6.2 队列与 BFS 准备

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

图示：队列操作

Queue Operations

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

用队列模拟

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

📄 C++ 完整代码 
#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.6.3 双端队列——两端都能操作

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

📄 `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.6.4 单调双端队列——滑动窗口最大值

题目： 给定 N 个整数的数组 A 和大小为 K 的窗口，找每个窗口从左向右滑动时的最大值。

朴素做法：对每个窗口扫描全部 K 个元素 → O(N×K)。K 较大时太慢。

单调双端队列做法：O(N)。

双端队列按值递减的顺序存储下标，队首始终是最大值。

📄 双端队列按**值递减**的顺序存储下标，队首始终是最大值。 
#include <bits/stdc++.h>
using namespace std;

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

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    deque<int> dq;  // 存下标；A[dq[i]] 的值递减
    vector<int> maxInWindow;

    for (int i = 0; i < n; i++) {
        // 移除超出窗口的元素（队首过期）
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 从队尾移除所有小于 A[i] 的元素
        // （只要这个新元素在窗口中，它们就不可能是最大值）
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();
        }

        dq.push_back(i);  // 加入当前下标

        // 从 i = k-1 开始，窗口已满
        if (i >= k - 1) {
            maxInWindow.push_back(A[dq.front()]);  // 队首始终是最大值
        }
    }

    for (int x : maxInWindow) cout << x << " ";
    cout << "\n";

    return 0;
}

样例输入：

8 3
1 3 -1 -3 5 3 6 7

样例输出：

3 3 5 5 6 7

窗口：[1,3,-1]=3，[3,-1,-3]=3，[-1,-3,5]=5，[-3,5,3]=5，[5,3,6]=6，[3,6,7]=7。

3.6.5 基于栈的直方图最大矩形

竞赛编程经典题：给定 N 根高度为 h[0..N-1] 的柱子，找直方图内能放入的最大矩形面积。

📄 竞赛编程经典题：给定 N 根高度为 h[0..N-1] 的柱子，找直方图内能放入的最大矩形面积。 
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> h(n);
    for (int &x : h) cin >> x;

    stack<int> st;   // 按高度递增存储下标
    long long maxArea = 0;

    for (int i = 0; i <= n; i++) {
        int currentH = (i == n) ? 0 : h[i];  // 末尾添加哨兵 0

        while (!st.empty() && h[st.top()] > currentH) {
            int height = h[st.top()];   // 矩形高度
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;  // 宽度
            maxArea = max(maxArea, (long long)height * width);
        }

        st.push(i);
    }

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

⚠️ 第 3.6 章常见错误

#错误错在哪里修复方法
1对空栈/队列调用 top()/front()未定义行为，程序崩溃先检查 !st.empty()
2单调栈中比较方向错误「下一个更大」需要 >，用了 < 变成「下一个更小」仔细阅读题意，用样例验证
3滑动窗口中忘记移除过期元素双端队列的队首下标超出窗口范围，结果错误while (dq.front() <= i - k)
4直方图最大矩形忘记哨兵栈中剩余元素未处理，遗漏最终答案i == n 时使用高度 0
5混淆 stack 和 dequestack 只能访问顶部，不能遍历中间元素需要两端操作时改用 deque

本章总结

📌 核心要点

结构操作关键使用场景为什么重要
stack<T>push/pop/top — O(1)括号匹配、撤销/重做、DFSLIFO 逻辑的核心工具
queue<T>push/pop/front — O(1)BFS、模拟排队FIFO 逻辑的核心工具
deque<T>两端 push/pop — O(1)滑动窗口、BFS 变体支持两端访问的多功能容器
单调栈总计 O(N)下一个更大/更小元素USACO Silver 高频考点
单调双端队列总计 O(N)滑动窗口最大/最小值窗口极值的 O(N) 解法

❓ 常见问题

Q1：为什么单调栈是 O(N) 而不是 O(N²)？看起来有嵌套循环啊。

A：核心观察——每个元素最多被压入一次，最多被弹出一次。虽然内层 while 循环可能一次弹出多个元素，但全局弹出总次数 ≤ N。所以总操作 ≤ 2N = O(N)。这种分析方法叫均摊分析。

Q2：什么时候用 stack vs deque？

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

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

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

Q4：「最大矩形」问题为什么能用栈解决？

A：栈维护着高度递增的柱子序列。遇到更矮的柱子时，说明栈顶柱子「向右延伸」到此为止，此时可以计算以栈顶柱子为高度的矩形面积。每根柱子各压入弹出一次，总复杂度 O(N)。

🔗 与后续章节的联系

  • 第 5.2 章（图 BFS/DFS）：queue 是 BFS 的核心容器，stack 可用于迭代式 DFS
  • 第 3.4 章（双指针）：滑动窗口技术与本章的单调双端队列完美结合
  • 第 6.1–6.3 章（DP）：某些优化技术（如 DP 的滑动窗口极值优化）直接使用本章的单调双端队列
  • 单调栈也可以作为第 3.9 章（线段树）的替代——许多能用线段树解决的问题也可以用单调栈以 O(N) 解决

练习题

题目 3.6.1 — 股票跨度 🟢 简单 对每一天，找价格 ≤ 今日价格的连续天数（包含今天）。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> P(n); for (int& x : P) cin >> x;
    vector<int> span(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && P[st.top()] <= P[i]) st.pop();
        span[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    for (int x : span) cout << x << " "; cout << "\n";
}

样例： [100,80,60,70,60,75,85] → [1,1,1,2,1,4,6] 复杂度： O(N)。

题目 3.6.2 — 循环队列 🟡 中等 实现大小为 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.6.3 — 滑动窗口最小值 🟡 中等 找每个大小为 K 的滑动窗口的最小值。

✅ 完整题解 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for (int& x : a) cin >> x;
    deque<int> dq;  // 单调递增，队首 = 最小值
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " \n"[i==n-1];
    }
}

与滑动窗口最大值结构相同，但维护递增双端队列（弹出 ≥ 新元素的值）。

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

✅ 完整题解 
#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.6.5 — 干草堆模拟 🟡 中等 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";
}