概述
stack、queue 和 priority_queue 在 C++ STL 中有一个特殊的身份——它们不是独立容器，而是容器适配器（Container Adapter）。
这意味着它们没有自己的底层存储，而是基于其他容器（默认 deque）实现的。它们通过限制底层容器的接口，只暴露特定操作，从而实现栈和队列的语义。
1
2
3
4
5
6
7
8
9
10
11
12
| ┌─────────┐
│ stack │ 只允许顶部操作
├─────────┤
│ queue │ 只允许两端操作
├─────────┤
│priority │ 只允许顶部操作（优先级）
│ _queue │
└────┬────┘
│ 适配
┌──────┴──────┐
│ deque/vector │ （底层容器）
└─────────────┘
|
stack —— 栈
栈是后进先出（LIFO, Last In First Out）的数据结构。就像一摞盘子，最后放上去的最先被拿走。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
std::cout << "top: " << s.top() << std::endl;
std::cout << "size: " << s.size() << std::endl;
std::cout << "empty: " << s.empty() << std::endl;
while (!s.empty()) {
std::cout << s.top() << " ";
s.pop();
}
std::cout << std::endl;
return 0;
}
|
stack 的完整接口
| 操作 |
说明 |
复杂度 |
push(x) |
入栈 |
O(1) |
pop() |
出栈（无返回值！） |
O(1) |
top() |
访问栈顶元素 |
O(1) |
size() |
元素数量 |
O(1) |
empty() |
是否为空 |
O(1) |
emplace(args...) |
原地构造入栈（C++11） |
O(1) |
指定底层容器
1
2
3
4
5
6
7
8
9
10
11
12
| #include <stack>
#include <vector>
#include <list>
std::stack<int> s1;
std::stack<int, std::vector<int>> s2;
std::stack<int, std::list<int>> s3;
|
实际应用：括号匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <stack>
#include <string>
bool isValidParentheses(const std::string& s) {
std::stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty()) return false;
char top = st.top();
st.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return st.empty();
}
int main() {
std::cout << std::boolalpha;
std::cout << isValidParentheses("()") << std::endl;
std::cout << isValidParentheses("()[]{}") << std::endl;
std::cout << isValidParentheses("(]") << std::endl;
std::cout << isValidParentheses("([)]") << std::endl;
std::cout << isValidParentheses("{[]}") << std::endl;
std::cout << isValidParentheses("(") << std::endl;
return 0;
}
|
实际应用：表达式求值（后缀表达式）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <stack>
#include <string>
#include <cctype>
int evaluatePostfix(const std::string& expr) {
std::stack<int> st;
for (char c : expr) {
if (isspace(c)) continue;
if (isdigit(c)) {
st.push(c - '0');
} else {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
switch (c) {
case '+': st.push(a + b); break;
case '-': st.push(a - b); break;
case '*': st.push(a * b); break;
case '/': st.push(a / b); break;
}
}
}
return st.top();
}
int main() {
std::cout << evaluatePostfix("3 4 + 2 *") << std::endl;
std::cout << evaluatePostfix("5 1 2 + 4 * + 3 -") << std::endl;
return 0;
}
|
queue —— 队列
队列是先进先出（FIFO, First In First Out）的数据结构。就像排队买票，先到先服务。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
#include <queue>
int main() {
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
std::cout << "front: " << q.front() << std::endl;
std::cout << "back: " << q.back() << std::endl;
std::cout << "size: " << q.size() << std::endl;
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
std::cout << std::endl;
return 0;
}
|
queue 的完整接口
| 操作 |
说明 |
复杂度 |
push(x) / emplace(x) |
入队 |
O(1) |
pop() |
出队（无返回值！） |
O(1) |
front() |
访问队首 |
O(1) |
back() |
访问队尾 |
O(1) |
size() |
元素数量 |
O(1) |
empty() |
是否为空 |
O(1) |
指定底层容器
1
2
3
4
5
6
7
8
| #include <queue>
#include <list>
std::queue<int> q1;
std::queue<int, std::list<int>> q2;
|
⚠️ queue 不能用 vector 作为底层容器，因为 vector 不支持 pop_front()。
实际应用：BFS 层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <queue>
#include <vector>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (!root) return result;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
std::vector<int> level;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
auto result = levelOrder(root);
for (auto& level : result) {
for (int x : level) {
std::cout << x << " ";
}
std::cout << std::endl;
}
return 0;
}
|
priority_queue —— 优先队列
优先队列是一个堆实现的容器适配器，默认是最大堆。每次取出的不是最先入队的元素，而是优先级最高（最大或最小）的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}
|
最小堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <iostream>
#include <queue>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
minHeap.push(1);
minHeap.push(5);
while (!minHeap.empty()) {
std::cout << minHeap.top() << " ";
minHeap.pop();
}
std::cout << std::endl;
return 0;
}
|
自定义类型优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
#include <queue>
#include <string>
struct Task {
std::string name;
int priority;
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
int main() {
std::priority_queue<Task> pq;
pq.push({"Low priority task", 1});
pq.push({"High priority task", 3});
pq.push({"Medium priority task", 2});
while (!pq.empty()) {
auto task = pq.top();
pq.pop();
std::cout << task.name << " (priority: " << task.priority << ")" << std::endl;
}
return 0;
}
|
实际应用：Top K 问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <queue>
#include <vector>
std::vector<int> topK(const std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int x : nums) {
minHeap.push(x);
if ((int)minHeap.size() > k) {
minHeap.pop();
}
}
std::vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result;
}
int main() {
std::vector<int> nums = {3, 2, 1, 5, 6, 4, 8, 7, 9, 10};
auto result = topK(nums, 3);
std::cout << "Top 3: ";
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
实际应用：合并 K 个有序链表（堆方法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <queue>
#include <vector>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct CompareNode {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(std::vector<ListNode*>& lists) {
std::priority_queue<ListNode*, std::vector<ListNode*>, CompareNode> pq;
for (auto* node : lists) {
if (node) pq.push(node);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = tail->next;
if (node->next) {
pq.push(node->next);
}
}
return dummy.next;
}
|
三种适配器对比
| 特性 |
stack |
queue |
priority_queue |
| 数据结构 |
LIFO 栈 |
FIFO 队列 |
堆 |
| 默认底层容器 |
deque |
deque |
vector |
| 插入 |
push() |
push() |
push() |
| 删除 |
pop() |
pop() |
pop() |
| 访问 |
top() |
front()/back() |
top() |
| 遍历 |
❌ 不支持 |
❌ 不支持 |
❌ 不支持 |
| 排序 |
按插入顺序（逆序） |
按插入顺序 |
按优先级 |
常见陷阱
1. pop() 不返回值！
1
2
3
4
5
6
7
8
9
| std::stack<int> s;
s.push(42);
int val = s.top();
s.pop();
|
这是初学者最常犯的错误。STL 设计成 pop() 不返回值是有原因的：如果 pop() 返回值，在返回过程中如果发生异常（拷贝构造失败），元素已经被弹出了，就丢失了。分离 top() 和 pop() 更安全。
2. 不要试图遍历适配器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
std::stack<int> temp = s;
while (!temp.empty()) {
std::cout << temp.top() << " ";
temp.pop();
}
|
3. priority_queue 不支持修改已有元素
1
2
3
4
5
6
7
8
9
| std::priority_queue<int> pq;
pq.push(5);
pq.push(3);
pq.push(8);
|
4. priority_queue 的模板参数顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
std::priority_queue<int> pq1;
std::priority_queue<int, std::vector<int>, std::less<int>> pq1_full;
std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;
auto cmp = [](const auto& a, const auto& b) { return a.val < b.val; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq3(cmp);
|
总结
- stack：DFS、递归转迭代、括号匹配、表达式求值
- queue：BFS、层序遍历、任务调度、消息队列
- priority_queue：Top K、Dijkstra、贪心、任务调度（按优先级）
理解适配器模式有助于你更好地使用这些容器，也明白为什么它们不支持迭代器——限制接口正是适配器的意义所在。
