Lesson 0011 · 栈、队列与优先队列

C++ 进阶 — 第 4 课

1. stack — 后进先出（LIFO）

像一摞盘子：最后放上去的，最先拿下来。

#include <stack>

stack<int> s;
s.push(1);           // 放入 1
s.push(2);           // 放入 2
s.push(3);           // 放入 3
cout << s.top();     // 3（只看栈顶，不删）
s.pop();             // 弹出栈顶（删掉 3）
cout << s.size();    // 2（还剩 1, 2）

经典应用：括号匹配

bool check(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);
        else if (c == ')') {
            if (st.empty()) return false;  // 右括号多了
            st.pop();
        }
    }
    return st.empty();                     // 栈空才算匹配
}

为什么用栈？因为一个右括号只能和「最近一个还没配对的左括号」配对 —— 最近的先出，正好是后进先出。最后那行 return st.empty(); 是在查「左括号多了」的情况，两个方向都要查。

2. queue — 先进先出（FIFO）

像排队：先来的先处理。

#include <queue>

queue<int> q;
q.push(1);           // 入队
q.push(2);
q.push(3);
cout << q.front();   // 1（队首，不删）
cout << q.back();    // 3（队尾，不删）
q.pop();             // 出队（删掉 1）
cout << q.front();   // 2

注意和栈一样：pop() 只负责删，不负责把删掉的东西交给你。想要那个值，得先用 front() / top() 存一份。

3. priority_queue — 每次取最大（或最小）

不是按「先来后到」，而是按值的大小出队。

#include <queue>         // priority_queue 也在 queue 头文件里

priority_queue<int> pq;
pq.push(3);
pq.push(5);
pq.push(1);
cout << pq.top();       // 5（最大）
pq.pop();
cout << pq.top();       // 3

默认大顶堆（大的先出）。想要小的先出：

priority_queue<int, vector<int>, greater<int>> pq;  // 小顶堆

三个模板参数要写全：元素类型、底层容器、比较器。少写一个都编译不过 —— 这也是初学者最常卡住的一行。

为什么 top() 是 O(1) 而 push / pop 是 O(log n)？因为堆只保证「堆顶最大」，一看就有答案；而进来一个、出去一个，都要沿着树往上或往下挪几层，层数是 log n。

4. 三者对比

5. 用 vector 模拟 stack

stack 底层就是 vector，只是把 push_back 改名 push，把 pop_back 改名 pop，然后禁掉中间插入：

vector<int> v;
v.push_back(1);   v.push_back(2);    // 代替 push
cout << v.back();                    // 代替 top()
v.pop_back();                         // 代替 pop()

6. 坑点清单

• pop() 不返回元素：它只删不给。想要那个值，先 top() / front() 存一份，再 pop()。
• 先判空，再取值：在空容器上调用 top() / front() / pop() 是未定义行为，程序可能直接崩。
• 小顶堆要写全三个参数：priority_queue<int, vector<int>, greater<int>>，只写 greater 不行。
• 优先队列不能遍历：它没有下标、也没有迭代器，想看全部只能反复 top() + pop()，而且这样会把堆清空。
• 括号匹配别只查右括号：最后一定要 return st.empty();，否则 (() 这种会判成匹配。
• 这三种容器都只能动两端：需要按下标访问、需要随机插入时，还是回 vector。

7. 小测

8. 动手练习

选做：把第 5 节的 vector 写法包成一个 struct MyStack，只公开 push / pop / top / size / empty，内部用 vector 存。写完你就明白「限制操作」是什么意思了。

卡住时的自查顺序

1. 括号题先跑 ()、)(、(() 三组样例，看三个答案是不是都对的。
2. 每次 pop() / top() / front() 之前问一句：这时候容器会不会是空的？
3. 最后有没有 return st.empty();？漏了它，左括号多的串会被判成匹配。
4. 优先队列要小顶堆，三个模板参数写全了吗？编译错误多半在这一行。
5. 答案对但顺序不对：是不是把队列当栈用了（或者反过来）？把操作序列抄在纸上画一遍。
6. 都不是：把输入、期望输出、你的输出三样一起贴过来。

本课小结

• stack：后进先出，括号匹配、撤销操作。
• queue：先进先出，排队、BFS 广搜。
• priority_queue：按大小出，Top K、合并类问题；默认大顶堆，push/pop 是 O(log n)，top 是 O(1)。
• 三者都是限制操作方式的容器，用对工具代码更清晰。