0.1 概述&序言

这里是白杨。上一篇把 list 从用法到手写实现走了个全套。这篇进入 STL 第四站：stack 和 queue。

这篇要过五件事：

• stack / queue 的用法和经典实战（最小栈）
• 容器适配器思想：它俩为什么算"套壳"，不算容器
• 手写模拟实现 + 换底层实测
• priority_queue：堆的用法与手写实现
• deque 初探：为什么标准库默认拿它当底层

老规矩，跑得通的结果才写进来（环境见下）；完整代码文末自取，也可以直接去仓库：gitee.com/BaiYang_SQ/stack-queue-sim。

实测环境：w64devkit g++ 15.2.0（-std=c++11 -Wall -Wextra）+ VS2022；教学简化版，生产请直接使用std::stack/std::queue/std::priority_queue。
文中代码均为本人手写并实测；官方文档：cppreference·stack / queue / priority_queue。

让我们开始吧。

一、stack：后进先出

一句话：后进先出（LIFO），只允许在栈顶一端插入和删除。

stack<int>st;for(inti=1;i<=4;++i)st.push(i);cout<<st.top()<<endl;// 4（栈顶）st.pop();cout<<st.top()<<endl;// 3

【一句话记】push 压栈顶、pop 弹栈顶、top 看栈顶——三个动作全在栈顶，所以都是 O(1)。

【面试】stack 没有迭代器、不支持遍历，是缺陷吗？不是——它的职责就是管住"只能动一头"，不给你乱看中间元素的机会。需要遍历，说明选错容器了。

二、stack 实战：最小栈

光会 push/pop 不算会用，直接上 OJ：设计一个栈，push / pop / top / getMin 全部 O(1)。

思路：开两个栈。_elem存所有元素；_min存"历史最小值"——每次压入的值只要"不大于当前最小值"，就在_min里也记一份。

classMinStack{public:voidpush(intx){_elem.push(x);// 只有"不大于当前最小"才记入 _min（重复最小值也要记，pop 才不会错）if(_min.empty()||x<=_min.top())_min.push(x);}voidpop(){// 出栈的元素正好是当前最小，_min 跟着出if(_min.top()==_elem.top())_min.pop();_elem.pop();}inttop(){return_elem.top();}intgetMin(){return_min.top();}private:stack<int>_elem;// 存所有元素stack<int>_min;// 存"当前最小值"的历史};

实测（仓库stack_queue_sim.cpp的test_min_stack()）：

getMin=-3 top=0 getMin=-2 top=-2 getMin=-2

【易错】push 里的判断是<=不是<：把重复的最小值也记进_min，pop 时才能一一对应地弹掉；写成<的话，一旦最小值出现了两次，弹出一次后 getMin 就出错了。

同类的栈实战还有"栈的弹出压入序列"“逆波兰表达式求值”“用两个栈实现队列”，思路都是用栈模拟过程，仓库里没放全，感兴趣的先自己写，写不出来评论区喊我。

三、queue：先进先出

一句话：先进先出（FIFO），队尾进、队头出。

queue<int>q;q.push(10);q.push(20);q.push(30);cout<<q.front()<<" "<<q.back()<<endl;// 10 30q.pop();cout<<q.front()<<endl;// 20

【一句话记】queue 的 push 只管尾、pop 只管头，也是全 O(1)；front / back 一个看头、一个看尾。

经典场景：二叉树的层序遍历、图的 BFS——“一圈一圈往外扩”，天生是队列的活。

四、容器适配器：stack 和 queue 是"套壳"

stack 和 queue 在 STL 里有个特殊身份：容器适配器（container adapter）。

适配器是一种设计模式：把一个类的接口，转换成使用者期望的另一个接口。生活里的例子就是电源转换插头——插座还是那个插座，插头换个形状就能用了。

看标准库的模板签名就明白了：

template<classT,classContainer=deque<T>>classstack;template<classT,classContainer=deque<T>>classqueue;

Container就是"底层容器"的槽位：stack / queue 自己不存数据，所有元素都放在一个Container类型的成员_c里，接口一个个"转包"过去：

所以底层容器要"接得住"这些活：

【面试】queue<vector<int>>为什么编译不过？vector 没有高效的头部删除——pop_front这个接口在 vector 上根本不存在，模板实例化直接报错。

换底层实测（仓库stack_queue_sim.cpp的test_adapter_switch()）：

stack 顶: 4 4 4 queue 头尾: 1/4 1/4

三栈同顶、两队列同头尾：同一套接口，底层随便换，行为完全一致，差别只在性能。

五、手写模拟实现：stack 与 queue

看清"套壳"本质，手写就是把转包关系翻译成代码——一个成员 + 一行转发。完整实现见仓库stack_queue_sim.cpp的namespace bit：

namespacebit{template<classT,classCon=deque<T>>classstack{public:voidpush(constT&x){_c.push_back(x);}voidpop(){_c.pop_back();}T&top(){return_c.back();}constT&top()const{return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};template<classT,classCon=deque<T>>classqueue{public:voidpush(constT&x){_c.push_back(x);}voidpop(){_c.pop_front();}T&front(){return_c.front();}constT&front()const{return_c.front();}T&back(){return_c.back();}constT&back()const{return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};}

实测输出（同一份模板，三种 / 两种底层都跑）：

[deque 底层] size=5 top=50 | pop: 50 40 30 20 10 | empty=1 [vector 底层] size=5 top=50 | pop: 50 40 30 20 10 | empty=1 [list 底层] size=5 top=50 | pop: 50 40 30 20 10 | empty=1 [deque 底层] size=5 front=10 back=50 | pop: 10 20 30 40 50 | empty=1 [list 底层] size=5 front=10 back=50 | pop: 10 20 30 40 50 | empty=1

注意 queue 没有 vector 版——原因上一节刚说过。

【一句话记】适配器的实现公式：成员_c+ 接口逐一转发；换底层只需换一个模板参数。

六、priority_queue：堆的封装

6.1 用法：默认大堆

priority_queue 也是适配器，但它比 stack / queue 多一层：底层用堆（heap）算法维护优先级。默认底层是 vector，默认比较是"小于"，所以默认是大堆——top()永远是最大元素。

默认大堆，想变小堆就把比较方式换成greater：

vector<int>v{3,2,7,6,0,4,1,9,8,5};priority_queue<int>q1(v.begin(),v.end());// 大堆cout<<q1.top()<<endl;// 9priority_queue<int,vector<int>,greater<int>>q2(v.begin(),v.end());// 小堆cout<<q2.top()<<endl;// 0

自定义类型要注意：默认大堆要求类型支持operator<；换greater变小堆则要求operator>。

6.2 手写模拟实现：堆的两个调整

priority_queue 的内核就是堆，手写的关键只有两个函数：向上调整（新元素从尾浮到该去的位置）和向下调整（堆顶下沉）。完整实现见仓库stack_queue_sim.cpp的priority_queue部分：

template<classT,classCon=vector<T>,classCompare=less<T>>classpriority_queue{// ... 省略构造 / top / size / emptyvoidpush(constT&x){_c.push_back(x);adjust_up(_c.size()-1);// 尾插后向上调整}voidpop(){swap(_c[0],_c[_c.size()-1]);// 堆顶和末尾交换_c.pop_back();// 删掉原来的堆顶adjust_down(0);// 新堆顶向下调整}private:voidadjust_up(size_t child){Compare com;size_t parent=(child-1)/2;while(child>0){if(com(_c[parent],_c[child]))// 双亲比孩子"小"，交换{swap(_c[parent],_c[child]);child=parent;parent=(child-1)/2;}elsebreak;}}voidadjust_down(size_t parent){Compare com;size_t child=parent*2+1;while(child<_c.size()){if(child+1<_c.size()&&com(_c[child],_c[child+1]))++child;// 挑"更该上去"的那个孩子if(com(_c[parent],_c[child])){swap(_c[parent],_c[child]);parent=child;child=parent*2+1;}elsebreak;}}Con _c;};

实测输出：

[默认大堆] top=9 | 依次弹出: 9 8 7 6 5 4 3 2 1 0 [greater 小堆] top=0 | 依次弹出: 0 1 2 3 4 5 6 7 8 9 [push 版大堆] size=10 top=9

【一段话记】push = 尾插 + 向上调整；pop = 堆顶与末尾交换、删尾、再向下调整；区间建堆则从最后一个非叶子结点开始，倒着做向下调整。仿函数less/greater决定大堆小堆——同一份堆代码，换个比较器就换了个性。

经典 OJ：数组中的第 K 个最大元素——建个大堆，pop 掉 K-1 次，剩下的堆顶就是答案。

七、deque：为什么默认底层是它

stack / queue 的默认底层是 deque（双端队列）。它长什么样？

deque 不是一整块连续空间，而是一段段固定大小的缓冲区拼起来的，再用一个"中控器"（map，指针数组）记住每段的地址。对外假装连续：支持[]随机访问；对内两头都能 O(1) 进出。用一个实测感受下（仓库stack_queue_sim.cpp的test_deque()）：

双端插入后: -10 0 10 20 30 | size=5 dq[0]=-10 dq[4]=30 中间插 99: -10 0 10 99 20 30 | size=6 两头各删一个: 0 10 99 20 | size=4

和两位老朋友比一比：

deque 的优点是"头尾都能 O(1)、还支持随机访问"，致命缺点是"遍历慢"。

【面试】那 stack / queue 为什么还要默认选它？

1. stack / queue不需要遍历（连迭代器都没有），刚好绕开 deque 的最大缺陷，吃满它"两端操作快"的优点；
2. 元素增长时，deque 扩容不需要搬大量元素（vector 要），队列场景下内存利用率也更好。

短板全躲开、长板全用上——这就是标准库的取舍。

八、选型对比总表

九、速记卡

考前扫一眼，面试不卡壳：

十、自测三连

先自己默答，再看答案对照：

1. 为什么 stack / queue 叫"容器适配器"？默认底层是什么？

它们自己不存数据，只是把一个底层容器（默认deque<T>）包起来，把 push/pop/top 等接口"转包"给底层的 push_back/pop_back/front 等接口——把一种接口包装成另一种接口，就是适配器模式。

2. queue<vector<int>>能不能编译？为什么？

不能。queue 的接口要求底层支持pop_front（队头删除），而 vector 根本没有这个接口，模板实例化时直接编译错误。queue 的底层只能用 deque 或 list。

3. priority_queue 默认大堆还是小堆？怎么变小堆？手写的 push / pop 各做了什么？

默认大堆（vector + less）。变小堆：priority_queue<int, vector<int>, greater<int>>。push = 尾插 + 向上调整；pop = 堆顶与末尾交换、删尾、新堆顶向下调整。两者都是 O(log N)。

附录 A：完整代码仓库

完整工程（单文件版，全部实验一次跑完）在 Gitee：

https://gitee.com/BaiYang_SQ/stack-queue-sim

不想翻文件的话，下面是 stack / queue 的最小骨架，面试前拿来手写练手正合适：

// stack / queue 适配器·最小可运行骨架// 完整单文件版（含全部实验与项目输出）见 Gitee：// https://gitee.com/BaiYang_SQ/stack-queue-sim#include<iostream>#include<deque>usingnamespacestd;namespacebit{template<classT,classCon=deque<T>>classstack{public:voidpush(constT&x){_c.push_back(x);}voidpop(){_c.pop_back();}T&top(){return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};template<classT,classCon=deque<T>>classqueue{public:voidpush(constT&x){_c.push_back(x);}voidpop(){_c.pop_front();}T&front(){return_c.front();}T&back(){return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};}intmain(){bit::stack<int>st;st.push(1);st.push(2);st.push(3);cout<<st.top()<<endl;// 3st.pop();cout<<st.top()<<endl;// 2bit::queue<int>q;q.push(1);q.push(2);q.push(3);cout<<q.front()<<" "<<q.back()<<endl;// 1 3q.pop();cout<<q.front()<<endl;// 2return0;}

好了，stack 和 queue 这篇到此完结！下一篇是入门篇的收官之战——模板进阶（预告：非类型模板参数、模板特化、分离编译，还有"为什么模板的声明和定义不能随便分家"）。如果对你有帮助，不要忘记点赞三连一波哦，我是白杨，我们下期见。