【STL】stack/queue 底层模拟实现与典型算法场景实践

namespace bit { // 容器适配器：模拟实现stack（LIFO 后进先出） // T：元素类型；Container：底层存储容器，默认deque<T> template<class T, class Container = deque<T>> class stack { public: // 压栈：将x插入栈顶 void push(const T& x) { _con.push_back(x); } // 出栈：删除栈顶元素（不返回值） void pop() { _con.pop_back(); } // 获取栈顶元素（const引用返回，避免拷贝） const T& top() { return _con.back(); } // 判断栈是否为空 bool empty() { return _con.empty(); } // 获取栈中元素个数 size_t size() { return _con.size(); } private: Container _con; // 底层容器，实际存储数据 }; }

deque 是双端队列，虽名字带 “队列”，但和 FIFO 结构的队列无实际关联。它是支持头尾高效增删、可随机访问的双端动态容器，是 STL 中灵活高效的基础容器之一。下一章会简单介绍它，目前大家可以先把它当作类似 vector 和 list 的容器来理解。

Container _con：是stack的底层容器对象，实际存储所有元素；stack的所有操作都是通过封装这个容器的接口实现的（体现 “适配器” 的封装思想）。

☃. 接口介绍：

push(const T& x)：调用底层容器_con的push_back，把元素x插入到栈顶（对应容器尾部）。

pop()：调用_con的pop_back，删除栈顶元素（不返回值）。

const T& top()：返回_con.back()，即栈顶元素的const引用（避免拷贝，也防止外部修改）。

empty()：返回_con.empty()的结果，判断栈是否为空。

size()：返回_con.size()，获取栈中元素的个数。

问题：为啥 stack 不用提供默认成员函数？

回答：因为编译器会自动为stack生成默认成员函数（包括默认构造、拷贝构造、赋值重载、析构函数等），而这些自动生成的函数会调用底层容器（如deque）的对应函数 —— 比如默认构造调用容器的无参构造、拷贝构造调用容器的拷贝构造，能完整实现stack的初始化、拷贝、资源释放等需求。同时stack是容器适配器，自身不管理额外动态资源，所有功能都依赖底层容器，因此无需手动提供默认成员函数。

---------------queue--------------

1、queue介绍

queue 的定位：队列是一种容器适配器，专门用于在 FIFO（先进先出）上下文中操作，其中从容器一端插入元素，另一端提取元素。

queue 的实现逻辑：队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

queue 对底层容器的要求：底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

empty：检测队列是否为空

size：返回队列中有效元素的个数

front：返回队头元素的引用

back：返回队尾元素的引用

push_back：在队列尾部入队列

pop_front：在队列头部出队列

queue 的默认底层容器：标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。

2、queue模拟实现

namespace bit { // 容器适配器：模拟实现queue（FIFO 先进先出） // T：元素类型；Container：底层存储容器，默认用deque<T> template<class T, class Container = deque<T>> class queue { public: // 入队：将元素x插入队列尾部（复用底层容器的尾插） void push(const T& x) { _con.push_back(x); } // 出队：删除队列头部元素（复用底层容器的头删） void pop() { _con.pop_front(); } // 获取队列头部元素（const引用返回，避免拷贝、防止外部修改） const T& front() { return _con.front(); } // 获取队列尾部元素（const引用返回，避免拷贝、防止外部修改） const T& back() { return _con.back(); } // 判断队列是否为空（复用底层容器的判空） bool empty() { return _con.empty(); } // 获取队列中元素的个数（复用底层容器的size） size_t size() { return _con.size(); } private: Container _con; // 底层容器，实际存储队列的所有元素 }; }

Container _con： 是 queue 的底层容器对象，实际存储所有元素；queue 的所有操作都是通过封装这个容器的接口实现的（体现 “适配器” 的封装思想）。

☃. 接口介绍：

push (const T& x)： 调用底层容器_con 的 push_back，把元素 x 插入到队列尾部（对应容器尾部）。

pop ()：调用_con 的 pop_front，删除队列头部元素（不返回值）。

const T& front ()：返回_con.front ()，即队列头部元素的 const 引用（避免拷贝，也防止外部修改）。

const T& back ()：返回_con.back ()，即队列尾部元素的 const 引用（避免拷贝，也防止外部修改）。

empty ()：返回_con.empty () 的结果，判断队列是否为空。

size ()：返回_con.size ()，获取队列中元素的个数。

--------------算法题--------------

1、最小栈

【题目链接】：https://leetcode.cn/problems/min-stack/description/

【思路分析】

用一个数据栈存储所有入栈元素，另一个最小值栈同步维护对应阶段的栈内最小值；入栈时仅当新元素小于等于最小值栈顶（或最小值栈为空）时，才将其压入最小值栈；出栈时若弹出的元素是当前最小值（与最小值栈顶相等），则同步弹出最小值栈顶；获取最小值直接返回最小值栈顶，实现 O (1) 时间复杂度的查询，同时保证入栈、出栈操作高效可行。

【示例代码】

class MinStack { public: MinStack() { } void push(int val) { _st.push(val); // 压入数据栈 // 维护最小值栈，空或当前值≤栈顶时压入 if(_minst.empty() || val <= _minst.top()) { _minst.push(val); } } void pop() { // 弹出的是最小值时，同步弹出最小值栈 if(_minst.top() == _st.top()) { _minst.pop(); } _st.pop(); // 弹出数据栈 } int top() { return _st.top(); // 返回数据栈顶 } int getMin() { return _minst.top(); // 返回最小值栈顶 } private: stack<int> _st; // 数据栈：存储所有元素 stack<int> _minst; // 最小值栈：存储各阶段最小值 };

2、栈的压入、弹出序列

【题目链接】：https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106

【思路分析】

模拟栈的入栈、出栈过程，最终栈为空则代表符合规则：

先将元素入栈，若当前入栈元素与出栈数组的待匹配元素一致，则让该入栈元素出栈，同时出栈数组的匹配指针后移；重复这一过程，直到所有元素处理完后，若栈为空，说明入栈、出栈的顺序是合法的。

【示例代码】

class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> st;//模拟出入栈 int pushi = 0; int popi = 0; //入完了就跳出循环 while(pushi < pushV.size()) { st.push(pushV[pushi++]); //不匹配 if(st.top() != popV[popi]) { continue; }//匹配 else { while(!st.empty() && st.top() == popV[popi]) { popi++; st.pop(); } } } //等于空说明符合栈的规则 return st.empty(); } };

3、逆波兰表达式求值

【题目链接】：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

【思路解析】

【代码示例】

class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(auto& e: tokens) { //操作符 取栈顶两个元素进行运算，运算结果入栈 if(e == "+" ||e== "-" || e== "*" || e== "/") { int right = st.top(); st.pop(); int left = st.top(); st.pop(); switch(e[0]) { case '+': st.push(left+right); break; case '-': st.push(left-right); break; case '*': st.push(left*right); break; case '/': st.push(left/right); break; } } else//操作数直接入栈 { //字符串转整型 st.push(stoi(e)); } } return st.top(); } };

4、用栈实现队列

【题目链接】：https://leetcode.cn/problems/implement-queue-using-stacks/

【思路分析】

【代码示例】

class MyQueue { public: // 构造函数：编译器自动生成，初始化两个空栈 MyQueue() { } // 入队操作：将元素x加入队列（直接压入push_st栈） void push(int x) { push_st.push(x); } // 出队操作：移除并返回队列的队头元素 int pop() { // 1. 若pop_st为空，将push_st中的所有元素倒序转移到pop_st中 // 转移后pop_st的栈顶即为队列的队头元素 if(pop_st.empty()) { while(!push_st.empty()) { int top = push_st.top(); push_st.pop(); pop_st.push(top); } } // 2. 保护逻辑：若两个栈都为空（队列空），返回0 if(pop_st.empty()) { return 0; } // 3. 弹出pop_st栈顶（即队列队头）并返回 int top = pop_st.top(); pop_st.pop(); return top; } // 查看队头元素：返回队列的队头元素（不移除） int peek() { // 1. 若pop_st为空，将push_st中的所有元素倒序转移到pop_st中 if(pop_st.empty()) { while(!push_st.empty()) { int top = push_st.top(); push_st.pop(); pop_st.push(top); } } // 2. 保护逻辑：若两个栈都为空（队列空），返回0 if(pop_st.empty()) { return 0; } // 3. 返回pop_st栈顶（即队列队头），不弹出元素 int top = pop_st.top(); return top; } // 判断队列是否为空：两个栈都为空时，队列才为空 bool empty() { return push_st.empty() && pop_st.empty(); } private: stack<int> push_st; // 入数据栈：专门接收新加入队列的元素 stack<int> pop_st; // 出数据栈：专门用于弹出/查看队列的队头元素 };

5、用队列实现栈

【题目链接】：https://leetcode.cn/problems/implement-stack-using-queues/

【思路分析】

push 操作：始终向 “非空的队列” 中加入元素（保证新元素在队列尾部，最终成为栈顶）；

pop 操作：将非空队列的元素（除了最后一个）全部倒入空队列，剩下的最后一个元素就是栈顶，直接弹出即可。

【代码示例】

class MyStack { public: MyStack() { } // 入栈：压入非空队列（双空则入q2） void push(int x) { if(!q1.empty()) { q1.push(x); } else { q2.push(x); } } int pop() { // 情况1：q1为空，处理q2 if(q1.empty()) { // 将q2前n-1个元素导入q1，保留最后一个作为栈顶 while(q2.size()>1) { int front = q2.front(); q2.pop(); q1.push(front); } // 取出并弹出q2中仅剩的栈顶元素 int ret = q2.front(); q2.pop(); return ret; } // 情况2：q2为空，处理q1（逻辑同q2） else { while(q1.size()>1) { int front = q1.front(); q1.pop(); q2.push(front); } int ret = q1.front(); q1.pop(); return ret; } // 栈空保护：两个队列都为空时返回0（注：此语句无法执行，已提前在top()处理） if(empty()) { return 0; } } // 取栈顶：返回非空队列的队尾，栈空返回0 int top() { if(!q1.empty()) { return q1.back(); } else if(!q2.empty()) { return q2.back(); } else { return 0; } } // 判断栈空：两个队列都为空即为栈空 bool empty() { return q1.empty() && q2.empty(); } queue<int> q1; queue<int> q2; };