stack、queue 与 priority_queue 底层剖析

C++ STL stack、queue 与 priority_queue 底层剖析：容器适配器的设计哲学

这篇不聊pushpop怎么用。如果你还在背接口，先去看 cppreference。这里只干三件事：

1. 容器适配器到底是什么设计模式，为什么 STL 不把 stack 和 queue 算进"容器"
2. deque 的底层分段连续结构——为什么它天生是给 stack 和 queue 当爹的料
3. priority_queue 的堆维护到底在干什么，make_heap/push_heap/pop_heap的复杂度怎么保证

一、容器适配器：这不是容器，是包装纸

STL 的容器家族分三类：

• 序列式容器：vector、list、deque——自己管内存，自己管数据
• 关联式容器：map、set、unordered_map——自己管键值关系
• 容器适配器：stack、queue、priority_queue——不自己管任何事

适配器的核心思想来自设计模式里的Adapter Pattern：把一个类的接口转换成客户希望的另一个接口。stack 和 queue 本质上就是对某个底层容器的接口做了一层裁剪和重命名。

template<classT,classContainer=deque<T>>classstack{Container _c;public:voidpush(constT&x){_c.push_back(x);}voidpop(){_c.pop_back();}T&top(){return_c.back();}// ...};

看到没有？stack 自己没有内存，没有节点，什么都没有。它只有一个_c，所有操作都转发给_c。这就是为什么 STL 不把 stack 和 queue 划入容器——它们没有独立的存储语义，只是"容器的一种使用方式"。

1.1 为什么这种设计是合理的

假设 STL 把 stack 做成独立容器，底层用链表实现。那你会得到什么？

• 一套和 vector/list/deque 完全不同的内存管理逻辑
• 一堆重复的 bug（内存泄漏、迭代器失效）
• 无法复用已有的优化（比如 vector 的缓存友好性）

适配器模式把"栈的抽象语义"和"底层存储"解耦。你要栈语义？行，随便挑一个底层容器，只要它支持push_back/pop_back就行。想缓存友好选 vector，想稳定迭代器选 list，想两头通吃选 deque。

这是典型的"组合优于继承"——stack has-a Container，而不是 stack is-a Container。

1.2 底层容器的选择策略

PPT 里提到 stack 可以用 vector 模拟，queue 可以用 list 模拟。这没问题，但默认用 deque 是经过深思熟虑的。下一节拆 deque 的底。

二、deque：分段连续的障眼法

deque 全称 double-ended queue，双端队列。它的设计目标很直接：头尾插入删除都是 O(1)，同时保持比 list 更好的缓存友好性。

2.1 内存布局：不是数组，是数组的数组

deque 的底层不是一大块连续内存，而是一组固定大小的小数组（buffer），再用一个**中控数组（map）**来索引这些小数组。

map（中控数组，存储各 buffer 的指针） +----+----+----+----+----+----+ | ptr| ptr| ptr| ptr| ptr| ptr| +----+----+----+----+----+----+ | | | v v v +-----+ +-----+ +-----+ |a b c| |d e f| |g h i| <-- 每个 buffer 固定大小（如 512 个元素） +-----+ +-----+ +-----+ ^ ^ begin end

中控数组本身也是动态的，满了就扩容——但扩容成本很低，因为它只存指针，不存元素。搬移的是指针数组，不是元素本身。

2.2 迭代器的负担

deque 要维持"随机访问"的假象，迭代器设计比 vector 复杂得多。一个 deque 迭代器通常要存四个东西：

struct_Deque_iterator{T*_M_cur;// 指向当前元素T*_M_first;// 指向当前 buffer 的首元素T*_M_last;// 指向当前 buffer 的尾后位置T**_M_node;// 指向中控数组中的当前 buffer 指针};

四个指针，32 字节（64 位系统）。对比 vector 迭代器就是一个T*（8 字节），差距巨大。

为什么需要这么多？因为 deque 的++操作要处理跨 buffer 边界：

Self&operator++(){++_M_cur;if(_M_cur==_M_last){// 走到当前 buffer 末尾了_M_node++;// 跳到中控数组的下一个指针_M_first=*_M_node;_M_last=_M_first+buffer_size;_M_cur=_M_first;}return*this;}

每次++都要做一次边界检查。遍历 deque 时，这个检查的频率是每 512 个元素一次（假设 buffer 大小为 512）。听起来不多，但和 vector 的"直接指针++"相比，分支预测失败和额外内存访问的代价是实实在在的。

2.3 deque 的致命缺陷：遍历慢

PPT 里总结得很到位：deque 不适合遍历。原因有三：

1. 迭代器跨 buffer 的边界检查：每次接近 buffer 末尾都要判断，分支预测失败率高
2. 缓存不连续：虽然单个 buffer 内部连续，但 buffer 之间散落在堆上。跳转到下一个 buffer 时，大概率缓存未命中
3. 预取失效：CPU 的硬件预取器对连续内存效果好，对 deque 这种"连续一小段、跳一大段"的模式完全抓瞎

实测数据：遍历 100 万个 int，vector 通常比 deque 快 20%-50%。如果元素类型更大，差距会更明显。

2.4 那为什么 stack 和 queue 默认用 deque？

因为 stack 和 queue不需要遍历。它们的操作只有：

• stack：push_back（尾插）、pop_back（尾删）、back（访问尾部）
• queue：push_back（尾插）、pop_front（头删）、front/back（访问头尾）

deque 的弱点（遍历慢）被完美回避，而它的 strengths 全部用上：

• 头尾操作都是 O(1)：比 vector 的头删 O(N) 强太多
• 扩容不搬元素：中控数组扩容只搬指针，元素留在原地。vector 扩容要搬全部元素
• 缓存比 list 好：单个 buffer 内部连续，空间利用率远高于 list 的 24 字节节点

PPT 里的原话是"结合了 deque 的优点，而完美的避开了其缺陷"。确实如此。

三、priority_queue：堆算法的自动化外壳

priority_queue 也是容器适配器，但它的底层逻辑比 stack/queue 复杂——它不只是转发接口，还要在每次插入和删除后维护堆结构。

3.1 默认是大堆

priority_queue<int>pq;// 默认大堆，top() 返回最大元素

底层容器默认是 vector。为什么用 vector？因为堆在逻辑上是完全二叉树，物理上最好用数组存储——父节点 i 的左右孩子是 2i+1 和 2i+2。vector 的连续内存天然适合这个映射。

3.2 堆维护的三个算法

STL 提供了三个堆算法，priority_queue 内部自动调用：

make_heap：把一段无序数据变成堆

make_heap(first,last);// O(N)

时间复杂度 O(N) 不是 O(N log N)。因为它用自下而上的堆化（bottom-up heapify）：从最后一个非叶子节点开始，逐个向下调整。叶子节点不需要调整，所以实际工作量是 N/2 + N/4 + N/8 + … ≈ N。

push_heap：在堆尾插入元素后向上调整

push_heap(first,last);// O(log N)

假设堆已经有 N 个元素，vector 的push_back把新元素放到位置 N。然后push_heap让这个元素和父节点比较，如果更大就交换，一路向上冒泡到根。

pop_heap：把堆顶移到末尾，然后向下调整

pop_heap(first,last);// O(log N)

这个操作的名字很迷惑——它不是真的弹出元素。它做的是：

1. 把堆顶（first）和最后一个元素（last-1）交换
2. 对[first, last-1)这段做向下调整，恢复堆结构
3. 返回后，原来的堆顶现在在last-1，可以被pop_back()真正移除

priority_queue 的pop()内部就是pop_heap+pop_back。

3.3 为什么priority_queue的迭代器被封死了

priority_queue不提供迭代器。不是因为实现不了，而是语义上不允许。

堆的结构是"局部有序"——只保证父节点大于（或小于）子节点，不保证兄弟节点之间有序。如果你拿到迭代器遍历一遍，看到的不是有序序列，而是让人困惑的"半乱序"状态。STL 干脆不提供迭代器，避免用户误用。

如果你需要有序遍历，应该先把元素倒到 vector 里再sort，而不是用 priority_queue 的迭代器（虽然你拿不到）。

3.4 自定义比较器：大堆变小堆

// 小堆：top() 返回最小元素priority_queue<int,vector<int>,greater<int>>min_pq;

greater<int>是一个函数对象（functor），内部重载了operator()：

template<classT>structgreater{booloperator()(constT&a,constT&b)const{returna>b;}};

堆算法在比较时用comp(a, b)判断"a 的优先级是否低于 b"。greater让"大值"被视为"低优先级"，于是小值上浮到堆顶。

对于自定义类型，你需要提供operator<（用于大堆）或operator>（用于小堆）。如果两个都提供，可以灵活切换。

四、从底层看经典问题

4.1 最小栈：双栈法的空间开销

PPT 里的最小栈用两个 stack 实现：_elem存数据，_min存当前最小值。

voidpush(intx){_elem.push(x);if(_min.empty()||x<=_min.top())_min.push(x);}voidpop(){if(_min.top()==_elem.top())_min.pop();_elem.pop();}

空间复杂度不是严格的 O(N)。当输入序列单调递减时，_min和_elem一样大，O(N)。当输入单调递增时，_min只存一个元素，O(1)。平均情况下接近 O(N)。

一个优化思路：_min里不存重复值，存<值, 计数>对。但 PPT 里的版本没有做这个优化，教学代码追求简洁。

4.2 用两个栈实现队列

经典面试题。核心思想：

• 入队栈：只负责push
• 出队栈：只负责pop和front
• 当出队栈为空时，把入队栈的所有元素倒到出队栈

均摊复杂度 O(1)。最坏情况下一次pop要搬 N 个元素，但每个元素最多被搬两次（入队栈 → 出队栈 → 弹出），所以均摊下来是 O(1)。

4.3 逆波兰表达式求值

栈的经典应用。PPT 里的代码有个细节值得注意：

intright=s.top();s.pop();intleft=s.top();s.pop();s.push(left+right);

减法和除法不是交换律的，所以必须先弹出右操作数，再弹出左操作数。如果顺序反了，5 3 -会变成3 - 5 = -2，而不是正确的2。

五、性能实测：vector vs list vs deque 当 stack

虽然理论上三种容器都能当 stack 的底层，但实际性能差距明显。

写一个简单测试：连续 push 100 万个 int，然后连续 pop 100 万个 int。

// 测试框架（示意）template<classContainer>voidbench_stack(){stack<int,Container>s;for(inti=0;i<1e6;++i)s.push(i);while(!s.empty())s.pop();}

典型结果（gcc -O2，x86_64）：

vector 和 deque 在只操作尾部时性能接近，因为 deque 的尾部操作不需要跨 buffer。list 慢是因为每次new/delete节点都有堆分配开销。

但注意：如果测试包含大量交替 push/pop，deque 和 vector 的差距会拉大——vector 在临界容量时可能触发扩容，deque 的中控数组扩容只搬指针。

六、设计思想的延伸

6.1 适配器模式的通用性

stack/queue/priority_queue 都是适配器，但适配的维度不同：

• stack/queue：接口适配——裁剪底层容器的接口，只暴露 LIFO/FIFO 语义
• priority_queue：行为适配——在转发接口的同时，附加堆维护的副作用

这种分层设计让 STL 的代码复用率达到极致。stack 的源代码只有几十行，因为它把所有工作都委托给了底层容器。

6.2 "不提供迭代器"是一种设计决策

stack、queue、priority_queue 都不提供迭代器。这不是偷懒，而是接口隔离原则——只暴露用户需要的操作，隐藏可能破坏数据结构不变量的操作。

如果 stack 提供了迭代器，用户就能随便修改中间元素，破坏栈的不变量。priority_queue 如果提供迭代器，用户可能误以为遍历结果是有序的。

6.3 deque 的启示：没有银弹

deque 试图兼顾 vector 的缓存友好和 list 的头尾操作效率，结果得到了一个"两头都好、中间拉胯"的结构。遍历慢、迭代器臃肿、实现复杂——这些代价在需要线性遍历的场景下无法接受。

这告诉我们：数据结构的设计是权衡（trade-off）。deque 在 stack/queue 的场景下是完美选择，因为它回避了自己的弱点。但如果你在写一个需要频繁遍历的队列（比如滑动窗口），deque 可能不是最优解。

七、总结

搞懂 stack、queue、priority_queue 的底层，核心就这几条：

1. 它们是适配器，不是容器。所有操作都委托给底层容器，自己没有存储语义。
2. 默认底层是 deque 不是偶然。deque 的头尾 O(1) + 分段连续，完美匹配 stack/queue 的操作模式，同时回避了遍历慢的缺陷。
3. priority_queue 的堆维护是自动的。push_heap/pop_heap/make_heap三个算法撑起了所有操作，复杂度分别是 O(log N) / O(log N) / O(N)。
4. 不提供迭代器是刻意的设计。避免用户破坏数据结构的不变量，避免误用。

最后留一个思考题：如果你要设计一个"中位数队列"——支持 push、pop、以及 O(1) 查询当前队列中位数——你会怎么组合 STL 的容器和适配器？（提示：两个 priority_queue。）