手撕 STL 容器适配器：stack、queue、priority_queue 从原理到手写实现

哈喽大家好，接着上一篇 string 的节奏，今天咱们来啃三个"老朋友"：stack（栈）、queue（队列）、priority_queue（优先级队列）。

这三个东西平时用起来都很简单，push一下、pop一下就完事了。但面试时面试官一句"你自己手写一个看看"，很多人就卡壳了。

这篇文章我会先讲清楚它们为什么存在，再带着大家从底层原理一路手写实现，最后把 priority_queue 的"堆"和"仿函数"这两个难点掰开揉碎。口语化讲解，该严谨的地方不含糊，放心食用~

目录

• 一、先铺垫：为什么需要"容器适配器"？
• 二、deque：vector 和 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（栈）：只允许你从一端进、从同一端出（后进先出 LIFO）
• queue（队列）：只允许你从一端进、从另一端出（先进先出 FIFO）

底层的活，全交给被它包装的那个容器去干。所以你会发现，stack 和 queue 的代码特别短——因为大部分功能都是"转发"给底层容器的。

一句话记住：适配器 = 拿现成容器，改造成符合特定存取规则的新接口。

二、deque：vector 和 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）。

它只暴露这几个接口：

注意：stack 不支持遍历，没有迭代器，也不能访问中间元素，这是它的规则限制。

3.2 手写实现

stack 的模板长这样：template<class T, class Container = deque<T>>，第二个模板参数是底层容器，默认 deque。

#pragmaonce#include<deque>namespaceDongKes{template<classT,classContainer=deque<T>>classstack{public:// 只支持尾插：压栈voidpush(constT&x){_con.push_back(x);}// 只支持尾删：弹栈voidpop(){_con.pop_back();}// 查看栈顶constT&top()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}

3.3 几个容易忽略的点

1. 构造、拷贝构造、析构都不用自己写。因为底层容器_con是自定义类型，编译器会自动调用它自己的构造、拷贝、析构，我们只管转发增删查改就行。
2. 为什么底层选 deque 而不是 vector？因为 stack 只做尾插尾删，vector 其实也能干；选 deque 是 STL 的默认权衡，你也可以手动传 vector 当底层。

四、queue 队列：先进先出，手写实现

4.1 规则：FIFO

队列就像排队买饭：先排进去的，先出来（First In First Out）。

• push：从队尾入队（push_back）
• pop：从队头出队（pop_front）

4.2 手写实现

queue 的结构和 stack 几乎一模一样，区别只在于：入队用push_back，出队用pop_front，而且能同时看队头和队尾。

#pragmaonce#include<deque>namespaceDongKes{template<classT,classContainer=deque<T>>classqueue{public:// 队尾入队voidpush(constT&x){_con.push_back(x);}// 队头出队voidpop(){_con.pop_front();}// 查看队头constT&front()const{return_con.front();}// 查看队尾constT&back()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 < ytemplate<classT>classLess{public:booloperator()(constT&x,constT&y){returnx<y;}};// Greater：比较 x > ytemplate<classT>classGreater{public:booloperator()(constT&x,constT&y){returnx>y;}};

使用的时候你会觉得它跟函数一模一样：

Less<int>less;less(3,5);// 等价于 3 < 5，返回 true

关键规则（默认行为）：

• 不传参，或传Less<T>→建大堆
• 传Greater<T>→建小堆

这一点和标准库一致：priority_queue<T>默认就是大堆，想要小堆要显式传greater<T>。

模板签名也因此有三个参数：

template<classT,classContainer=vector<T>,classCompare=Less<T>>classpriority_queue

• 第一个：元素类型 T
• 第二个：底层容器，默认vector（堆要用下标随机访问，所以选连续的 vector，而不是 deque）
• 第三个：比较方式 Compare，默认 Less 建大堆

5.2 向上调整 AdjustUp：尾插之后往上冒泡

priority_queue只支持尾插。把新元素放到数组末尾后，要让它沿着父节点一路往上"冒泡"，直到满足堆的性质——这就是向上调整。

大堆规则：父节点应该比子节点大。如果父节点比新插入的孩子还小，就交换，继续往上比。

voidAdjustUp(intchild){Compare com;intparent=(child-1)/2;// 由孩子下标算父下标while(child>0){// com(parent, child) 即 parent < child：父比子小，违反大堆，交换if(com(_con[parent],_con[child])){swap(_con[parent],_con[child]);child=parent;parent=(child-1)/2;}else{break;// 父已经比子大，满足堆，停止}}}

push就是先尾插，再从最后一个位置向上调整：

voidpush(constT&x){_con.push_back(x);AdjustUp(_con.size()-1);}

5.3 向下调整 AdjustDown：删根之后往下沉

priority_queue只支持头删（删堆顶，也就是最大值）。但数组不能直接删第一个元素，标准做法是：

1. 把堆顶元素和最后一个元素交换
2. 删掉最后一个元素（pop_back）
3. 此时堆顶"新来"的元素位置不对，从根开始向下调整，让它一路沉到该去的地方

voidAdjustDown(intparent){Compare com;intchild=parent*2+1;// 先拿左孩子// 在两个孩子里找出较大的那个（大堆）// com(left, right) 即 left < right，说明右孩子更大，选右if(com(_con[child],_con[child+1])){child=child+1;}while(parent<(int)_con.size()){// !com(child, parent) 即 不是 child < parent，也就是 child >= parent// 孩子比父大，违反大堆，交换并继续下沉if(!com(_con[child],_con[parent])){swap(_con[child],_con[parent]);parent=child;child=parent*2+1;// 下沉过程中同样要先选出较大孩子if(child+1<(int)_con.size()&&com(_con[child],_con[child+1])){child=child+1;}}else{break;}}}

pop的三步走：

voidpop(){swap(_con[0],_con[_con.size()-1]);// 堆顶与末尾交换_con.pop_back();// 删掉末尾（原堆顶）AdjustDown(0);// 从根向下调整}

5.4 完整手写实现

把上面拼起来，就是一份完整可用的 priority_queue：

#pragmaonce#include<vector>#include<algorithm>// 仿函数：Less 建大堆，Greater 建小堆template<classT>classLess{public:booloperator()(constT&x,constT&y){returnx<y;}};template<classT>classGreater{public:booloperator()(constT&x,constT&y){returnx>y;}};namespaceDongKes{// 默认大堆：底层 vector，比较方式 Lesstemplate<classT,classContainer=vector<T>,classCompare=Less<T>>classpriority_queue{public:// 向上调整voidAdjustUp(intchild){Compare com;intparent=(child-1)/2;while(child>0){if(com(_con[parent],_con[child])){swap(_con[parent],_con[child]);child=parent;parent=(child-1)/2;}else{break;}}}// 只支持尾插，插完立刻向上调整成堆voidpush(constT&x){_con.push_back(x);AdjustUp((int)_con.size()-1);}// 向下调整voidAdjustDown(intparent){Compare com;intchild=parent*2+1;while(child<(int)_con.size()){// 选出较大的孩子if(child+1<(int)_con.size()&&com(_con[child],_con[child+1])){child=child+1;}// 孩子比父大，交换并继续下沉if(!com(_con[child],_con[parent])){swap(_con[child],_con[parent]);parent=child;child=parent*2+1;}else{break;}}}// 只支持头删：交换首尾 → 删末尾 → 向下调整voidpop(){swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}// 堆顶即最大值（大堆）constT&top()const{return_con[0];}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}

使用示例：

#include<iostream>usingnamespacestd;intmain(){DongKes::priority_queue<int>pq;// 默认大堆pq.push(3);pq.push(1);pq.push(5);pq.push(2);while(!pq.empty()){cout<<pq.top()<<" ";// 5 3 2 1，依次取出最大值pq.pop();}return0;}

六、三者对比与面试高频点

面试高频考点：

1. stack、queue 是容器还是适配器？→ 都是容器适配器，底层包装别的容器，不自己存数据。
2. 为什么 stack、queue 默认用 deque，而 priority_queue 默认用 vector？→ 前两者只操作头尾，deque 头尾都高效；堆需要频繁下标随机访问父子节点，连续的 vector 更合适。
3. priority_queue 默认大堆还是小堆？→ 默认大堆（Less），要小堆传greater<T>。
4. 什么是仿函数？→ 重载了()的类对象，能像函数一样调用，在这里用来封装"比较规则"，让同一份堆代码能灵活切换大小堆。
5. push 和 pop 分别用什么调整？→ push 尾插后向上调整，pop 交换首尾删末尾后向下调整。
6. stack/queue 有迭代器吗？能遍历吗？→ 没有，也不允许遍历，这是规则本身的限制。

七、总结

咱们快速回顾一下：

1. 容器适配器：自己不存数据，包装现成容器并限定存取规则，stack、queue 都是。
2. deque：vector 和 list 的折中缝合，头尾高效、中间插入慢，所以被 stack、queue 默认选用。
3. stack（LIFO）：push_back压栈、pop_back弹栈、top看栈顶，纯转发。
4. queue（FIFO）：push_back入队、pop_front出队，能看队头队尾。
5. priority_queue：底层是堆，默认 vector + Less 建大堆；push向上调整，pop交换首尾后向下调整；仿函数()封装比较规则，切换大小堆。

把这三份手写实现敲一遍、跑一遍，再对着调整算法画几棵堆的示意图，这一块面试基本就稳了。

如果这篇对你有帮助，别忘了点赞收藏关注~ 后面有机会单独把 deque 的内部结构和 priority_queue 的 top-K 经典题补上，咱们下篇见！

参考：STL 标准库 stack / queue / priority_queue 接口与实现思路