C++复健笔记 Vol.5：stack、queue、deque 和 priority_queue

发布于 2026年6月14日 2321 字约 12 分钟

摘要

复习四个常见容器：栈、队列、双端队列和优先队列。|

这一篇继续补 STL 里非常常见的几个容器：stack、queue、deque 和 priority_queue。

它们都很适合机考，因为语义直接，代码短，手写起来也不容易太绕。

stack：后进先出

stack 可以理解成栈，最后放进去的元素最先出来。

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

int main() {
    stack<int> st;

    st.push(1);
    st.push(2);
    st.push(3);

    cout << st.top() << '\n'; // 3
    st.pop();
    cout << st.top() << '\n'; // 2

    return 0;
}

常用操作：

st.push(x)：入栈。
st.pop()：出栈。
st.top()：栈顶元素。
st.empty()：是否为空。
st.size()：元素个数。

栈特别适合做：

括号匹配；
撤销/回退类模拟；
单调栈。

注意，pop() 只是删掉栈顶，不返回值。要先 top() 再 pop()。

int x = st.top();
st.pop();

空栈不能直接 top() 或 pop()。

queue：先进先出

queue 是队列，先进去的先出来。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    cout << q.front() << '\n'; // 1
    q.pop();
    cout << q.front() << '\n'; // 2

    return 0;
}

常用操作：

q.push(x)：入队。
q.pop()：出队。
q.front()：队头元素。
q.back()：队尾元素。
q.empty()：是否为空。
q.size()：元素个数。

队列常见于：

BFS；
模拟排队；
逐层处理问题。

和栈一样，pop() 不返回值，先取 front() 再 pop()。

deque：双端队列

deque 是双端队列，前后都能进出。

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d;

    d.push_back(2);
    d.push_front(1);
    d.push_back(3);

    cout << d.front() << ' ' << d.back() << '\n'; // 1 3
    d.pop_front();
    d.pop_back();

    return 0;
}

常用操作：

d.push_back(x)：尾部插入。
d.push_front(x)：头部插入。
d.pop_back()：尾部删除。
d.pop_front()：头部删除。
d.front()：头元素。
d.back()：尾元素。
d[i]：支持下标访问。

deque 的一个优点是既像队列，又能当数组用。

机考里它常出现在：

单调队列；
滑动窗口；
需要两端操作的模拟题。

这里可以顺手记住一句：deque 比 vector 更适合频繁头插头删，但随机访问通常还是 vector 更常见。

priority_queue：优先队列

priority_queue 默认是大根堆，也就是每次 top() 都拿到最大的元素。

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(3);
    pq.push(1);
    pq.push(5);

    cout << pq.top() << '\n'; // 5
    pq.pop();
    cout << pq.top() << '\n'; // 3

    return 0;
}

常用操作：

pq.push(x)：插入元素。
pq.pop()：删除堆顶。
pq.top()：堆顶元素。
pq.empty()：是否为空。
pq.size()：元素个数。

和前面一样，pop() 不返回值。

小根堆

默认是大根堆。如果要小根堆，可以加比较器：

priority_queue<int, vector<int>, greater<int>> pq;

例子：

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(3);
pq.push(1);
pq.push(5);

cout << pq.top() << '\n'; // 1

这个在写最短路、Top K、贪心题时很常见。

priority_queue 和 pair

priority_queue 也可以放 pair。

priority_queue<pair<int, int>> pq;
pq.push({2, 10});
pq.push({1, 99});
pq.push({2, 5});

默认会先比 first，first 相同再比 second。

所以上面堆顶会是 {2, 10}。

如果想按别的规则排序，就需要自定义比较器。

struct Cmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> pq;

这个比较器写法一开始容易绕，但核心只要记住：它决定“谁的优先级更高”。

这几个容器到底怎么选

可以粗暴记成：

stack：只在一头进出，后进先出。
queue：一头进，一头出，先进先出。
deque：两头都能操作，灵活。
priority_queue：每次拿最值，适合堆。

如果题目里出现“最近的”“上一个”“配对消除”，先想栈。

如果出现“按顺序处理”“一层一层扩散”，先想队列。

如果出现“头尾都要动”，看看 deque。

如果出现“每次取最大/最小值”，优先想 priority_queue。

小练习：模拟出栈顺序

读入一串操作，1 x 表示入栈，2 表示出栈并输出栈顶。

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

int main() {
    int m;
    cin >> m;

    stack<int> st;
    for (int i = 0; i < m; i++) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            st.push(x);
        } else if (op == 2) {
            if (!st.empty()) {
                cout << st.top() << '\n';
                st.pop();
            }
        }
    }

    return 0;
}

这个题型很适合拿来练手，因为它几乎就是在复述容器 API。

小结

stack：后进先出，适合括号、回退、单调栈。
queue：先进先出，适合 BFS 和排队模拟。
deque：双端都能操作，常用于滑动窗口和单调队列。
priority_queue：默认大根堆，greater<int> 可变小根堆。
pop() 都不返回值，先 top() / front() 再删。