C++ 竞赛训练营第二课：STL 核心容器之 stack 与 queue 详解 

一、课程导航 🚀

1. 🎯 竞赛视角：stack 与 queue 的 “不可替代性”（为什么不能只用 vector？）
2. 📚 核心特性：stack（LIFO）与 queue（FIFO）的本质区别
3. 🔧 竞赛高频操作：关键接口与效率分析（O (1) 操作全覆盖）
4. ⚡ 竞赛核心场景：括号匹配、单调栈、BFS 算法实战
5. 📝 真题演练：从入门到进阶（LeetCode 竞赛高频题）
6. ❌ 竞赛避坑指南：接口误用、边界条件处理
7. 🔖 下节预告：STL 核心容器之 priority_queue（优先队列 / 堆的竞赛用法）

二、核心知识点与竞赛实战

🎯 1. 竞赛视角：stack 与 queue 的 “不可替代性”

上一课我们学了万能的 vector，但为什么竞赛中还需要 stack 和 queue？核心原因是场景适配性—— 它们通过 “限制存取规则”，强制规范解题思路，同时保证关键操作的高效性：

• vector 是 “自由存取”（随机访问），但 stack/queue 是 “规则存取”（固定顺序），适配特定算法逻辑（如栈的后进先出对应递归、队列的先进先出对应层序遍历）；

• 关键操作（push/pop/ 访问首尾）均为 O (1) 时间复杂度，无冗余开销，比手动模拟（数组 + 指针）更简洁、不易出错；

• 竞赛中 “专用容器 + 专用算法” 是最优解（如 BFS 必用 queue，单调栈必用 stack），避免因 vector 过度灵活导致逻辑混乱。

竞赛场景适配：

• stack：括号匹配、表达式求值、单调栈（找左右第一个更大 / 更小元素）、递归模拟（避免栈溢出）；

• queue：BFS（广度优先搜索）、滑动窗口、消息队列模拟、层序遍历（树 / 图）。

📚 2. 核心特性：stack 与 queue 的本质区别

2.1 底层结构与核心规则

容器	核心规则（存取顺序）	底层实现（竞赛无关，但需了解）	核心用途
stack	后进先出（LIFO）	通常基于 deque（双端队列）适配	模拟递归、单调栈、括号匹配
queue	先进先出（FIFO）	通常基于 deque 或 list 适配	BFS 算法、滑动窗口、层序遍历

2.2 核心区别可视化

• stack：像 “叠盘子”—— 只能从最上面放（push）、最上面拿（pop），看不到中间的盘子；

• queue：像 “排队买票”—— 只能从队尾排队（push）、队首买票（pop），不能插队或中途退出。

2.3 与 vector 的选型对比（竞赛必看）

操作场景	stack/queue 优势	vector 劣势
仅需尾部添加 / 删除（stack）	接口简洁（push_back/pop_back 等价）	无劣势，但逻辑不规范
仅需队首删除 + 队尾添加（queue）	pop_front () 为 O (1)（vector 为 O (n)）	队首删除需平移元素，时间开销大
强制 LIFO/FIFO 规则	避免逻辑错误（如 BFS 不能用 LIFO）	规则灵活，易误写 “插队” 操作
单调栈 / 单调队列场景	天然适配 “只操作首尾” 的逻辑	需手动控制存取顺序，代码冗余

🔧 3. 竞赛高频操作：关键接口与效率分析

stack 和 queue 的接口非常简洁，竞赛中仅需掌握 “核心 4 接口 + 1 判断”，无需记忆复杂用法：

3.1 stack 核心接口（竞赛必备）

stack<int> stk; // 定义栈（存储int类型，可替换为任意类型）

stk.push(x); // 尾部添加元素x（O(1)），竞赛首选

stk.pop(); // 删除尾部元素（O(1)），注意：无返回值！

stk.top(); // 访问尾部元素（O(1)），必须先判空

stk.empty(); // 判断栈是否为空（O(1)），访问top/pop前必用

stk.size(); // 获取元素个数（O(1)），竞赛中偶尔用于边界判断

3.2 queue 核心接口（竞赛必备）

queue<int> q; // 定义队列（存储int类型）

q.push(x); // 队尾添加元素x（O(1)）

q.pop(); // 删除队首元素（O(1)），注意：无返回值！

q.front(); // 访问队首元素（O(1)），必须先判空

q.back(); // 访问队尾元素（O(1)），竞赛中偶尔用（如滑动窗口）

q.empty(); // 判断队列是否为空（O(1)），访问front/pop前必用

q.size(); // 获取元素个数（O(1)），如BFS中控制每层遍历次数

3.3 竞赛关键提醒（避坑第一！）

• 无返回值陷阱：pop() 仅删除元素，不返回被删除的值（与 vector 不同），需先 top()/front() 获取再 pop()；

• 越界风险：top()/front() 不能在空容器上调用，竞赛中必须先写 if (!stk.empty()) 再操作；

• 不可遍历：stack 和 queue 不支持随机访问，也不能用范围 for 循环遍历（竞赛中无需遍历，若需遍历则说明选型错误）。

⚡ 4. 竞赛核心场景：stack 与 queue 的实战应用

4.1 stack 场景 1：括号匹配（竞赛入门必考题）

题目描述：给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判断字符串是否有效（括号必须成对、顺序正确）。

核心思路：左括号入栈，右括号与栈顶匹配，匹配成功则出栈，最终栈空则有效。

竞赛代码（简洁版）：

#include <iostream>
#include <stack>       // 修正：正确包含stack头文件（原代码写了#include >）
#include <unordered_map> // 修正：正确包含unordered_map头文件（原代码写了#include _map>）
#include <string>      // 补充：string类型头文件
using namespace std;

bool isValid(string s) {
    // 修正：stack模板参数补充<char>
    stack<char> stk;
    // 修正：unordered_map模板参数补充<char, char>
    unordered_map<char, char> mp = {{')', '('}, {'}', '{'}, {']', '['}};

    for (char c : s) {
        if (mp.count(c)) { // 遇到右括号
            if (stk.empty() || stk.top() != mp[c]) return false;
            stk.pop();
        } else { // 遇到左括号，入栈
            stk.push(c);
        }
    }

    return stk.empty(); // 最终栈空则所有括号匹配
}

int main() {
    // 修正：输出流符号<<，补充endl换行
    cout << (isValid("()[]{}") ? "有效" : "无效") << endl; // 有效
    cout << (isValid("(]") ? "有效" : "无效") << endl;     // 无效

    return 0;
}

竞赛优势：代码仅 10 行核心逻辑，O (n) 时间复杂度，无冗余操作，是竞赛标准答案。

4.2 stack 场景 2：单调栈（竞赛高频难点）

题目描述：给定一个整数数组，返回每个元素的 “下一个更大元素”（即数组中右边第一个比它大的元素，若无则为 - 1）。

核心思路：维护一个 “单调递减栈”，栈中存储元素索引，遍历数组时：

• 若当前元素 > 栈顶元素：栈顶元素的下一个更大元素就是当前元素，出栈并记录结果；

• 否则：当前元素入栈，维持栈的递减特性。

竞赛代码（O (n) 时间，最优解）：

#include <iostream>   // 补充：用于cout输出
#include <vector>     // 补充：vector容器头文件
#include <stack>      // 补充：stack容器头文件
using namespace std;

// 修正：函数参数补充<int>，返回值指定<int>
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1); // 修正：补充<int>，定义结果数组
    stack<int> stk;         // 修正：补充<int>，栈存储索引

    // 修正：循环条件i < n
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && nums[i] > nums[stk.top()]) {
            res[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }

    return res;
}

int main() {
    vector<int> nums = {2, 1, 2, 4, 3}; // 修正：补充<int>和赋值符号
    vector<int> res = nextGreaterElement(nums);

    // 修正：输出流符号<<
    for (int x : res) cout << x << " "; 
    cout << endl; // 补充换行

    return 0;
}

竞赛关键：单调栈是 “空间换时间” 的典范，将暴力 O (n²) 优化为 O (n)，是竞赛中 “找左右第一个极值” 问题的标准解法。

4.3 queue 场景：BFS 算法（广度优先搜索，竞赛必考）

题目描述：给定一棵二叉树，返回其层序遍历结果（按层次从上到下、从左到右遍历节点值）。

核心思路：用队列存储当前层节点，遍历一层时弹出所有节点，同时将下一层节点入队，循环至队空。

竞赛代码（二叉树层序遍历）：

#include <iostream>   // 补充：用于cout输出
#include <vector>     // 补充：vector容器头文件
#include <queue>      // 补充：queue容器头文件
using namespace std;

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 修正：函数名补充level，返回值和参数完整
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res; // 修正：补充<int>
    if (!root) return res;

    queue<TreeNode*> q; // 修正：queue模板参数为TreeNode*（原代码queuereeNode*错误）
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> level;

        // 修正：循环条件i < levelSize
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* curr = q.front();
            q.pop();
            level.push_back(curr->val);

            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }

        res.push_back(level);
    }

    return res;
}

// 测试代码
int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    vector<vector<int>> res = levelOrder(root); // 修正：补充<int>

    for (auto& level : res) {
        for (int x : level) cout << x << " ";
        cout << endl;
    }

    // 释放内存（可选，避免内存泄漏）
    delete root->right->right;
    delete root->right->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

竞赛延伸：BFS 不仅用于二叉树层序遍历，还用于最短路径问题（如迷宫最短路径、单词接龙），核心都是 “队列存储待处理节点，按顺序处理”。

📝 5. 真题演练：竞赛高频题强化

例题 1：stack—— 有效的括号字符串（LeetCode 678，中等难度）

题目描述：给定一个包含 '('、')' 和 '' 的字符串，'' 可以当作 '('、')' 或空字符，判断字符串是否有效。

核心思路：用两个栈分别存储左括号索引和 '' 索引，遇到右括号时优先匹配左括号，左括号为空则匹配 ''，均为空则无效。

竞赛代码关键片段：

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

bool checkValidString(string s) {
    stack<int> leftStk, starStk; // 存储左括号和*的索引

    // 遍历字符串，匹配右括号
    for (int i = 0; i < s.size(); ++i) { // 修正：补全循环条件i < s.size()
        if (s[i] == '(') {
            leftStk.push(i);
        } else if (s[i] == '*') {
            starStk.push(i);
        } else { // 遇到右括号
            if (!leftStk.empty()) {
                leftStk.pop(); // 优先用左括号匹配
            } else if (!starStk.empty()) {
                starStk.pop(); // 用*匹配
            } else {
                return false; // 无匹配项，直接返回false
            }
        }
    }

    // 剩余左括号需用*匹配（*的索引必须在左括号之后）
    while (!leftStk.empty() && !starStk.empty()) {
        if (leftStk.top() > starStk.top()) {
            return false; // *在左括号前面，无法匹配
        }
        leftStk.pop();
        starStk.pop();
    }

    return leftStk.empty(); // 左括号全部匹配完则有效
}

// 测试用例
int main() {
    cout << boolalpha; // 让cout输出true/false而非1/0
    cout << checkValidString("()") << endl;       // true
    cout << checkValidString("(*)") << endl;      // true
    cout << checkValidString("(*))") << endl;     // true
    cout << checkValidString("(((*)") << endl;    // false
    cout << checkValidString(")*(") << endl;      // false
    return 0;
}

例题 2：queue—— 滑动窗口最大值（LeetCode 239，困难难度，队列优化）

题目描述：给定一个数组和滑动窗口大小 k，返回每个窗口中的最大值。

核心思路：用 “单调队列”（队列中存储元素索引，维持队列递减），窗口滑动时：

• 移除队列中超出窗口范围的元素；

• 移除队列中比当前元素小的元素（保证队首是最大值）；

• 当前元素入队，队首即为当前窗口最大值。

竞赛代码（O (n) 时间，最优解）：

#include <iostream>   // 补充：用于cout输出
#include <vector>     // 补充：vector容器头文件
#include <deque>      // 补充：deque容器头文件（原代码写了#include >）
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) { // 修正：补充参数nums的引用
    vector<int> res;
    deque<int> q; // 修正：补充deque模板参数<int>，存储数组索引

    for (int i = 0; i < nums.size(); ++i) { // 修正：循环条件i < nums.size()
        // 1. 移除窗口外的元素（队首索引超出窗口左边界）
        if (!q.empty() && q.front() <= i - k) q.pop_front(); // 修正：窗口边界判断

        // 2. 维护单调队列：移除队尾比当前元素小的索引（保证队首是最大值索引）
        while (!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();

        // 3. 当前元素索引入队
        q.push_back(i);

        // 4. 窗口形成后（i >= k-1），记录队首对应的最大值
        if (i >= k - 1) res.push_back(nums[q.front()]);
    }

    return res;
}

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7}; // 修正：补充<int>和赋值符号
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k); // 修正：变量名res，补充赋值

    // 修正：输出流符号<<
    for (int x : res) cout << x << " "; 
    cout << endl;

    return 0;
}

竞赛关键：这道题用普通队列会超时，单调队列是竞赛中的 “最优解模板”，必须掌握。

❌ 6. 竞赛避坑指南：常见错误与解决方案

6.1 接口误用（最容易丢分！）

• 错误 1：调用 pop() 后直接访问元素（如 stk.pop(); cout <.top();）—— 忘记 pop() 无返回值，需先 top() 再 pop()；

• 错误 2：queue 用 top() 访问队首（queue 无 top()，队首是 front()，队尾是 back()）；

• 错误 3：空容器调用 top()/front()—— 竞赛中必须先判空（if (!stk.empty())），否则直接 RE（运行时错误）。

6.2 边界条件处理

• 场景：括号匹配中 “左括号多” 或 “右括号多”（如 "(((" 或 ")))"）—— 最终需判断栈是否为空；

• 场景：BFS 中根节点为空（如二叉树层序遍历输入 null）—— 需先判断 if (!root) 直接返回；

• 场景：单调栈中数组元素全相等（如 [5,5,5]）—— 无需特殊处理，栈会维持递减，最终结果全为 - 1。

6.3 性能误区

• 错误：用 stack/queue 存储大量数据时调用 size() 遍历（如 for (int i=0; ik.size(); ++i)）——size() 是 O (1)，但 stack/queue 不能随机访问，遍历无意义；

• 正确：若需遍历，说明选型错误，应改用 vector 或 deque。

🔖 7. 下节预告：STL 核心容器之 priority_queue（优先队列 / 堆的竞赛用法）

1. 基础特性：大根堆（默认）与小根堆快速配置，核心接口（push/pop/top/empty）；
2. 自定义优先级：结构体 /pair 的排序规则配置（竞赛高频）；
3. 竞赛核心场景：贪心算法、topK 问题、Dijkstra 最短路径算法；
4. 真题适配：第 k 个最大元素、合并 k 个升序链表、数据流的中位数。