深入解析STL中的stack、queue与priority_queue

引言

在前面 STL 系列中，我们学习了 vector、deque、list、set、map 等容器。今天要讲的 queue 和 stack 不是独立的容器，而是容器适配器——它们底层使用其他容器（默认是 deque），但只暴露特定的接口。

• stack：后进先出（LIFO），只能操作栈顶

• queue：先进先出（FIFO），只能操作队头和队尾

这种"限制接口"的设计正是适配器模式的核心思想：把功能丰富的容器包装成特定用途的数据结构，让使用者更安全、更语义化。

第一部分：stack（栈）

一、基本概念

栈是后进先出（LIFO，Last In First Out）的数据结构。最后放进去的元素，最先取出来。就像一摞盘子——最上面的先用。

二、创建与初始化

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

int main() {
// 1. 默认（底层 deque）
stack<int> s1;

// 2. 指定底层容器为 vector
stack<int, vector<int>> s2;

// 3. 指定底层容器为 list
stack<int, list<int>> s3;

// 注意：stack 不支持初始化列表！
// stack<int> s = {1,2,3}; // 错误！

return 0;
}

三、核心操作

stack<int> s;

// push：入栈
s.push(10);
s.push(20);
s.push(30);

// top：获取栈顶元素（不删除）
cout << s.top() << endl; // 30

// pop：弹出栈顶元素（不返回）
s.pop();
cout << s.top() << endl; // 20

// size / empty
cout << "元素个数：" << s.size() << endl; // 2
cout << "是否为空：" << s.empty() << endl; // 0（false）

重要：pop() 不返回被删除的值！需要先 top() 获取值，再 pop() 删除。

// ✅ 正确做法
int val = s.top();
s.pop();

// ❌ pop() 没有返回值
// int val = s.pop(); // 编译错误

四、完整示例

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

int main() {
stack<int> s;

cout << "入栈顺序：";
for (int i = 1; i <= 5; i++) {
cout << i << " ";
s.push(i);
}
cout << endl;

cout << "出栈顺序：";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
// 输出：5 4 3 2 1（后进先出）

return 0;
}

第二部分：queue（队列）

一、基本概念

队列是先进先出（FIFO，First In First Out）的数据结构。先放进去的元素，先取出来。就像排队买票——先来的先服务。

二、创建与初始化

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

int main() {
// 1. 默认（底层 deque）
queue<int> q1;

// 2. 指定底层容器为 list
queue<int, list<int>> q2;

// 错误！vector 没有 pop_front
// queue<int, vector<int>> q3; // 编译错误！

return 0;
}

三、核心操作

queue<int> q;

// push：入队（队尾）
q.push(10);
q.push(20);
q.push(30);

// front：获取队头元素（不删除）
cout << q.front() << endl; // 10

// back：获取队尾元素（不删除）
cout << q.back() << endl; // 30

// pop：出队（队头）
q.pop();
cout << q.front() << endl; // 20

// size / empty
cout << "元素个数：" << q.size() << endl; // 2

四、完整示例

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

int main() {
queue<int> q;

cout << "入队顺序：";
for (int i = 1; i <= 5; i++) {
cout << i << " ";
q.push(i);
}
cout << endl;

cout << "出队顺序：";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
// 输出：1 2 3 4 5（先进先出）

return 0;
}

第三部分：stack vs queue 对比

第四部分：priority_queue（优先队列）

一、基本概念

priority_queue 是另一种队列适配器，它不按入队顺序出队，而是按优先级——默认最大的元素优先出队。

二、基本操作

#include <iostream>
#include <queue>
#include <functional> // greater<>
using namespace std;

int main() {
// 默认大顶堆（降序出队）
priority_queue<int> pq1;
pq1.push(3);
pq1.push(5);
pq1.push(1);
pq1.push(9);

cout << "大顶堆出队：";
while (!pq1.empty()) {
cout << pq1.top() << " "; // 9 5 3 1
pq1.pop();
}
cout << endl;

// 小顶堆（升序出队）
priority_queue<int, vector<int>, greater<int>> pq2;
pq2.push(3);
pq2.push(5);
pq2.push(1);
pq2.push(9);

cout << "小顶堆出队：";
while (!pq2.empty()) {
cout << pq2.top() << " "; // 1 3 5 9
pq2.pop();
}
cout << endl;

return 0;
}

三、自定义优先级

// 自定义类型
struct Student {
string name;
int score;
};

// 自定义比较器（分数高的优先）
struct CompareScore {
bool operator()(const Student& a, const Student& b) {
return a.score < b.score; // 大顶堆：分数高的优先
}
};

int main() {
priority_queue<Student, vector<Student>, CompareScore> pq;
pq.push({"张三", 85});
pq.push({"李四", 92});
pq.push({"王五", 78});

while (!pq.empty()) {
cout << pq.top().name << ": " << pq.top().score << endl;
pq.pop();
}
// 李四: 92
// 张三: 85
// 王五: 78

return 0;
}

第五部分：适配器底层容器选择

总结

一、核心操作速查

二、适配器设计思想

三、一句话记忆

stack 后进先出只操作栈顶（push/pop/top），queue 先进先出操作两端（push/pop/front/back），priority_queue 按优先级出队（push/pop/top）。三者都是容器适配器，默认底层用 deque，只暴露有限接口。