引言C 标准模板库STL中stack、queue和priority_queue是三个非常实用的容器。初学者往往只知道怎么用——push、pop、top却很少思考它们的底层是怎么工作的。实际上它们并不真正存储数据而是站在其他容器的肩膀上通过限制接口和封装来实现特定行为。这种设计模式叫做容器适配器Container Adapter。比如 stack 默认依赖 deque但也可以换成 vector 或 listqueue 默认也是 deque却不能直接使用 vector因为 pop_front 效率太低而 priority_queue 则不同它默认基于 vector并在其上构建了堆结构来保证每次取出的都是最大或最小元素。理解这三者的底层实现是吃透 C 容器适配器的关键。本文将从 deque 的存储结构讲起再到堆的向上/向下调整算法最后带你一步步手撕stack、queue和priority_queue的完整代码。deque双端队列什么是 dequedequedouble-ended queue双端队列是一种可以在头尾两端进行常数时间插入和删除操作的序列容器。它在C STL中的声明在deque头文件中。deque结合了vector的随机访问能力和 list 的头尾操作高效优点是stack和queue默认底层容器的理想选择。deque并不是一块连续的大内存而是由一段段固定大小的连续缓冲区buffer组成并通过一个中控器map来管理这些缓冲区。中控器map一个指针数组每个元素指向一块缓冲区缓冲区buffer一段连续的固定长度内存默认大小通常为 512 字节 / 元素大小迭代器deque 的迭代器内部维护了四个指针——cur当前元素、first缓冲区首、last缓冲区尾、node指向中控器中的位置实现跨缓冲区遍历deque 的迭代器深入解析迭代器的内部结构deque 的迭代器不是普通的指针而是一个自定义类内部维护了四个指针struct__deque_iterator{T*cur;// 当前指向的元素T*first;// 当前缓冲区的起始位置T*last;// 当前缓冲区的结束位置末尾哨兵map_pointer node;// 指向中控器中当前缓冲区的指针};cur迭代器当前指向的具体元素first / last当前所在缓冲区的[first, last)范围用来判断是否走到缓冲区边界node指向中控器map中对应的元素即map[pos]用于跨缓冲区跳转迭代器如何在缓冲区内部移动前移()selfoperator(){cur;// 先移动到下一个元素if(curlast){// 是否走到了当前缓冲区的末尾set_node(node1);// 切换到下一个缓冲区curfirst;// cur 指向新缓冲区的开头}return*this;}后移–itselfoperator--(){if(curfirst){// 是否走到了当前缓冲区的开头set_node(node-1);// 切换到上一个缓冲区curlast;// cur 指向新缓冲区的末尾}--cur;// 再往前走一个元素return*this;}跨缓冲区跳转set_nodevoidset_node(map_pointer new_node){nodenew_node;first*new_node;// 新缓冲区的起始lastfirstbuffer_size();// 新缓冲区的末尾}随机访问n / -ndeque 迭代器支持 it n 的随机访问计算比 vector 复杂得多selfoperator(difference_type n){difference_type offsetn(cur-first);if(offset0offsetdifference_type(buffer_size()))curn;// 没跨缓冲区直接偏移else{// 跨了缓冲区需要计算跳到哪个缓冲区difference_type node_offsetoffset0?offset/buffer_size():-((-offset-1)/buffer_size())-1;set_node(nodenode_offset);// 计算在新缓冲区中的偏移curfirst(offset-node_offset*buffer_size());}return*this;}这也是为什么deque的operator[]是O(1)但常数比vector大——需要做一次除法和取模计算目标位置所在的缓冲区和偏移。stack 的模拟实现什么是 stack栈stack是一种先进后出FILO的数据结构。元素只能从栈顶一端插入和删除就像一摞盘子——你永远只能拿走最上面的那个。STL 的 stack 本身并不存储数据而是适配到底层容器上通过限制接口来实现栈的行为。容器适配器的概念templateclassT,classCondequeTclassstack{...};第二个模板参数Con就是底层容器默认是dequeT。这意味着stack并不关心数据怎么存它只是把底层容器的某些接口包装成自己的语义push→ 调用底层容器的push_backpop→ 调用底层容器的pop_backtop→ 调用底层容器的back你也可以传入其他容器只要它支持 push_back、pop_back、back 等操作stackint, vectorint st; // 用vector做底层stackint, listint st; // 用list做底层完整代码实现#pragmaonce#includedequenamespacezy{templateclassT,classCondequeTclassstack{public:stack(){}voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_back();}Ttop(){return_c.back();}constTtop()const{return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};}关键点说明push直接尾插——栈顶就是底层容器的尾部pop尾删——移除栈顶元素top返回back()——即底层容器的最后一个元素为什么用 deque 而不是 vector虽然 vector 也能做同样的操作但 deque 在扩容时不需要搬移旧数据性能更优并且如果用户想用 list 替换deque 的接口天然兼容queue 的模拟实现什么是 queue队列queue是一种先进先出FIFO的数据结构。元素从队尾入队从队头出队就像排队买票——先到的人先服务。与 stack 的不同queue需要在两端操作push队尾插入 →push_backpop队头删除 →pop_front这就排除了vector作为默认容器的可能因为vector没有pop_front即使手动erase头部也是O(n)的。完整代码实现#pragmaonce#includedequenamespacezy{templateclassT,classCondequeTclassqueue{public:queue(){}voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_front();}Tback(){return_c.back();}constTback()const{return_c.back();}Tfront(){return_c.front();}constTfront()const{return_c.front();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};}关键点说明back和front分别对应底层容器的back()和front()因为queue需要同时访问队头和队尾默认不能用vectorvector的erase( begin() )是O(n)不符合queue的O(1)要求可以换成listlist同时支持push_back、pop_front、front、back完全胜任stack 与 queue 对比小结stackqueue数据流向一端进出后进先出两端操作先进先出pushpush_backpush_backpoppop_backpop_front访问top() back()front() back()默认容器dequedeque可选容器vector / list / dequelist / deque不能用 vector堆的向上调整与向下调整priority_queue优先级队列的底层核心就是堆。在正式看代码之前必须先理解堆的这两个关键操作。什么是堆堆是一棵完全二叉树用数组存储时满足大堆大根堆任意节点的值 ≥ 其子节点的值根节点是最大值小堆小根堆任意节点的值 ≤ 其子节点的值根节点是最小值父子节点的下标关系数组从 0 开始parent (kid - 1) / 2leftKid parent * 2 1rightKid parent * 2 2向上调整adjust_up场景向堆中插入一个新元素插入到数组末尾需要将其调整到正确位置以维持堆结构。过程从新插入的节点最后一个元素开始与父节点比较如果当前节点比父节点更优先大堆中更大/小堆中更小则交换向上走到父节点位置重复步骤 2直到到达根节点或不再需要交换代码实现voidadjust_up(intkid){intparent(kid-1)/2;while(kid0){if(comp(_c[parent],_c[kid]))// 如果父节点小于子节点则交换{std::swap(_c[kid],_c[parent]);kidparent;parent(kid-1)/2;}else{break;}}}向下调整adjust_down场景删除堆顶元素最大值/最小值将最后一个元素移到堆顶然后向下调整从一个无序数组构建堆从最后一个非叶子节点开始向下调整过程以大堆为例从指定节点通常是根节点开始找出当前节点及其左右子节点中最大的那个如果当前节点不是最大的则与最大子节点交换向下走到交换后的子节点位置重复上述步骤直到到达叶子节点或当前节点就是最大的代码实现voidadjust_down(){intparent0;intkidparent*21;// 默认先选左孩子while(kid_c.size()){// 如果右孩子存在且右孩子比左孩子更优先则选右孩子if(kid1size()comp(_c[kid],_c[kid1])){kid;}// 如果父节点小于子节点则交换if(comp(_c[parent],_c[kid])){std::swap(_c[kid],_c[parent]);parentkid;kidparent*21;}else{break;}}}两个操作的时间复杂度都是*O(log n)*这也是堆排序和优先级队列高效的关键。这里补充一下无序建堆从最后一个非叶子节点开始向前做向下调整时间复杂度 O(n)。无序数组快速建堆for (int i (n - 1 - 1) / 2; i 0; i--){adjust_down(i);}向下调整从底部的非叶子节点开始往前走到根 → 先把底层的小堆建好上层再往下调整时下面的子树已经合法了adjust_down(i) 的前提是i 的左右子树已经是堆。仿函数Functor什么是仿函数仿函数是一个重载了operator()的类对象它可以像函数一样被调用。在priority_queue中仿函数用于决定元素的优先级比较规则。为什么需要仿函数如果直接用或硬编码比较逻辑那么最大堆和最小堆需要写两份重复的代码。使用仿函数作为模板参数可以在不修改算法代码的前提下通过传入不同的仿函数来改变比较行为。实现 Greater 和 Less// Less判断 a b用于构建大堆父节点小于子节点时交换templateclassTclassLess{public:booloperator()(constTa,constTb){returnab;}};// Greater判断 a b用于构建小堆templateclassTclassGreater{public:booloperator()(constTa,constTb){returnab;}};使用示例Lessintls;coutls(3,5)endl;// 输出 1true因为 3 5Greaterintgt;coutgt(3,5)endl;// 输出 0false因为 3 5 为假在 priority_queue 中的使用templateclassT,classContainervectorT,classCompareLessTclasspriority_queue{// ...Compare comp;// 仿函数成员// ...};比较时用 comp(a, b) 代替 a bcomp LessT → comp(a, b) 等价于 a b → 大堆小的往下沉大的浮上来comp GreaterT → comp(a, b) 等价于 a b → 小堆大的往下沉小的浮上来之所以仿函数能内联是因为comp(a, b)在编译期就确定了具体类型LessT或GreaterT编译器可以直接内联operator()的调用而函数指针需要运行时间接寻址。priority_queue 的模拟实现什么是priority_queue优先级队列priority_queue是一种允许以任意顺序插入元素但总是取出优先级最高元素的容器适配器。它的底层数据结构就是堆——默认是大堆堆顶始终是最大值。当调用pop()时堆顶元素被移除并重新调整堆当调用top()时返回堆顶元素。完整代码实现#pragmaonce#includevector#includefunctionalnamespacezy{// 仿函数用于比较两个元素templateclassTclassLess{public:booloperator()(constTa,constTb){returnab;}};templateclassTclassGreater{public:booloperator()(constTa,constTb){returnab;}};templateclassT,classContainervectorT,classCompareLessTclasspriority_queue{public:priority_queue(){}// 迭代器区间构造函数快速建堆O(n) 向下调整templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last):_c(first,last){for(inti(_c.size()-1-1)/2;i0;--i){adjust_down(i);}}voidpush(constTx){_c.push_back(x);// 尾插adjust_up(_c.size()-1);// 向上调整}voidpop(){std::swap(_c[0],_c[_c.size()-1]);// 堆顶与最后一个元素交换_c.pop_back();// 删除堆顶原最后一个元素adjust_down(0);// 从根开始向下调整}Ttop(){return_c[0];}constTtop()const{return_c[0];}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:voidadjust_up(intkid){intparent(kid-1)/2;while(kid0){if(comp(_c[parent],_c[kid])){std::swap(_c[kid],_c[parent]);kidparent;parent(kid-1)/2;}else{break;}}}voidadjust_down(intparent){intkidparent*21;while(kid_c.size()){if(kid1_c.size()comp(_c[kid],_c[kid1])){kid;}if(comp(_c[parent],_c[kid])){std::swap(_c[kid],_c[parent]);parentkid;kidparent*21;}else{break;}}}private:Container _c;Compare comp;};}关键点说明默认模板参数Compare LessT用Less作为大堆最大堆当_c[parent] _c[kid]时交换大的元素向上浮。//Lessa b返回true→ 父小于子就交换 → 大堆priority_queueint pq;// 大堆priority_queueint, vectorint, Greaterint pq;// 小堆pop()的三步操作第一步堆顶与末尾交换第二步删除末尾第三步向下调整根节点迭代器区间构造函数templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last):_c(first,last)// 直接用数据初始化底层容器{// 从最后一个非叶子节点开始向下调整for(inti(_c.size()-1-1)/2;i0;--i){adjust_down(i);}}先用传入区间构造vector再统一向下调整建堆。时间复杂度O(n)比一个个push的O(n log n)更优。总结从 deque 的底层结构到堆的调整算法再到三个容器适配器的完整实现贯穿其中的设计思想是复用与适配stack 和 queue 复用了 deque 的线性操作通过限制接口得到特定的数据结构priority_queue 复用了 vector 的随机访问能力在上面构建了堆仿函数将比较策略抽象出来让同一份算法代码同时支持大堆和小堆理解容器的底层才能更好地使用容器。 希望这篇文章能帮你彻底搞懂这三个适配器的来龙去脉。谢谢大家观看
