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

引言在前面 STL 系列中我们学习了vector、deque、list、set、map等容器。今天要讲的queue和stack不是独立的容器而是容器适配器——它们底层使用其他容器默认是deque但只暴露特定的接口。stack后进先出LIFO只能操作栈顶queue先进先出FIFO只能操作队头和队尾这种限制接口的设计正是适配器模式的核心思想把功能丰富的容器包装成特定用途的数据结构让使用者更安全、更语义化。第一部分stack栈一、基本概念栈是后进先出LIFOLast In First Out的数据结构。最后放进去的元素最先取出来。就像一摞盘子——最上面的先用。二、创建与初始化#include iostream #include stack #include vector #include list using namespace std; int main() { // 1. 默认底层 deque stackint s1; // 2. 指定底层容器为 vector stackint, vectorint s2; // 3. 指定底层容器为 list stackint, listint s3; // 注意stack 不支持初始化列表 // stackint s {1,2,3}; // 错误 return 0; }三、核心操作stackint 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; // 0false操作方法说明入栈push(val)将元素放入栈顶出栈pop()移除栈顶元素不返回值获取栈顶top()返回栈顶元素的引用大小size()返回元素个数判空empty()是否为空重要pop()不返回被删除的值需要先top()获取值再pop()删除。// ✅ 正确做法 int val s.top(); s.pop(); // ❌ pop() 没有返回值 // int val s.pop(); // 编译错误四、完整示例#include iostream #include stack using namespace std; int main() { stackint 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队列一、基本概念队列是先进先出FIFOFirst In First Out的数据结构。先放进去的元素先取出来。就像排队买票——先来的先服务。二、创建与初始化#include iostream #include queue #include list using namespace std; int main() { // 1. 默认底层 deque queueint q1; // 2. 指定底层容器为 list queueint, listint q2; // 错误vector 没有 pop_front // queueint, vectorint q3; // 编译错误 return 0; }三、核心操作queueint 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操作方法说明入队push(val)将元素放入队尾出队pop()移除队头元素不返回值获取队头front()返回队头元素的引用获取队尾back()返回队尾元素的引用大小size()返回元素个数判空empty()是否为空四、完整示例#include iostream #include queue using namespace std; int main() { queueint 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 对比操作stackqueue插入push()栈顶push()队尾删除pop()栈顶pop()队头获取top()栈顶front()队头 /back()队尾特点后进先出LIFO先进先出FIFO类比一摞盘子排队买票默认底层dequedeque可用底层deque / vector / listdeque / list不能用 vector第四部分priority_queue优先队列一、基本概念priority_queue是另一种队列适配器它不按入队顺序出队而是按优先级——默认最大的元素优先出队。二、基本操作#include iostream #include queue #include functional // greater using namespace std; int main() { // 默认大顶堆降序出队 priority_queueint 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_queueint, vectorint, greaterint 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; }操作方法说明入队push(val)插入并自动调整出队pop()移除堆顶元素获取堆顶top()返回优先级最高的元素大小size()元素个数判空empty()是否为空三、自定义优先级// 自定义类型 struct Student { string name; int score; }; // 自定义比较器分数高的优先 struct CompareScore { bool operator()(const Student a, const Student b) { return a.score b.score; // 大顶堆分数高的优先 } }; int main() { priority_queueStudent, vectorStudent, 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; }第五部分适配器底层容器选择适配器默认容器可选容器不能用原因stackdequevector, list—都需要 back/push_back/pop_backqueuedequelistvectorvector 没有 pop_frontpriority_queuevectordequelist需要随机访问总结一、核心操作速查操作stackqueuepriority_queue插入pushpushpush删除poppoppop访问top()front()/back()top()特点LIFOFIFO按优先级二、适配器设计思想三、一句话记忆stack 后进先出只操作栈顶push/pop/topqueue 先进先出操作两端push/pop/front/backpriority_queue 按优先级出队push/pop/top。三者都是容器适配器默认底层用 deque只暴露有限接口。