★ FEATURED ARTICLE 个人主页 流年如梦专栏 《零基础轻松入门C语言》 《数据结构从入门到掌握》 《C编程研习录》文章目录一.stack的介绍和使用1.1 stack的介绍1.2 stack的常用接口1.2.1 最小栈1.2.2 栈的弹出序列1.2.3 逆波兰表达式求值1.3 stack 的模拟实现二.queue 的介绍和使用2.1 queue的介绍2.2 queue的常用接口2.3 queue的模拟实现三.priority_queue的介绍和使用3.1 priority_queue的介绍3.2 priority_queue的常用接口3.3 OJ 实战数组中第 K 个最大元素3.4 priority_queue的模拟实现四.容器适配器与deque4.1 什么是适配器模式4.2 STL 适配器的模板定义4.3 deque简单介绍4.4 为什么选择deque作为默认底层4.5 标准库式模拟实现可指定底层容器总结⚠️易错点前言stack、queue、priority_queue 是 STL 中三类典型的**容器适配器**。它们并不直接实现底层数据结构而是对已有容器进行封装对外提供语义明确的操作接口。其中stack 遵循后进先出LIFO原则仅允许在栈顶进行操作queue 遵循先进先出FIFO原则队尾入队、队头出队priority_queue 则基于堆结构保证堆顶元素始终拥有最高优先级。本文将从接口使用与经典算法场景入手系统讲解这三类适配器并逐步完成它们的模拟实现深入剖析容器适配器设计模式与底层 deque 的原理同时对比不同底层容器的优劣。一.stack的介绍和使用1.1 stack的介绍stack 是**后进先出Last In First Out**的容器适配器仅支持栈顶一端的插入、删除与访问不支持遍历与随机访问。默认以 deque 作为底层容器也可指定 vector、list 作为底层实现典型应用场景括号匹配、表达式求值、函数调用栈、模拟递归等1.2 stack的常用接口使用 stack 必须包含头文件#include stack接口说明stack()构造空栈empty()检测栈是否为空空返回 truesize()返回栈中元素个数top()返回栈顶元素的引用push()将元素压入栈顶pop()弹出栈顶元素1.2.1 最小栈题目思路双栈实现元素栈存数据辅助栈存每一步的最小值两个栈同步操作保证getMin时间复杂度 O (1)代码classMinStack{public:voidpush(intx){_elem.push(x);// 空栈或新元素更小则压入辅助栈if(_min.empty()||x_min.top())_min.push(x);}voidpop(){// 弹出元素等于当前最小值辅助栈同步弹出if(_min.top()_elem.top())_min.pop();_elem.pop();}inttop(){return_elem.top();}intgetMin(){return_min.top();}private:stackint_elem;// 存储所有元素stackint_min;// 维护最小值序列};1.2.2 栈的弹出序列题目思路用辅助栈模拟压入弹出过程按弹出序列匹配栈顶匹配成功则弹出全部匹配完成则合法代码classSolution{public:boolvalidateStackSequences(vectorintpushed,vectorintpopped){if(pushed.size()!popped.size())returnfalse;stackintst;intinIdx0,outIdx0;while(outIdxpopped.size()){// 栈空或栈顶不匹配持续压栈while(st.empty()||st.top()!popped[outIdx]){if(inIdxpushed.size())returnfalse;st.push(pushed[inIdx]);}// 栈顶匹配则弹出st.pop();outIdx;}returntrue;}};1.2.3 逆波兰表达式求值题目思路遇到数字压栈遇到运算符弹出两个数计算结果重新压栈最终栈顶即为表达式结果。注意操作数顺序先弹出的是右操作数代码classSolution{public:intevalRPN(vectorstringtokens){stackintst;for(autostr:tokens){// 数字直接入栈if(str!str!-str!*str!/){st.push(stoi(str));}else{// 先弹出右操作数再弹出左操作数intrightst.top();st.pop();intleftst.top();st.pop();switch(str[0]){case:st.push(leftright);break;case-:st.push(left-right);break;case*:st.push(left*right);break;case/:st.push(left/right);break;}}}returnst.top();}};1.3 stack 的模拟实现栈仅需尾插尾删使用 vector 封装即可实现#includevectornamespacemy{templateclassTclassstack{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:vectorT_c;// 底层容器};}二.queue 的介绍和使用2.1 queue的介绍queue 是**先进先出First In First Out**的容器适配器支持队尾插入、队头删除不支持随机访问与遍历。默认以 deque 作为底层容器也可指定 list 作为底层实现典型应用场景广度优先搜索BFS、任务队列、消息队列、缓存等2.2 queue的常用接口使用 queue 必须包含头文件#include queue接口说明queue()构造空队列empty()检测队列是否为空空返回 truesize()返回队列中元素个数front()返回队头元素的引用back()返回队尾元素的引用push()队尾插入元素pop()队头弹出元素2.3 queue的模拟实现队列需要尾插头删vector 头删效率为 O (N)因此选用 list 封装实现#includelistnamespacemy{templateclassTclassqueue{public:queue(){}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:listT_c;// 底层容器};}三.priority_queue的介绍和使用3.1 priority_queue的介绍priority_queue 又称优先级队列是基于堆结构的容器适配器保证队顶元素始终是优先级最高的元素。默认以 vector 作为底层容器默认构建大堆顶部元素最大典型应用场景TopK 问题、任务优先级调度、合并有序链表等3.2 priority_queue的常用接口使用 priority_queue 必须包含头文件#include queue使用greater比较器需包含#include functional接口说明priority_queue()构造空优先级队列priority_queue(first, last)用迭代器区间构造empty()检测是否为空top()返回堆顶优先级最高元素push(x)插入元素并调整堆结构pop()删除堆顶元素并调整堆注意事项默认是大堆比较器为lessT创建小堆需指定第三个模板参数greaterT自定义类型放入优先级队列必须重载大堆或小堆运算符举例// 默认大堆顶部元素最大priority_queueintq1;// 小堆顶部元素最小priority_queueint,vectorint,greaterintq2;3.3 OJ 实战数组中第 K 个最大元素题目思路利用大顶堆特性所有元素入堆后依次弹出 k-1 个最大值堆顶即为第 k 大元素代码classSolution{public:intfindKthLargest(vectorintnums,intk){priority_queueintpq(nums.begin(),nums.end());// 弹出前k-1个最大元素for(inti0;ik-1;i)pq.pop();returnpq.top();}};3.4 priority_queue的模拟实现底层基于 vector 存储封装堆调整算法实现优先级队列#includevector#includealgorithmnamespacemy{templateclassT,classContainervectorT,classComparelessTclasspriority_queue{public:priority_queue(){}templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last):_c(first,last){make_heap(_c.begin(),_c.end(),_cmp);}voidpush(constTx){_c.push_back(x);push_heap(_c.begin(),_c.end(),_cmp);}voidpop(){pop_heap(_c.begin(),_c.end(),_cmp);_c.pop_back();}constTtop()const{return_c.front();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Container _c;Compare _cmp;};}四.容器适配器与deque4.1 什么是适配器模式适配器是一种结构型设计模式核心作用是将一个类的接口转换成客户期望的另一种接口让原本接口不兼容的类可以协同工作。STL 容器适配器就是封装底层容器对外提供统一的特定语义接口屏蔽底层容器的差异本质是接口转换与封装属于黑箱复用耦合度低于继承4.2 STL 适配器的模板定义stack 和 queue 第二个模板参数指定底层容器默认均为 dequetemplateclassT,classContainerdequeTclassstack;templateclassT,classContainerdequeTclassqueue;priority_queue 默认底层为 vector比较器默认lesstemplateclassT,classContainervectorT,classComparelessTclasspriority_queue;4.3 deque简单介绍deque双端队列是支持两端 O (1) 插入删除的序列容器底层是分段连续的内存块通过中控器管理多个缓冲区对外模拟连续空间的假象。优点头尾插入删除 O (1)扩容无需大量移动元素空间利用率高于 list缺点迭代器设计复杂遍历效率低随机访问性能弱于 vector4.4 为什么选择deque作为默认底层stack 和 queue 不需要遍历、不需要随机访问仅在一端或两端操作完美避开 deque 遍历效率低的缺点同时 deque 头尾操作效率高扩容成本低于 vector空间利用率优于 list因此成为栈与队列的默认底层容器4.5 标准库式模拟实现可指定底层容器// stack 通用版本支持自定义底层容器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;};// queue 通用版本支持自定义底层容器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;};总结stack 是后进先出适配器仅栈顶操作默认底层 deque适用于括号匹配、表达式求值等场景queue 是先进先出适配器队尾入队头出默认底层 deque适用于 BFS、任务队列等场景priority_queue 是堆结构适配器默认大堆底层 vector适用于 TopK、优先级调度等场景容器适配器本质是接口封装属于适配器设计模式本身不实现原生数据结构deque 是分段连续双端队列头尾操作高效遍历性能弱完美适配栈与队列的操作特性最小栈、弹出序列验证、逆波兰求值、TopK 是栈与优先级队列的经典算法应用适配器支持自定义底层容器可根据场景选择 vector、list、deque 实现⚠️易错点混淆 stack 和 queue 的进出方向栈尾进尾出队列尾进头出priority_queue 默认是大堆误以为是小堆导致 TopK 结果错误自定义类型放入 priority_queue未重载比较运算符导致编译错误误以为 stack 和 queue 是容器实际是容器适配器用 vector 实现 queue头删操作 O (N) 效率极低deque 随机访问效率低于 vector遍历场景优先用 vector逆波兰表达式求值时操作数左右顺序搞反减法除法结果出错最小栈中相等元素不同时压入辅助栈pop 后最小值错误priority_queue 底层是堆插入删除都需要调整堆结构时间复杂度 O (logN)适配器底层容器不支持对应操作时编译报错比如用 vector 做 queue 底层会因pop_front失效 关注我们一路同行从入门到大师慢慢沉淀、稳步成长❤️ 点赞鼓励原创让优质内容被更多人看见⭐ 收藏收好核心知识点与实战技巧需要时随时查阅 评论分享你的疑问或踩坑经历一起交流避坑、共同进步
阅读完成 · 觉得有帮助？
