【C++STL上】栈和队列模拟实现 容器适配器 力扣经典算法秘籍
🔥个人主页：爱和冰阔乐
📚专栏传送门：《数据结构与算法》 、C++
🐶学习方向：C++方向学习爱好者
⭐人生格言：得知坦然 ，失之淡然
🏠博主简介
文章目录
前言
本文从STL容器适配器视角，深度解析栈与队列的设计本质——以双端队列（deque）为底层容器，实现高效头尾操作。结合最小栈、二叉树层序遍历等经典算法题，实战演示栈的"先进后出"与队列的"先进先出"特性，并揭秘优先级队列的堆实现原理。通过模拟实现代码，希望读完本文可以让大家对栈和队列有更深刻理解
一、栈与队列原型简介
1.1 Stack
stack官方文档链接：https://cplusplus.com/reference/stack/stack/?kw=stack
在stack官方文档说明中介绍其不是容器而是容器适配器，在文档中栈和在C语言中实现的其——先进后出的特点，其使用的是模板+封装实现的，这里使用的缺省参数是deque(在后面我们会介绍)，如下是栈的主要接口：
这些接口我们发现很熟悉，在C语言中便已经实现过了
注意:容器适配器不再拥有迭代器了，举个简单的例子，如果栈和队列拥有了迭代器便不能保证先进先出和先进后出，而是可以通过迭代器的下标+[]即可出入数据
1.2 Queue
队列官方文档链接：https://cplusplus.com/reference/queue/queue/
同理：在squeue官方文档说明中介绍其不是容器而是容器适配器，在文档中栈和在C语言中实现的其——先进先出的特点，如下是队列的主要接口：
如若对C语言阶段实现的栈和队列有所遗忘，可以点击我——>后来者居上与先来后到：栈和队列的顺序哲学及算法实战（含源码）
1.3 最小栈的练习
力扣网址：https://leetcode.cn/problems/min-stack/
题目解释： 在本题中除了需要完成栈的基本接口以外，还要在时间复杂度为O(1)的情况下找到最小的元素
思路： 在这道题中大部分想到的思路便是：
1.通过定义变量来存储最小的值，将第一次插入到栈的数据先存放到变量中（假设第一次插入的数据为最小值）
2.再将后续的数据一个个插入到栈中，依次和变量存储的数据进行比较，如果插入栈中的数据小于变量存放的则变量中的数据更新为新的数据
但是我们如果要出栈的话，存放在变量中的最小元素也要删除，那么在栈中最小的元素是什么？如果我们要遍历栈，那么时间复杂度为O（n）
在前面的算法中我们便知道可以定义两个栈，一个栈_str用来进行入栈和出栈数据的存放与删除，一个栈_minstr用来和_str中插入的数据比大小
：如若_str入的数据小于_minstr中的数据，那么便将该数据插入到_minstr中（第一次数据入_str的同时也要入_minstr），如果_str插入的数据一直大于_minstr存放的数据，那么便不在_minstr中入数据（如果插入的数据与_minstr存放的数据相同是要将该数据存放到_minstr中）
代码演示：
classMinStack{public:MinStack(){}voidpush(int val){ _str.push(val);if(_minstr.empty()||val<=_minstr.top()) _minstr.push(val);}voidpop(){if(_str.top()==_minstr.top()){ _minstr.pop();} _str.pop();}inttop(){return _str.top();}intgetMin(){return _minstr.top();}private: stack<int> _str; stack<int> _minstr;};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */1.4 栈的压入、弹出序列
牛客网址：栈的压入、弹出序列
题目解释： 给定两个数组，第一个表示进栈的顺序，第二个数组表示出栈的顺序，判断两个数组是否为一个栈的出入栈的顺序
思路： 只要入栈序列能模拟出出栈序列的过程，那么就是匹配的，否则不是
1.入栈序列先入栈（每次入一个数据）
2.每次入栈完后将该数据和出栈序列的数据进行比对，如果匹配则持续出数据（出栈序列指针依次往后走），不匹配则继续将入栈序列的数据入栈（入栈序列指针往后走）
3.入栈序列结束则结束
代码实现：
classSolution{public:/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */boolIsPopOrder(vector<int>& pushV, vector<int>& popV){ size_t popi=0; stack<int> st;for(auto e:pushV){//入栈 st.push(e);//入栈序列与出栈序列匹配while(!st.empty()&&st.top()==popV[popi]){//将数据出栈,如果持续的出数据导致st中为空，无法取栈顶元素 st.pop();//让popi走向下一个位置 popi++;}}return st.empty();}};1.5 二叉树的层序遍历
力扣网址：二叉树的层序遍历
题目解释：要求将二叉树的每一层放到二维数组的每一行上组层二维数组，这里的二维数组的每一行便不再相等（不是标准的二维数组）
那么怎么将输入的二叉树的节点放到二维数组对应的位置上？
思路： 广度优先遍历:
1.先将二叉树的根（3）入到队列里面，然后将其出出来，再将其的孩子入进去（9,20）
2.将9出出来，再将9的孩子节点出来，因为9没有孩子节点，所以不用出
3 .将20出出来，再将20的孩子节点出出来
但是如果9有孩子节点，那么队列中会同时存在两层不同的数据，那么我们怎么区分？
这里我们想到可以使用最小栈的思路，定义两个队列，第一个队列存放树的节点的指针，第二个队列存该数据是第几层的：
1.我们在q1队列入数的根节点（3），3对应的是第一层，因此q2队列存放1
2.将3和1出队列，再将3的孩子9,20入队列，因为根节点对应的是第一层，因此其孩子节点只需++，即第二层
3.将9出出来，因为其没有孩子节点，所以q2不入数据，q1出20，将20的孩子节点15，,7入数据，15,7对应的是第三层
但是由于定义了两个队列，有所繁琐，下面我们只使用一个队列看看如何搞定！
思路2：定义变量levelSize代表当前层的数据个数，我们每一次出数据都将该层的数据全部出出来（levelSize为0代表该层的数据出完了）
1.将根节点3入队列，levelSize为1，将3出队列，孩子节点9,20入队列，levelSize更新为2
2.将9出队列levelSize变为1,再将20出队列，levelsize为0，再将其孩子节点15,7入队列，levelSize更新为2，因此队列的size就是下一层的数据个数
代码实现：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public: vector<vector<int>>levelOrder(TreeNode* root){//二维数组 vector<vector<int>> vv; queue<TreeNode*>q;int levelsize=0;//当前层的数据个数，控制一层一层出if(root){ q.push(root); levelsize=1;}while(!q.empty()){//当前层的数据个数，控制一层一层出 vector<int> v;while(levelsize--){ TreeNode*front=q.front(); q.pop(); v.push_back(front->val);if(front->left) q.push(front->left);if(front->right) q.push(front->right);} vv.push_back(v);//当前层出完，下一层都进队列了，队列的size就是下一层的数据个数 levelsize=q.size();}return vv;}};二、模拟实现栈
2.1 容器适配器
在传统实现容器时我们都使用模板，如下：
但在这里我们便使用适配器，那么什么是适配器？
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
在日常生活中由于家里的供电标准是120v，但是实际上我们手机或者电灯充电的是3v/5v，那么为什么我们的设备没有因为电量过大导致炸了（或者我们摸下充电器裸露的一部分，120v的电压我们碰到会怎么样）？这便是因为我们使用了充电器将电压转换成我们需要的功率
那么什么是设计模式？设计模式可以理解为孙子兵法，将各种打仗的方式进行了总结，迭代器也是一种设计模式
2.2栈的实现
在认识到适配器后，我们思考下栈的特点便是在栈顶插入删除元素这些操作，在我们已经学到的容器中vector和list支持在一段插入删除数据，因此其通过封装便可得到栈，这里我们传Container（容器），好处便是栈的类型不再写死，而是可以传vector/list都可以，通过Container适配转换出要的stack
代码实现：
#include<vector>#include<list>//栈这个容器可以使用其他容器进行封装转换得到栈//栈顶插入/删除即可//vector/list都可以在一段插入和删除数据，那么我们通过封装vector/list得到栈namespace hxx {//用Contaier适配转换出要的栈template<classT,classContainer==vector<T>>classstack{public://栈的构造函数便不需要写，因为Container是自定义类型，会调用Container的构造函数//我们统一把尾部当成栈顶voidpush(const T& x){ _con.push_back(x);}voidpop(){ _con.pop_back();}const T&top(){return _con.back();} size_t size()const{return _con.size();}boolempty()const{return _con.empty();}private: Container _con;};}三、模拟实现队列
队列的实现与栈的实现大同小异，但是我们需要注意队列的实现不能通过封装vector来适配出队列
1.队列删除队头元素对应的是pop_front，但是在vector中没有该接口
2.vector头插和头删的效率低下
代码实现：
#pragmaoncenamespace hxx {//Container适配转换出queue，队列需要在一段进，另外一端出，这里我们不能使用vector进行适配，因为队列是删除队头元素，vector中没有pop_front接口template<classT,classContainer=list<T>>classqueue{public:voidpush(const T& x){ _con.push_back(x);}//删除队头元素voidpop(){ _con.pop_front();}//获取队头元素const T&front(){return _con.front();}//获取队尾元素const T&back(){return _con.back();} size_t size()const{return _con.size();}boolempty()const{return _con.empty();}private: Container _con;};}三、总结
坚持到这里，已经很棒啦，希望读完本文可以帮读者大大更好了解栈和队列的底层逻辑！！！如果喜欢本文的可以给博主点点免费的攒攒，你们的支持就是我前进的动力🎆
资源分享：栈和队列模拟实现源码
