手撕 STL 容器适配器stack、queue、priority_queue 从原理到手写实现哈喽大家好接着上一篇 string 的节奏今天咱们来啃三个老朋友stack栈、queue队列、priority_queue优先级队列。这三个东西平时用起来都很简单push一下、pop一下就完事了。但面试时面试官一句你自己手写一个看看很多人就卡壳了。这篇文章我会先讲清楚它们为什么存在再带着大家从底层原理一路手写实现最后把 priority_queue 的堆和仿函数这两个难点掰开揉碎。口语化讲解该严谨的地方不含糊放心食用~目录一、先铺垫为什么需要容器适配器二、dequevector 和 list 的缝合怪三、stack 栈后进先出手写实现四、queue 队列先进先出手写实现五、priority_queue本质就是一座堆5.1 大堆与小堆仿函数 Less / Greater 说了算5.2 向上调整 AdjustUp尾插之后往上冒泡5.3 向下调整 AdjustDown删根之后往下沉5.4 完整手写实现六、三者对比与面试高频点七、总结一、先铺垫为什么需要容器适配器在正式写代码之前咱们先回答一个问题STL 里已经有 vector、list 这些容器了为什么还要再搞出 stack、queue答案是stack 和 queue 本身不是容器它们叫容器适配器Container Adapter。什么意思呢它们自己不存数据而是包一层别的容器只对外暴露一套符合特定规则的接口。stack栈只允许你从一端进、从同一端出后进先出 LIFOqueue队列只允许你从一端进、从另一端出先进先出 FIFO底层的活全交给被它包装的那个容器去干。所以你会发现stack 和 queue 的代码特别短——因为大部分功能都是转发给底层容器的。一句话记住适配器 拿现成容器改造成符合特定存取规则的新接口。二、dequevector 和 list 的缝合怪既然 stack、queue 要包装一个底层容器那默认包装谁呢答案是deque双端队列。要理解 deque咱们先回头看看 vector 和 list 各自的优缺点vector顺序表优点尾插尾删效率高支持高效的下标随机访问物理空间连续CPU 高速缓存利用率高缺点需要扩容存在空间浪费和扩容开销头插、中间插入删除要挪动数据效率低list链表优点按需申请空间不用扩容任意位置插入删除没有挪动负担缺点不支持下标随机访问找节点不方便物理空间不连续缓存利用率低你发现没有这俩简直是优缺点互补。那能不能把它们缝合起来造一个完美结构deque 应运而生它就是顺序表和链表的折中缝合体头尾插效率都很好支持下标访问虽然还行但不如 vector 快中间插入效率依然很低还是要挪动数据时间复杂度 O(N)也正因为 deque 两头都不极致它没能取代 vector 和 list但它有一个独特优势头尾操作都高效。而 stack、queue 恰好只需要操作头尾所以 deque 就成了它们的默认底层容器。这篇先不深入 deque 的内部结构中控器、分段连续那一套有机会单独出一篇细讲。这里你只要记住stack、queue 默认底层是 deque就够了。三、stack 栈后进先出手写实现3.1 规则LIFO栈就像一摞盘子你只能从最上面放盘子、拿盘子最后放进去的最先拿出来Last In First Out。它只暴露这几个接口接口作用push(x)尾插压栈pop()尾删弹栈top()查看栈顶元素size()元素个数empty()是否为空注意stack 不支持遍历没有迭代器也不能访问中间元素这是它的规则限制。3.2 手写实现stack 的模板长这样templateclass T, class Container dequeT第二个模板参数是底层容器默认 deque。#pragmaonce#includedequenamespaceDongKes{templateclassT,classContainerdequeTclassstack{public:// 只支持尾插压栈voidpush(constTx){_con.push_back(x);}// 只支持尾删弹栈voidpop(){_con.pop_back();}// 查看栈顶constTtop()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}3.3 几个容易忽略的点构造、拷贝构造、析构都不用自己写。因为底层容器_con是自定义类型编译器会自动调用它自己的构造、拷贝、析构我们只管转发增删查改就行。为什么底层选 deque 而不是 vector因为 stack 只做尾插尾删vector 其实也能干选 deque 是 STL 的默认权衡你也可以手动传 vector 当底层。四、queue 队列先进先出手写实现4.1 规则FIFO队列就像排队买饭先排进去的先出来First In First Out。push从队尾入队push_backpop从队头出队pop_front接口作用push(x)队尾入队pop()队头出队front()查看队头back()查看队尾size()元素个数empty()是否为空4.2 手写实现queue 的结构和 stack 几乎一模一样区别只在于入队用push_back出队用pop_front而且能同时看队头和队尾。#pragmaonce#includedequenamespaceDongKes{templateclassT,classContainerdequeTclassqueue{public:// 队尾入队voidpush(constTx){_con.push_back(x);}// 队头出队voidpop(){_con.pop_front();}// 查看队头constTfront()const{return_con.front();}// 查看队尾constTback()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}对比一下你就懂了stack 和 queue 的骨架完全相同都是包一个 deque转发几个方法差别只在从哪头进、从哪头出。五、priority_queue本质就是一座堆终于到了本篇的重头戏。priority_queue优先级队列比前两个复杂因为它的底层不是简单包装而是建了一座堆。5.1 大堆与小堆仿函数 Less / Greater 说了算先说两个概念大堆大顶堆堆顶是整个堆里最大的元素每次top()拿到最大值小堆小顶堆堆顶是整个堆里最小的元素每次top()拿到最小值那怎么控制建大堆还是小堆STL 用了一个非常优雅的设计——仿函数functor。什么是仿函数就是一个类或结构体重载了函数调用运算符()让这个类的对象用起来像函数一样可以调用。// Less比较 x ytemplateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};// Greater比较 x ytemplateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};使用的时候你会觉得它跟函数一模一样Lessintless;less(3,5);// 等价于 3 5返回 true关键规则默认行为不传参或传LessT→建大堆传GreaterT→建小堆这一点和标准库一致priority_queueT默认就是大堆想要小堆要显式传greaterT。模板签名也因此有三个参数templateclassT,classContainervectorT,classCompareLessTclasspriority_queue第一个元素类型 T第二个底层容器默认vector堆要用下标随机访问所以选连续的 vector而不是 deque第三个比较方式 Compare默认 Less 建大堆5.2 向上调整 AdjustUp尾插之后往上冒泡priority_queue只支持尾插。把新元素放到数组末尾后要让它沿着父节点一路往上冒泡直到满足堆的性质——这就是向上调整。大堆规则父节点应该比子节点大。如果父节点比新插入的孩子还小就交换继续往上比。voidAdjustUp(intchild){Compare com;intparent(child-1)/2;// 由孩子下标算父下标while(child0){// com(parent, child) 即 parent child父比子小违反大堆交换if(com(_con[parent],_con[child])){swap(_con[parent],_con[child]);childparent;parent(child-1)/2;}else{break;// 父已经比子大满足堆停止}}}push就是先尾插再从最后一个位置向上调整voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}5.3 向下调整 AdjustDown删根之后往下沉priority_queue只支持头删删堆顶也就是最大值。但数组不能直接删第一个元素标准做法是把堆顶元素和最后一个元素交换删掉最后一个元素pop_back此时堆顶新来的元素位置不对从根开始向下调整让它一路沉到该去的地方voidAdjustDown(intparent){Compare com;intchildparent*21;// 先拿左孩子// 在两个孩子里找出较大的那个大堆// com(left, right) 即 left right说明右孩子更大选右if(com(_con[child],_con[child1])){childchild1;}while(parent(int)_con.size()){// !com(child, parent) 即 不是 child parent也就是 child parent// 孩子比父大违反大堆交换并继续下沉if(!com(_con[child],_con[parent])){swap(_con[child],_con[parent]);parentchild;childparent*21;// 下沉过程中同样要先选出较大孩子if(child1(int)_con.size()com(_con[child],_con[child1])){childchild1;}}else{break;}}}pop的三步走voidpop(){swap(_con[0],_con[_con.size()-1]);// 堆顶与末尾交换_con.pop_back();// 删掉末尾原堆顶AdjustDown(0);// 从根向下调整}5.4 完整手写实现把上面拼起来就是一份完整可用的 priority_queue#pragmaonce#includevector#includealgorithm// 仿函数Less 建大堆Greater 建小堆templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};namespaceDongKes{// 默认大堆底层 vector比较方式 LesstemplateclassT,classContainervectorT,classCompareLessTclasspriority_queue{public:// 向上调整voidAdjustUp(intchild){Compare com;intparent(child-1)/2;while(child0){if(com(_con[parent],_con[child])){swap(_con[parent],_con[child]);childparent;parent(child-1)/2;}else{break;}}}// 只支持尾插插完立刻向上调整成堆voidpush(constTx){_con.push_back(x);AdjustUp((int)_con.size()-1);}// 向下调整voidAdjustDown(intparent){Compare com;intchildparent*21;while(child(int)_con.size()){// 选出较大的孩子if(child1(int)_con.size()com(_con[child],_con[child1])){childchild1;}// 孩子比父大交换并继续下沉if(!com(_con[child],_con[parent])){swap(_con[child],_con[parent]);parentchild;childparent*21;}else{break;}}}// 只支持头删交换首尾 → 删末尾 → 向下调整voidpop(){swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}// 堆顶即最大值大堆constTtop()const{return_con[0];}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}使用示例#includeiostreamusingnamespacestd;intmain(){DongKes::priority_queueintpq;// 默认大堆pq.push(3);pq.push(1);pq.push(5);pq.push(2);while(!pq.empty()){coutpq.top() ;// 5 3 2 1依次取出最大值pq.pop();}return0;}六、三者对比与面试高频点对比项stackqueuepriority_queue存取规则后进先出 LIFO先进先出 FIFO每次取堆顶最值底层默认容器dequedequevector插入位置尾插尾插队尾尾插删除位置尾删头删队头头删堆顶核心算法无纯转发无纯转发向上/向下调整建堆比较方式无无Less 大堆 / Greater 小堆面试高频考点stack、queue 是容器还是适配器→ 都是容器适配器底层包装别的容器不自己存数据。为什么 stack、queue 默认用 deque而 priority_queue 默认用 vector→ 前两者只操作头尾deque 头尾都高效堆需要频繁下标随机访问父子节点连续的 vector 更合适。priority_queue 默认大堆还是小堆→ 默认大堆Less要小堆传greaterT。什么是仿函数→ 重载了()的类对象能像函数一样调用在这里用来封装比较规则让同一份堆代码能灵活切换大小堆。push 和 pop 分别用什么调整→ push 尾插后向上调整pop 交换首尾删末尾后向下调整。stack/queue 有迭代器吗能遍历吗→ 没有也不允许遍历这是规则本身的限制。七、总结咱们快速回顾一下容器适配器自己不存数据包装现成容器并限定存取规则stack、queue 都是。dequevector 和 list 的折中缝合头尾高效、中间插入慢所以被 stack、queue 默认选用。stackLIFOpush_back压栈、pop_back弹栈、top看栈顶纯转发。queueFIFOpush_back入队、pop_front出队能看队头队尾。priority_queue底层是堆默认 vector Less 建大堆push向上调整pop交换首尾后向下调整仿函数()封装比较规则切换大小堆。把这三份手写实现敲一遍、跑一遍再对着调整算法画几棵堆的示意图这一块面试基本就稳了。如果这篇对你有帮助别忘了点赞收藏关注~ 后面有机会单独把 deque 的内部结构和 priority_queue 的 top-K 经典题补上咱们下篇见参考STL 标准库 stack / queue / priority_queue 接口与实现思路 
长河君 · 2026/10/29 2:01:36 · 阅读 1.2k 手撕 STL 容器适配器：stack、queue、priority_queue 从原理到手写实现
手撕 STL 容器适配器stack、queue、priority_queue 从原理到手写实现哈喽大家好接着上一篇 string 的节奏今天咱们来啃三个老朋友stack栈、queue队列、priority_queue优先级队列。这三个东西平时用起来都很简单push一下、pop一下就完事了。但面试时面试官一句你自己手写一个看看很多人就卡壳了。这篇文章我会先讲清楚它们为什么存在再带着大家从底层原理一路手写实现最后把 priority_queue 的堆和仿函数这两个难点掰开揉碎。口语化讲解该严谨的地方不含糊放心食用~目录一、先铺垫为什么需要容器适配器二、dequevector 和 list 的缝合怪三、stack 栈后进先出手写实现四、queue 队列先进先出手写实现五、priority_queue本质就是一座堆5.1 大堆与小堆仿函数 Less / Greater 说了算5.2 向上调整 AdjustUp尾插之后往上冒泡5.3 向下调整 AdjustDown删根之后往下沉5.4 完整手写实现六、三者对比与面试高频点七、总结一、先铺垫为什么需要容器适配器在正式写代码之前咱们先回答一个问题STL 里已经有 vector、list 这些容器了为什么还要再搞出 stack、queue答案是stack 和 queue 本身不是容器它们叫容器适配器Container Adapter。什么意思呢它们自己不存数据而是包一层别的容器只对外暴露一套符合特定规则的接口。stack栈只允许你从一端进、从同一端出后进先出 LIFOqueue队列只允许你从一端进、从另一端出先进先出 FIFO底层的活全交给被它包装的那个容器去干。所以你会发现stack 和 queue 的代码特别短——因为大部分功能都是转发给底层容器的。一句话记住适配器 拿现成容器改造成符合特定存取规则的新接口。二、dequevector 和 list 的缝合怪既然 stack、queue 要包装一个底层容器那默认包装谁呢答案是deque双端队列。要理解 deque咱们先回头看看 vector 和 list 各自的优缺点vector顺序表优点尾插尾删效率高支持高效的下标随机访问物理空间连续CPU 高速缓存利用率高缺点需要扩容存在空间浪费和扩容开销头插、中间插入删除要挪动数据效率低list链表优点按需申请空间不用扩容任意位置插入删除没有挪动负担缺点不支持下标随机访问找节点不方便物理空间不连续缓存利用率低你发现没有这俩简直是优缺点互补。那能不能把它们缝合起来造一个完美结构deque 应运而生它就是顺序表和链表的折中缝合体头尾插效率都很好支持下标访问虽然还行但不如 vector 快中间插入效率依然很低还是要挪动数据时间复杂度 O(N)也正因为 deque 两头都不极致它没能取代 vector 和 list但它有一个独特优势头尾操作都高效。而 stack、queue 恰好只需要操作头尾所以 deque 就成了它们的默认底层容器。这篇先不深入 deque 的内部结构中控器、分段连续那一套有机会单独出一篇细讲。这里你只要记住stack、queue 默认底层是 deque就够了。三、stack 栈后进先出手写实现3.1 规则LIFO栈就像一摞盘子你只能从最上面放盘子、拿盘子最后放进去的最先拿出来Last In First Out。它只暴露这几个接口接口作用push(x)尾插压栈pop()尾删弹栈top()查看栈顶元素size()元素个数empty()是否为空注意stack 不支持遍历没有迭代器也不能访问中间元素这是它的规则限制。3.2 手写实现stack 的模板长这样templateclass T, class Container dequeT第二个模板参数是底层容器默认 deque。#pragmaonce#includedequenamespaceDongKes{templateclassT,classContainerdequeTclassstack{public:// 只支持尾插压栈voidpush(constTx){_con.push_back(x);}// 只支持尾删弹栈voidpop(){_con.pop_back();}// 查看栈顶constTtop()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}3.3 几个容易忽略的点构造、拷贝构造、析构都不用自己写。因为底层容器_con是自定义类型编译器会自动调用它自己的构造、拷贝、析构我们只管转发增删查改就行。为什么底层选 deque 而不是 vector因为 stack 只做尾插尾删vector 其实也能干选 deque 是 STL 的默认权衡你也可以手动传 vector 当底层。四、queue 队列先进先出手写实现4.1 规则FIFO队列就像排队买饭先排进去的先出来First In First Out。push从队尾入队push_backpop从队头出队pop_front接口作用push(x)队尾入队pop()队头出队front()查看队头back()查看队尾size()元素个数empty()是否为空4.2 手写实现queue 的结构和 stack 几乎一模一样区别只在于入队用push_back出队用pop_front而且能同时看队头和队尾。#pragmaonce#includedequenamespaceDongKes{templateclassT,classContainerdequeTclassqueue{public:// 队尾入队voidpush(constTx){_con.push_back(x);}// 队头出队voidpop(){_con.pop_front();}// 查看队头constTfront()const{return_con.front();}// 查看队尾constTback()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}对比一下你就懂了stack 和 queue 的骨架完全相同都是包一个 deque转发几个方法差别只在从哪头进、从哪头出。五、priority_queue本质就是一座堆终于到了本篇的重头戏。priority_queue优先级队列比前两个复杂因为它的底层不是简单包装而是建了一座堆。5.1 大堆与小堆仿函数 Less / Greater 说了算先说两个概念大堆大顶堆堆顶是整个堆里最大的元素每次top()拿到最大值小堆小顶堆堆顶是整个堆里最小的元素每次top()拿到最小值那怎么控制建大堆还是小堆STL 用了一个非常优雅的设计——仿函数functor。什么是仿函数就是一个类或结构体重载了函数调用运算符()让这个类的对象用起来像函数一样可以调用。// Less比较 x ytemplateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};// Greater比较 x ytemplateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};使用的时候你会觉得它跟函数一模一样Lessintless;less(3,5);// 等价于 3 5返回 true关键规则默认行为不传参或传LessT→建大堆传GreaterT→建小堆这一点和标准库一致priority_queueT默认就是大堆想要小堆要显式传greaterT。模板签名也因此有三个参数templateclassT,classContainervectorT,classCompareLessTclasspriority_queue第一个元素类型 T第二个底层容器默认vector堆要用下标随机访问所以选连续的 vector而不是 deque第三个比较方式 Compare默认 Less 建大堆5.2 向上调整 AdjustUp尾插之后往上冒泡priority_queue只支持尾插。把新元素放到数组末尾后要让它沿着父节点一路往上冒泡直到满足堆的性质——这就是向上调整。大堆规则父节点应该比子节点大。如果父节点比新插入的孩子还小就交换继续往上比。voidAdjustUp(intchild){Compare com;intparent(child-1)/2;// 由孩子下标算父下标while(child0){// com(parent, child) 即 parent child父比子小违反大堆交换if(com(_con[parent],_con[child])){swap(_con[parent],_con[child]);childparent;parent(child-1)/2;}else{break;// 父已经比子大满足堆停止}}}push就是先尾插再从最后一个位置向上调整voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}5.3 向下调整 AdjustDown删根之后往下沉priority_queue只支持头删删堆顶也就是最大值。但数组不能直接删第一个元素标准做法是把堆顶元素和最后一个元素交换删掉最后一个元素pop_back此时堆顶新来的元素位置不对从根开始向下调整让它一路沉到该去的地方voidAdjustDown(intparent){Compare com;intchildparent*21;// 先拿左孩子// 在两个孩子里找出较大的那个大堆// com(left, right) 即 left right说明右孩子更大选右if(com(_con[child],_con[child1])){childchild1;}while(parent(int)_con.size()){// !com(child, parent) 即 不是 child parent也就是 child parent// 孩子比父大违反大堆交换并继续下沉if(!com(_con[child],_con[parent])){swap(_con[child],_con[parent]);parentchild;childparent*21;// 下沉过程中同样要先选出较大孩子if(child1(int)_con.size()com(_con[child],_con[child1])){childchild1;}}else{break;}}}pop的三步走voidpop(){swap(_con[0],_con[_con.size()-1]);// 堆顶与末尾交换_con.pop_back();// 删掉末尾原堆顶AdjustDown(0);// 从根向下调整}5.4 完整手写实现把上面拼起来就是一份完整可用的 priority_queue#pragmaonce#includevector#includealgorithm// 仿函数Less 建大堆Greater 建小堆templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};namespaceDongKes{// 默认大堆底层 vector比较方式 LesstemplateclassT,classContainervectorT,classCompareLessTclasspriority_queue{public:// 向上调整voidAdjustUp(intchild){Compare com;intparent(child-1)/2;while(child0){if(com(_con[parent],_con[child])){swap(_con[parent],_con[child]);childparent;parent(child-1)/2;}else{break;}}}// 只支持尾插插完立刻向上调整成堆voidpush(constTx){_con.push_back(x);AdjustUp((int)_con.size()-1);}// 向下调整voidAdjustDown(intparent){Compare com;intchildparent*21;while(child(int)_con.size()){// 选出较大的孩子if(child1(int)_con.size()com(_con[child],_con[child1])){childchild1;}// 孩子比父大交换并继续下沉if(!com(_con[child],_con[parent])){swap(_con[child],_con[parent]);parentchild;childparent*21;}else{break;}}}// 只支持头删交换首尾 → 删末尾 → 向下调整voidpop(){swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}// 堆顶即最大值大堆constTtop()const{return_con[0];}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}使用示例#includeiostreamusingnamespacestd;intmain(){DongKes::priority_queueintpq;// 默认大堆pq.push(3);pq.push(1);pq.push(5);pq.push(2);while(!pq.empty()){coutpq.top() ;// 5 3 2 1依次取出最大值pq.pop();}return0;}六、三者对比与面试高频点对比项stackqueuepriority_queue存取规则后进先出 LIFO先进先出 FIFO每次取堆顶最值底层默认容器dequedequevector插入位置尾插尾插队尾尾插删除位置尾删头删队头头删堆顶核心算法无纯转发无纯转发向上/向下调整建堆比较方式无无Less 大堆 / Greater 小堆面试高频考点stack、queue 是容器还是适配器→ 都是容器适配器底层包装别的容器不自己存数据。为什么 stack、queue 默认用 deque而 priority_queue 默认用 vector→ 前两者只操作头尾deque 头尾都高效堆需要频繁下标随机访问父子节点连续的 vector 更合适。priority_queue 默认大堆还是小堆→ 默认大堆Less要小堆传greaterT。什么是仿函数→ 重载了()的类对象能像函数一样调用在这里用来封装比较规则让同一份堆代码能灵活切换大小堆。push 和 pop 分别用什么调整→ push 尾插后向上调整pop 交换首尾删末尾后向下调整。stack/queue 有迭代器吗能遍历吗→ 没有也不允许遍历这是规则本身的限制。七、总结咱们快速回顾一下容器适配器自己不存数据包装现成容器并限定存取规则stack、queue 都是。dequevector 和 list 的折中缝合头尾高效、中间插入慢所以被 stack、queue 默认选用。stackLIFOpush_back压栈、pop_back弹栈、top看栈顶纯转发。queueFIFOpush_back入队、pop_front出队能看队头队尾。priority_queue底层是堆默认 vector Less 建大堆push向上调整pop交换首尾后向下调整仿函数()封装比较规则切换大小堆。把这三份手写实现敲一遍、跑一遍再对着调整算法画几棵堆的示意图这一块面试基本就稳了。如果这篇对你有帮助别忘了点赞收藏关注~ 后面有机会单独把 deque 的内部结构和 priority_queue 的 top-K 经典题补上咱们下篇见参考STL 标准库 stack / queue / priority_queue 接口与实现思路