C++入门篇（十六）：stack 和 queue——容器适配器、deque 底层与手写模拟实现（附完整代码仓库）

0.1 概述序言这里是白杨。上一篇把 list 从用法到手写实现走了个全套。这篇进入 STL 第四站stack 和 queue。这篇要过五件事stack / queue 的用法和经典实战最小栈容器适配器思想它俩为什么算套壳不算容器手写模拟实现 换底层实测priority_queue堆的用法与手写实现deque 初探为什么标准库默认拿它当底层老规矩跑得通的结果才写进来环境见下完整代码文末自取也可以直接去仓库gitee.com/BaiYang_SQ/stack-queue-sim。实测环境w64devkit g 15.2.0-stdc11 -Wall -Wextra VS2022教学简化版生产请直接使用std::stack/std::queue/std::priority_queue。文中代码均为本人手写并实测官方文档cppreference·stack / queue / priority_queue。让我们开始吧。一、stack后进先出一句话后进先出LIFO只允许在栈顶一端插入和删除。接口说明stack()构造空栈empty()判空size()元素个数top()返回栈顶元素的引用push(x)压栈x 入栈顶pop()出栈弹出栈顶stackintst;for(inti1;i4;i)st.push(i);coutst.top()endl;// 4栈顶st.pop();coutst.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:stackint_elem;// 存所有元素stackint_min;// 存当前最小值的历史};实测仓库stack_queue_sim.cpp的test_min_stack()getMin-3 top0 getMin-2 top-2 getMin-2【易错】push 里的判断是不是把重复的最小值也记进_minpop 时才能一一对应地弹掉写成的话一旦最小值出现了两次弹出一次后 getMin 就出错了。同类的栈实战还有栈的弹出压入序列“逆波兰表达式求值”“用两个栈实现队列”思路都是用栈模拟过程仓库里没放全感兴趣的先自己写写不出来评论区喊我。三、queue先进先出一句话先进先出FIFO队尾进、队头出。接口说明queue()构造空队列empty()判空size()有效元素个数front()返回队头元素的引用back()返回队尾元素的引用push(x)队尾入队pop()队头出队queueintq;q.push(10);q.push(20);q.push(30);coutq.front() q.back()endl;// 10 30q.pop();coutq.front()endl;// 20【一句话记】queue 的 push 只管尾、pop 只管头也是全 O(1)front / back 一个看头、一个看尾。经典场景二叉树的层序遍历、图的 BFS——“一圈一圈往外扩”天生是队列的活。四、容器适配器stack 和 queue 是套壳stack 和 queue 在 STL 里有个特殊身份容器适配器container adapter。适配器是一种设计模式把一个类的接口转换成使用者期望的另一个接口。生活里的例子就是电源转换插头——插座还是那个插座插头换个形状就能用了。看标准库的模板签名就明白了templateclassT,classContainerdequeTclassstack;templateclassT,classContainerdequeTclassqueue;Container就是底层容器的槽位stack / queue 自己不存数据所有元素都放在一个Container类型的成员_c里接口一个个转包过去外壳接口实际动作stack::push_c.push_back(x)stack::pop_c.pop_back()stack::top_c.back()queue::push_c.push_back(x)queue::pop_c.pop_front()queue::front_c.front()所以底层容器要接得住这些活外壳对底层的要求谁能当底层stack尾插、尾删、取尾deque / vector / list 都行queue尾插、头删、取头取尾deque / list 行vector 不行没有pop_front【面试】queuevectorint为什么编译不过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 bitnamespacebit{templateclassT,classCondequeTclassstack{public: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;};templateclassT,classCondequeTclassqueue{public:voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_front();}Tfront(){return_c.front();}constTfront()const{return_c.front();}Tback(){return_c.back();}constTback()const{return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};}实测输出同一份模板三种 / 两种底层都跑[deque 底层] size5 top50 | pop: 50 40 30 20 10 | empty1 [vector 底层] size5 top50 | pop: 50 40 30 20 10 | empty1 [list 底层] size5 top50 | pop: 50 40 30 20 10 | empty1 [deque 底层] size5 front10 back50 | pop: 10 20 30 40 50 | empty1 [list 底层] size5 front10 back50 | pop: 10 20 30 40 50 | empty1注意 queue 没有 vector 版——原因上一节刚说过。【一句话记】适配器的实现公式成员_c 接口逐一转发换底层只需换一个模板参数。六、priority_queue堆的封装6.1 用法默认大堆priority_queue 也是适配器但它比 stack / queue 多一层底层用堆heap算法维护优先级。默认底层是 vector默认比较是小于所以默认是大堆——top()永远是最大元素。接口说明priority_queue()构造空堆priority_queue(first, last)迭代器区间建堆empty()/size()判空 / 个数top()堆顶默认最大元素push(x)插入自动调整pop()删除堆顶自动调整默认大堆想变小堆就把比较方式换成greatervectorintv{3,2,7,6,0,4,1,9,8,5};priority_queueintq1(v.begin(),v.end());// 大堆coutq1.top()endl;// 9priority_queueint,vectorint,greaterintq2(v.begin(),v.end());// 小堆coutq2.top()endl;// 0自定义类型要注意默认大堆要求类型支持operator换greater变小堆则要求operator。6.2 手写模拟实现堆的两个调整priority_queue 的内核就是堆手写的关键只有两个函数向上调整新元素从尾浮到该去的位置和向下调整堆顶下沉。完整实现见仓库stack_queue_sim.cpp的priority_queue部分templateclassT,classConvectorT,classComparelessTclasspriority_queue{// ... 省略构造 / top / size / emptyvoidpush(constTx){_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(child0){if(com(_c[parent],_c[child]))// 双亲比孩子小交换{swap(_c[parent],_c[child]);childparent;parent(child-1)/2;}elsebreak;}}voidadjust_down(size_t parent){Compare com;size_t childparent*21;while(child_c.size()){if(child1_c.size()com(_c[child],_c[child1]))child;// 挑更该上去的那个孩子if(com(_c[parent],_c[child])){swap(_c[parent],_c[child]);parentchild;childparent*21;}elsebreak;}}Con _c;};实测输出[默认大堆] top9 | 依次弹出: 9 8 7 6 5 4 3 2 1 0 [greater 小堆] top0 | 依次弹出: 0 1 2 3 4 5 6 7 8 9 [push 版大堆] size10 top9【一段话记】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 | size5 dq[0]-10 dq[4]30 中间插 99: -10 0 10 99 20 30 | size6 两头各删一个: 0 10 99 20 | size4和两位老朋友比一比维度vectorlistdeque空间一整块连续结点散装分段连续 中控器头插头删O(N)要搬家O(1)O(1)尾插尾删O(1)扩容要搬O(1)O(1)随机访问O(1)不支持O(1)遍历快缓存友好慢慢迭代器频繁跨段检测中间插删O(N)O(1)O(N)deque 的优点是头尾都能 O(1)、还支持随机访问致命缺点是遍历慢。【面试】那 stack / queue 为什么还要默认选它stack / queue不需要遍历连迭代器都没有刚好绕开 deque 的最大缺陷吃满它两端操作快的优点元素增长时deque 扩容不需要搬大量元素vector 要队列场景下内存利用率也更好。短板全躲开、长板全用上——这就是标准库的取舍。八、选型对比总表容器底层结构随机访问头尾插删中间插删典型场景vector连续数组O(1)尾 O(1) / 头 O(N)O(N)随机访问多、尾插多list带头双向循环链表不支持O(1)O(1)任意位置频繁插删deque分段连续 中控器O(1)O(1)O(N)双端进出其余少用stack适配器默认 deque不支持栈顶 O(1)—LIFO嵌套、回溯、模拟queue适配器默认 deque不支持队头队尾 O(1)—FIFO层序、BFS、排队priority_queue适配器vector 堆只读堆顶O(log N)—Top-K、动态取最大/最小九、速记卡考前扫一眼面试不卡壳十、自测三连先自己默答再看答案对照为什么 stack / queue 叫容器适配器默认底层是什么答案它们自己不存数据只是把一个底层容器默认dequeT包起来把 push/pop/top 等接口转包给底层的 push_back/pop_back/front 等接口——把一种接口包装成另一种接口就是适配器模式。queuevectorint能不能编译为什么答案不能。queue 的接口要求底层支持pop_front队头删除而 vector 根本没有这个接口模板实例化时直接编译错误。queue 的底层只能用 deque 或 list。priority_queue 默认大堆还是小堆怎么变小堆手写的 push / pop 各做了什么答案默认大堆vector less。变小堆priority_queueint, vectorint, greaterint。push 尾插 向上调整pop 堆顶与末尾交换、删尾、新堆顶向下调整。两者都是 O(log N)。附录 A完整代码仓库完整工程单文件版全部实验一次跑完在 Giteehttps://gitee.com/BaiYang_SQ/stack-queue-sim仓库文件说明stack_queue_sim.cpp单文件全部实验 完整模拟实现章节 ↔ 函数名对照见仓库 README 导览表output.txt全部实验的真实运行输出不想装编译器直接看这个build.batWindows 一键编译 运行 刷新 output.txtREADME.md一分钟上手 代码导览不想翻文件的话下面是 stack / queue 的最小骨架面试前拿来手写练手正合适// stack / queue 适配器·最小可运行骨架// 完整单文件版含全部实验与项目输出见 Gitee// https://gitee.com/BaiYang_SQ/stack-queue-sim#includeiostream#includedequeusingnamespacestd;namespacebit{templateclassT,classCondequeTclassstack{public:voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_back();}Ttop(){return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};templateclassT,classCondequeTclassqueue{public:voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_front();}Tfront(){return_c.front();}Tback(){return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};}intmain(){bit::stackintst;st.push(1);st.push(2);st.push(3);coutst.top()endl;// 3st.pop();coutst.top()endl;// 2bit::queueintq;q.push(1);q.push(2);q.push(3);coutq.front() q.back()endl;// 1 3q.pop();coutq.front()endl;// 2return0;}好了stack 和 queue 这篇到此完结下一篇是入门篇的收官之战——模板进阶预告非类型模板参数、模板特化、分离编译还有为什么模板的声明和定义不能随便分家。如果对你有帮助不要忘记点赞三连一波哦我是白杨我们下期见。