主页传送门:良木生香个人专栏:《C语言》《数据结构-初阶》《鼠鼠的C学习之路》《Linux系统编程》人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离一、前言在 C STL 中stack和queue是非常常用的容器。但很多人只停留在会用的层面对其底层实现、设计思想以及经典应用场景并不熟悉。那么今天就从容器适配器的设计思想出发深入讲解stack和queue的底层原理并配合经典面试题帮助大家彻底掌握这部分知识。二、Stack 与 Queue 的本质容器适配器2.1 什么是容器适配器适配器Adapter是一种设计模式将一个类的接口转换成用户期望的另一个接口。stack和queue本质上不是独立的容器而是在已有容器基础上封装的适配器。它们不自己管理数据而是复用底层容器的接口只暴露栈/队列特有的操作。// stack 的声明底层默认用 dequetemplateclassT,classContainerdequeTclassstack;// queue 的声明底层默认也用 dequetemplateclassT,classContainerdequeTclassqueue;2.2 为什么叫适配器底层容器Vector/List/Deque ┌─────────────────────────────┐ │ push_back() pop_back() │ │ push_front() pop_front()│ │ insert() erase() │ │ operator[] front() │ │ ... │ └──────────┬──────────────────┘ │ 适配限制接口 ↓ 栈接口只暴露这几个 ┌─────────────┐ │ push() │ ← 底层调用 push_back │ pop() │ ← 底层调用 pop_back │ top() │ ← 底层调用 back │ size() │ │ empty() │ └─────────────┘2.3 底层容器的选择容器适配器默认底层可选底层说明stackdequeTvectorT、listT只需要尾插尾删queuedequeTlistT需要头删尾插不能用 vector没有pop_front⚠️队列不能用 vector 的pop_front()因为 vector 头删需要 O(n) 移动所有元素。三、Stack后进先出LIFO3.1 核心特性push(5) ↓ ┌─────────┐ │ 5 │ ← 栈顶最后入栈最先出栈 ├─────────┤ │ 4 │ ├─────────┤ │ 3 │ ├─────────┤ │ 2 │ ├─────────┤ │ 1 │ ← 栈底最先入栈最后出栈 └─────────┘3.2 模拟实现基于 VectortemplatetypenameT,typenameContainervectorTclassStack{public:voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_back();}Ttop(){return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};3.3 时间复杂度操作复杂度说明pushO(1)尾插popO(1)尾删topO(1)访问末尾元素四、Queue先进先出FIFO4.1 核心特性出队pop 入队push ↓ ↓ ┌───────┬───────┬───────┬───────┐ │ 1 │ 2 │ 3 │ 4 │ └───────┴───────┴───────┴───────┘ ↑ ↑ front back 入队顺序1 → 2 → 3 → 4 出队顺序1 → 2 → 3 → 4完全相同4.2 模拟实现基于 ListtemplatetypenameT,typenameContainerlistTclassQueue{public:voidpush(constTx){_con.push_back(x);}// 队尾入voidpop(){_con.pop_front();}// 队头出Tfront(){return_con.front();}Tback(){return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};4.3 循环队列数组实现templatetypenameT,size_t NclassCircularQueue{T _data[N];size_t _front0,_rear0,_size0;public:boolpush(constTx){if(_sizeN)returnfalse;_data[_rear]x;_rear(_rear1)%N;_size;returntrue;}boolpop(){if(_size0)returnfalse;_front(_front1)%N;--_size;returntrue;}Tfront(){return_data[_front];}boolempty()const{return_size0;}boolfull()const{return_sizeN;}};五、List 迭代器的operator-重载5.1 问题场景当 List 中存储的是结构体时如何通过迭代器访问成员structPoint{int_x,_y;};ListPointpoints;points.push_back({1,2});autoitpoints.begin();// (*it)._x 10; // 方式1先解引用再访问成员// it-_x 10; // 方式2更简洁需要 operator- 支持6.2operator-的实现templatetypenameT,typenameRef,typenamePtrstruct__ListIterator{Node*_node;// 解引用返回 data 的引用Refoperator*(){return_node-_data;}// 返回 data 的指针Ptroperator-(){return_node-_data;}};// it-x 的调用过程// it.operator-() → _node-_data → (_node-_data)-x// 编译器会自动优化为直接访问成员六、经典面试题详解6.1 最小栈O(1) 获取最小值思路用两个栈一个存数据一个存最小值。classMinStack{stackint_data;// 数据栈stackint_min;// 辅助栈存当前最小值public:voidpush(intx){_data.push(x);// 如果 x 比之前的最小值还小或等于压入 xif(_min.empty()||x_min.top()){_min.push(x);}else{_min.push(_min.top());// 重复压入当前最小值}}voidpop(){_data.pop();_min.pop();}inttop(){return_data.top();}intgetMin(){return_min.top();}};// push 5: _data[5], _min[5]// push 2: _data[5,2], _min[5,2]// push 7: _data[5,2,7], _min[5,2,2]// push 1: _data[5,2,7,1], _min[5,2,2,1]// getMin() → 1// pop() → _data[5,2,7], _min[5,2,2]// getMin() → 2⚠️注意当data min.top()时minst不 push。但相同 min 时两边同时进否则删除后minst不更新6.2 栈的压入/弹出序列验证思路用辅助栈模拟入栈过程同时比较出栈序列。boolvalidateStackSequences(vectorintpushed,vectorintpopped){stackintst;intj0;// 指向 popped 的索引for(intx:pushed){st.push(x);// 入栈序列入栈// 栈顶与出栈序列比较while(!st.empty()st.top()popped[j]){st.pop();j;// 匹配成功继续比较下一个}}// 当入栈序列走完但出栈序列不为空则为 falsereturnst.empty();}6.3 逆波兰表达式求解中缀转后缀示例中缀1 2 × (3 4) / 5 后缀1 2 3 4 × 5 / 计算过程 遇到 1压栈 [1] 遇到 2压栈 [1, 2] 遇到 3压栈 [1, 2, 3] 遇到 4压栈 [1, 2, 3, 4] 遇到 弹出 4 和 3计算 347压栈 [1, 2, 7] 遇到 ×弹出 7 和 2计算 2×714压栈 [1, 14] 遇到 5压栈 [1, 14, 5] 遇到 /弹出 5 和 14计算 14/52压栈 [1, 2] 遇到 弹出 2 和 1计算 123压栈 [3] 结果3intevalRPN(vectorstringtokens){stackintst;for(conststringtoken:tokens){if(token||token-||token*||token/){intbst.top();st.pop();intast.top();st.pop();if(token)st.push(ab);elseif(token-)st.push(a-b);elseif(token*)st.push(a*b);elseif(token/)st.push(a/b);}else{st.push(stoi(token));}}returnst.top();}6.4 用两个栈实现队列classMyQueue{stackint_in;// 入队栈stackint_out;// 出队栈public:voidpush(intx){_in.push(x);}intpop(){peek();intval_out.top();_out.pop();returnval;}intpeek(){if(_out.empty()){while(!_in.empty()){_out.push(_in.top());_in.pop();}}return_out.top();}boolempty(){return_in.empty()_out.empty();}};6.5 二叉树的层序遍历队列应用vectorvectorintlevelOrder(TreeNode*root){vectorvectorintresult;if(!root)returnresult;queueTreeNode*q;q.push(root);while(!q.empty()){intlevelSizeq.size();vectorintlevel;for(inti0;ilevelSize;i){TreeNode*nodeq.front();q.pop();level.push_back(node-val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}result.push_back(level);}returnresult;}七、总结容器适配器核心特性底层结构典型应用stackLIFOdeque/vector/list括号匹配、DFS、函数调用、撤销queueFIFOdeque/listBFS、消息队列、任务调度关键要点回顾容器适配器stack和queue不是独立容器而是复用底层容器的适配器队列不能用 vector因为 vector 没有高效的pop_front()默认底层stack和queue默认用deque最小栈双栈实现辅助栈同步压入当前最小值逆波兰表达式遇到数字入栈遇到运算符弹出两个数计算栈序列验证辅助栈模拟入栈同时比较出栈序列那么以上就是本次所有的内容了文章是自己写的哈有什么描述不对的、不恰当的地方恳请大佬指正看到后会第一时间修改感谢您的阅读~~~~
【C++初阶】STL—— Stack Queue 从入门到精通：容器适配器、迭代器与经典面试题
主页传送门:良木生香个人专栏:《C语言》《数据结构-初阶》《鼠鼠的C学习之路》《Linux系统编程》人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离一、前言在 C STL 中stack和queue是非常常用的容器。但很多人只停留在会用的层面对其底层实现、设计思想以及经典应用场景并不熟悉。那么今天就从容器适配器的设计思想出发深入讲解stack和queue的底层原理并配合经典面试题帮助大家彻底掌握这部分知识。二、Stack 与 Queue 的本质容器适配器2.1 什么是容器适配器适配器Adapter是一种设计模式将一个类的接口转换成用户期望的另一个接口。stack和queue本质上不是独立的容器而是在已有容器基础上封装的适配器。它们不自己管理数据而是复用底层容器的接口只暴露栈/队列特有的操作。// stack 的声明底层默认用 dequetemplateclassT,classContainerdequeTclassstack;// queue 的声明底层默认也用 dequetemplateclassT,classContainerdequeTclassqueue;2.2 为什么叫适配器底层容器Vector/List/Deque ┌─────────────────────────────┐ │ push_back() pop_back() │ │ push_front() pop_front()│ │ insert() erase() │ │ operator[] front() │ │ ... │ └──────────┬──────────────────┘ │ 适配限制接口 ↓ 栈接口只暴露这几个 ┌─────────────┐ │ push() │ ← 底层调用 push_back │ pop() │ ← 底层调用 pop_back │ top() │ ← 底层调用 back │ size() │ │ empty() │ └─────────────┘2.3 底层容器的选择容器适配器默认底层可选底层说明stackdequeTvectorT、listT只需要尾插尾删queuedequeTlistT需要头删尾插不能用 vector没有pop_front⚠️队列不能用 vector 的pop_front()因为 vector 头删需要 O(n) 移动所有元素。三、Stack后进先出LIFO3.1 核心特性push(5) ↓ ┌─────────┐ │ 5 │ ← 栈顶最后入栈最先出栈 ├─────────┤ │ 4 │ ├─────────┤ │ 3 │ ├─────────┤ │ 2 │ ├─────────┤ │ 1 │ ← 栈底最先入栈最后出栈 └─────────┘3.2 模拟实现基于 VectortemplatetypenameT,typenameContainervectorTclassStack{public:voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_back();}Ttop(){return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};3.3 时间复杂度操作复杂度说明pushO(1)尾插popO(1)尾删topO(1)访问末尾元素四、Queue先进先出FIFO4.1 核心特性出队pop 入队push ↓ ↓ ┌───────┬───────┬───────┬───────┐ │ 1 │ 2 │ 3 │ 4 │ └───────┴───────┴───────┴───────┘ ↑ ↑ front back 入队顺序1 → 2 → 3 → 4 出队顺序1 → 2 → 3 → 4完全相同4.2 模拟实现基于 ListtemplatetypenameT,typenameContainerlistTclassQueue{public:voidpush(constTx){_con.push_back(x);}// 队尾入voidpop(){_con.pop_front();}// 队头出Tfront(){return_con.front();}Tback(){return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};4.3 循环队列数组实现templatetypenameT,size_t NclassCircularQueue{T _data[N];size_t _front0,_rear0,_size0;public:boolpush(constTx){if(_sizeN)returnfalse;_data[_rear]x;_rear(_rear1)%N;_size;returntrue;}boolpop(){if(_size0)returnfalse;_front(_front1)%N;--_size;returntrue;}Tfront(){return_data[_front];}boolempty()const{return_size0;}boolfull()const{return_sizeN;}};五、List 迭代器的operator-重载5.1 问题场景当 List 中存储的是结构体时如何通过迭代器访问成员structPoint{int_x,_y;};ListPointpoints;points.push_back({1,2});autoitpoints.begin();// (*it)._x 10; // 方式1先解引用再访问成员// it-_x 10; // 方式2更简洁需要 operator- 支持6.2operator-的实现templatetypenameT,typenameRef,typenamePtrstruct__ListIterator{Node*_node;// 解引用返回 data 的引用Refoperator*(){return_node-_data;}// 返回 data 的指针Ptroperator-(){return_node-_data;}};// it-x 的调用过程// it.operator-() → _node-_data → (_node-_data)-x// 编译器会自动优化为直接访问成员六、经典面试题详解6.1 最小栈O(1) 获取最小值思路用两个栈一个存数据一个存最小值。classMinStack{stackint_data;// 数据栈stackint_min;// 辅助栈存当前最小值public:voidpush(intx){_data.push(x);// 如果 x 比之前的最小值还小或等于压入 xif(_min.empty()||x_min.top()){_min.push(x);}else{_min.push(_min.top());// 重复压入当前最小值}}voidpop(){_data.pop();_min.pop();}inttop(){return_data.top();}intgetMin(){return_min.top();}};// push 5: _data[5], _min[5]// push 2: _data[5,2], _min[5,2]// push 7: _data[5,2,7], _min[5,2,2]// push 1: _data[5,2,7,1], _min[5,2,2,1]// getMin() → 1// pop() → _data[5,2,7], _min[5,2,2]// getMin() → 2⚠️注意当data min.top()时minst不 push。但相同 min 时两边同时进否则删除后minst不更新6.2 栈的压入/弹出序列验证思路用辅助栈模拟入栈过程同时比较出栈序列。boolvalidateStackSequences(vectorintpushed,vectorintpopped){stackintst;intj0;// 指向 popped 的索引for(intx:pushed){st.push(x);// 入栈序列入栈// 栈顶与出栈序列比较while(!st.empty()st.top()popped[j]){st.pop();j;// 匹配成功继续比较下一个}}// 当入栈序列走完但出栈序列不为空则为 falsereturnst.empty();}6.3 逆波兰表达式求解中缀转后缀示例中缀1 2 × (3 4) / 5 后缀1 2 3 4 × 5 / 计算过程 遇到 1压栈 [1] 遇到 2压栈 [1, 2] 遇到 3压栈 [1, 2, 3] 遇到 4压栈 [1, 2, 3, 4] 遇到 弹出 4 和 3计算 347压栈 [1, 2, 7] 遇到 ×弹出 7 和 2计算 2×714压栈 [1, 14] 遇到 5压栈 [1, 14, 5] 遇到 /弹出 5 和 14计算 14/52压栈 [1, 2] 遇到 弹出 2 和 1计算 123压栈 [3] 结果3intevalRPN(vectorstringtokens){stackintst;for(conststringtoken:tokens){if(token||token-||token*||token/){intbst.top();st.pop();intast.top();st.pop();if(token)st.push(ab);elseif(token-)st.push(a-b);elseif(token*)st.push(a*b);elseif(token/)st.push(a/b);}else{st.push(stoi(token));}}returnst.top();}6.4 用两个栈实现队列classMyQueue{stackint_in;// 入队栈stackint_out;// 出队栈public:voidpush(intx){_in.push(x);}intpop(){peek();intval_out.top();_out.pop();returnval;}intpeek(){if(_out.empty()){while(!_in.empty()){_out.push(_in.top());_in.pop();}}return_out.top();}boolempty(){return_in.empty()_out.empty();}};6.5 二叉树的层序遍历队列应用vectorvectorintlevelOrder(TreeNode*root){vectorvectorintresult;if(!root)returnresult;queueTreeNode*q;q.push(root);while(!q.empty()){intlevelSizeq.size();vectorintlevel;for(inti0;ilevelSize;i){TreeNode*nodeq.front();q.pop();level.push_back(node-val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}result.push_back(level);}returnresult;}七、总结容器适配器核心特性底层结构典型应用stackLIFOdeque/vector/list括号匹配、DFS、函数调用、撤销queueFIFOdeque/listBFS、消息队列、任务调度关键要点回顾容器适配器stack和queue不是独立容器而是复用底层容器的适配器队列不能用 vector因为 vector 没有高效的pop_front()默认底层stack和queue默认用deque最小栈双栈实现辅助栈同步压入当前最小值逆波兰表达式遇到数字入栈遇到运算符弹出两个数计算栈序列验证辅助栈模拟入栈同时比较出栈序列那么以上就是本次所有的内容了文章是自己写的哈有什么描述不对的、不恰当的地方恳请大佬指正看到后会第一时间修改感谢您的阅读~~~~
