STL 中的 stack 和 queue 本质是容器适配器，它们基于基础容器（如 vector、deque）封装，屏蔽复杂接口，只暴露特定操作逻辑。这种设计让我们能直接按栈或队列的经典逻辑使用数据，同时享受底层容器的性能优势。
容器适配器原理
适配器就像'转换器'，把不兼容的对象改造为适配特定场景的形式。容器适配器包装底层容器，限制访问方式。例如 stack 遵循后进先出（LIFO），只允许在尾部操作；queue 遵循先进先出（FIFO），队尾入队、队头出队。priority_queue 则关注优先级最高的元素。正因为适配器限制了遍历权限以维护结构特性，所以它们不支持迭代器。
Stack 模拟实现
Stack 默认底层容器是 deque，也可以是 vector 或 list。核心要求是支持 empty、back、push_back、pop_back。
template<class T, class Container = std::deque<T>>
class stack {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_back(); }
const T& top() { return _con.back(); }
bool empty() { return _con.empty(); }
size_t size() { return _con.size(); }
private:
Container _con;
};
这里所有操作都委托给 _con。编译器会自动生成默认成员函数，因为 stack 本身不管理额外资源，底层容器已处理内存。注意 top() 返回 const 引用，防止外部修改栈顶数据。
Queue 模拟实现
Queue 需要支持 front、back、push_back、pop_front。默认也是 deque。
template<class T, class Container = std::deque<T>>
class queue {
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
const T& front() { return _con.front(); }
const T& back() { return _con.back(); }
bool empty() { return _con.empty(); }
size_t size() { return _con.size(); }
private:
Container _con;
};
入队复用 push_back，出队复用 pop_front。同样依赖底层容器的随机访问能力。
典型算法场景
最小栈
需要在 O(1) 时间内获取最小值。思路是用两个栈：一个存数据，一个存历史最小值。新元素入栈时，若小于等于最小栈顶，也压入最小栈；弹出时若相等，同步弹出。
class MinStack {
public:
void push(int val) {
_st.push(val);
if(_minst.empty() || val <= _minst.top()) {
_minst.push(val);
}
}
void pop() {
if(!_minst.empty() && _minst.top() == _st.top()) {
_minst.pop();
}
_st.pop();
}
int getMin() { return _minst.top(); }
private:
std::stack<int> _st;
std::stack<int> _minst;
};
注意空栈保护，实际工程中需判断栈非空再访问 top。
栈的压入弹出序列
验证一个序列是否可能是另一个序列的弹出顺序。模拟入栈过程，每当栈顶匹配弹出序列当前元素，就弹出并移动指针。最后栈空即合法。
bool IsPopOrder(std::vector<int>& pushV, std::vector<int>& popV) {
std::stack<int> st;
int pushi = 0, popi = 0;
while(pushi < pushV.size()) {
st.push(pushV[pushi++]);
while(!st.empty() && st.top() == popV[popi]) {
st.pop();
popi++;
}
}
return st.empty();
}
内层循环处理连续弹出的情况，比单层判断更高效。
逆波兰表达式求值
后缀表达式计算。遇到数字入栈，遇到运算符弹出两个数运算后结果入栈。
int evalRPN(std::vector<std::string>& tokens) {
std::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();
}
这里简化了运算符判断逻辑，实际需区分加减乘除。
用栈实现队列 & 用队列实现栈
利用双栈倒序实现队列功能：一个栈负责入队，另一个负责出队。当出栈栈空时，将入栈栈全部倒入。 反之，用双队列实现栈：始终向非空队列加元素，出栈时将 n-1 个元素移入空队列，最后一个即为栈顶。
这些练习不仅巩固了 STL 用法，更加深了对数据结构转换的理解。掌握这些模式，面对复杂场景时能更快找到切入点。
