STL 中 stack 与 queue 本质是容器适配器，基于基础容器封装实现特定操作逻辑。本文先介绍容器适配器及二者核心概念，再手动模拟实现，最后通过几道算法题展示其应用，助力夯实 STL 设计思想与数据结构基础。
容器适配器
什么是容器适配器？
适配器可以理解为'转换器'——它能把原本不兼容、不符合需求的对象（比如函数、容器等），改造为可以直接使用、适配特定场景的形式。 容器适配器是适配器的一种，它专门用来包装底层容器（例如 deque、vector）：通过屏蔽底层容器的复杂接口，只暴露栈、队列等特定数据结构的核心操作（比如 stack 的 push/pop，queue 的 front/back），让我们可以直接按照经典数据结构的逻辑来使用它。
为啥容器配置器不支持迭代器
stack：仅允许操作栈顶（遵循后进先出 LIFO 规则），若暴露迭代器，用户就能遍历栈内所有元素，这会破坏它的设计意图。 queue：仅允许操作队首 / 队尾（遵循先进先出 FIFO 规则），迭代器会打破'队列只能从两端操作'的限制。 priority_queue：仅允许操作优先级最高的元素（堆顶），遍历其底层存储（比如用 vector 实现的堆）没有实际意义 —— 底层存储的顺序并非优先级顺序。 容器适配器的价值，正是用极简的接口解决特定场景的问题（比如栈只需要 push/pop/top）。而迭代器是'通用遍历'的工具，和适配器'限制访问'的核心目标完全相悖，因此二者天生不兼容。 在 C++ STL 中，容器适配器只有上述 3 种，本文我们只讲解前两种。
stack
1、stack 介绍
stack 的定位：stack 是一种容器适配器，专门用于'后进先出（LIFO）'的场景，元素的插入和提取操作只能在容器的一端进行。 stack 的实现逻辑：作为容器适配器，stack 是通过包装某一底层容器实现的 —— 它会以该容器为基础，提供一组特定的成员函数来访问元素；其中，底层容器的尾部会被当作栈顶，元素的压入、弹出操作都在这一端完成。 stack 对底层容器的要求：stack 的底层容器可以是任意标准容器模板，或是满足以下操作的特定容器：
**empty：**判断容器是否为空 **back：**获取容器尾部的元素 **push_back：**在容器尾部插入元素 **pop_back：**删除容器尾部的元素 默认底层容器：标准容器 vector、deque、list 都满足上述要求；若未显式指定 stack 的底层容器，默认会使用 deque。
2、stack 模拟实现
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、最小栈
题目描述：实现一个最小栈，支持 push、pop、top 以及获取最小元素的操作。 思路分析：用一个数据栈存储所有入栈元素，另一个最小值栈同步维护对应阶段的栈内最小值；入栈时仅当新元素小于等于最小值栈顶（或最小值栈为空）时，才将其压入最小值栈；出栈时若弹出的元素是当前最小值（与最小值栈顶相等），则同步弹出最小值栈顶；获取最小值直接返回最小值栈顶，实现 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、栈的压入、弹出序列
题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。 思路分析：模拟栈的入栈、出栈过程，最终栈为空则代表符合规则：先将元素入栈，若当前入栈元素与出栈数组的待匹配元素一致，则让该入栈元素出栈，同时出栈数组的匹配指针后移；重复这一过程，直到所有元素处理完后，若栈为空，说明入栈、出栈的顺序是合法的。 示例代码：
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、逆波兰表达式求值
题目描述：根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, /。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 思路解析：遍历 tokens，遇到数字入栈，遇到运算符则弹出栈顶两个元素进行计算，结果再入栈。 代码示例：
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、用栈实现队列
题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。 思路分析：使用两个栈，一个用于入队（push_st），一个用于出队（pop_st）。入队时直接压入 push_st。出队时，如果 pop_st 为空，则将 push_st 中的所有元素依次弹出并压入 pop_st，此时 pop_st 的栈顶即为队头元素。 代码示例：
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、用队列实现栈
题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。 思路分析：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; };
