C++ 标准库容器适配器详解
在 C++ STL 中，stack、queue 和 priority_queue 是非常常用的数据结构。它们虽然名字像容器，但实际上属于容器适配器。这意味着它们不是直接管理内存的底层容器，而是对其他容器（如 vector、deque、list）的接口进行了封装，提供了特定的操作方式。
一、Stack：后进先出
1. Stack 介绍
stack 遵循后进先出（LIFO）原则。默认情况下，它使用 deque 作为底层容器，但也可以指定 vector 或 list。头文件为 <stack>。
2. Stack 常用接口
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测 stack 是否为空 |
| size() | 返回 stack 中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素 val 压入 stack 中 |
| pop() | 将 stack 中尾部的元素弹出 |
3. 实战案例：最小栈 (Min Stack)
LeetCode 155 题要求设计一个支持 push、pop、top 以及获取最小值 getMin 操作的栈，且所有操作的时间复杂度必须是 O(1)。
思路：
我们可以维护两个栈：主栈 st 用于存储数据，辅助栈 minst 用于记录当前状态下的最小值。当 st 插入新元素时，如果 minst 为空或者新元素小于等于 minst 的栈顶，则同步压入 minst。弹出时，如果 st 的栈顶等于 minst 的栈顶，说明当前最小值即将被移除，minst 也要同步弹出。
代码实现：
class MinStack {
public:
MinStack() {}
void push(int val) {
_st.push(val);
// 如果 minst 为空或者 要插入的值小于 minst 的栈顶元素就插入
if (_minst.empty() || val <= _minst.top())
_minst.push(val);
}
void pop() {
// 如果删除的值和 minst 中的值相等，同时删，否则只删 st
if (!_st.empty() && _st.top() == _minst.top())
_minst.pop();
if (!_st.empty()) _st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;
stack<int> _minst;
};
优化思考：
如果在插入大量重复的最小值时，minst 会占用额外空间。可以定义一个结构体，包含 val 和 count，记录该值的出现次数，从而减少重复存储。
4. 实战案例：栈的压入、弹出序列
判断一个序列是否是另一个序列的合法弹出顺序。
思路： 模拟入栈过程。遍历压栈数组，依次入栈；每次入栈后检查栈顶是否等于当前期望弹出的元素，若相等则出栈并移动弹出指针。最后检查栈是否为空。
代码实现：
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
size_t pushi = 0, popi = 0;
stack<int> st;
while (pushi < pushV.size()) {
st.push(pushV[pushi++]);
while (!st.empty() && popV[popi] == st.top()) {
popi++;
st.pop();
}
}
return st.empty();
}
};
5. 实战案例：逆波兰表达式求值
利用栈处理后缀表达式（逆波兰表达式），遇到数字入栈，遇到运算符则弹出两个数字进行计算。
代码实现：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (auto& str : tokens) {
if ("+" == str || "-" == str || "*" == str || "/" == str) {
int right = s.top(); s.pop();
int left = s.top(); s.pop();
switch (str[0]) {
case '+': s.push(left + right); break;
case '-': s.push(left - right); break;
case '*': s.push(left * right); break;
case '/': s.push(left / right); break;
}
} else {
s.push(stoi(str));
}
}
return s.top();
}
};
6. Stack 模拟实现
了解其本质有助于调试和优化。stack 本质上是对底层容器的包装。
template<class T, class Continer = std::deque<T>>
class stack {
public:
stack() {}
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_back(); }
T& top() { return _con.back(); }
size_t size() { return _con.size(); }
bool empty() { return _con.empty(); }
private:
Continer _con;
};
二、Queue：先进先出
1. Queue 介绍
queue 是 FIFO（先进先出）结构。元素从队尾入队列，从队头出队列。底层容器可以是 deque 或 list，默认为 deque。
2. Queue 常用接口
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空 |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素 val 入队列 |
| pop() | 将队头元素出队列 |
3. Queue 模拟实现
由于需要支持头删，vector 不适用（头删效率低），通常选择 list 或 deque。
template<class T, class Continer = std::list<T>>
class queue {
public:
queue() {}
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_front(); }
T& front() { return _con.front(); }
T& back() { return _con.back(); }
size_t size() { return _con.size(); }
bool empty() { return _con.empty(); }
private:
Continer _con;
};
三、Priority Queue：优先队列
1. Priority Queue 介绍
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的（默认大堆）。底层容器通常是 vector，通过堆算法维持堆结构。
2. Priority Queue 使用
默认情况下，priority_queue 是大堆。如果需要小堆，可以通过仿函数（Functor）来定制比较逻辑。
| 函数声明 | 接口说明 |
|---|---|
| priority_queue() | 构造一个空的优先级队列 |
| empty() | 检测优先级队列是否为空 |
| top() | 返回优先级队列中最大元素 |
| push(x) | 在优先级队列中插入元素 x |
| pop() | 删除优先级队列中最大元素 |
3. OJ 实战：数组中的第 K 个最大元素
利用优先队列可以在 O(N log K) 时间内找到第 K 大元素，比完全排序更高效。
思路：
将数组放入优先级队列，弹出 k-1 次后，剩下的栈顶即为第 K 大元素。
代码实现：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> p(nums.begin(), nums.end());
while (--k) {
p.pop();
}
return p.top();
}
};
4. Priority Queue 模拟实现
这里展示了基于 vector 的手动堆实现，包括向上调整（AdjustUp）和向下调整（AdjustDown）。
基础版（大堆）：
namespace myPriorityQueue {
template<class T, class Container = std::vector<T>>
class priority_queue {
public:
void AdjustUp(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (_con[child] > _con[parent]) {
swap(_con[child], _con[parent]);
child = parent;
parent = (parent - 1) / 2;
} else {
break;
}
}
}
void AdjustDown(int parent) {
int child = parent * 2 + 1;
while (child < _con.size()) {
if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {
++child;
}
if (_con[child] > _con[parent]) {
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void pop() {
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
bool empty() { return _con.empty(); }
const T& top() { return _con[0]; }
size_t size() { return _con.size(); }
private:
Container _con;
};
}
支持仿函数版本（可配置大小堆）：
通过引入 Compare 模板参数，可以灵活控制堆的性质。例如传入 greater<T> 即可实现小堆。
namespace myPriorityQueue {
template<class T>
struct less {
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
template<class T>
struct greater {
bool operator()(const T& x, const T& y) const {
return x > y;
}
};
template<class T, class Container = std::vector<T>, class Compare = greater<T>>
class priority_queue {
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last) : _con(first, last) {
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(i);
}
}
void AdjustUp(int child) {
Compare com;
int parent = (child - 1) / 2;
while (child > 0) {
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
child = parent;
parent = (parent - 1) / 2;
} else {
break;
}
}
}
void AdjustDown(int parent) {
Compare com;
int child = parent * 2 + 1;
while (child < _con.size()) {
if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
++child;
}
if (com(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void pop() {
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
bool empty() { return _con.empty(); }
const T& top() { return _con[0]; }
size_t size() { return _con.size(); }
private:
Container _con;
};
}
四、容器适配器与 Deque
1. 什么是适配器
适配器模式将一个类的接口转换成客户希望的另外一个接口。在 STL 中，stack 和 queue 就是典型的容器适配器，它们不直接管理内存，而是包装其他容器。
2. 为什么选择 Deque 作为默认底层容器
deque（双端队列）是一种分段连续的空间数据结构。它在头部和尾部插入删除都是 O(1)，且扩容时不需要像 vector 那样搬移大量数据。
- 对比 Vector：
deque头插效率高，无需搬移元素。 - 对比 List：
deque空间利用率更高，没有额外的节点指针开销。
虽然 deque 遍历时迭代器较复杂（需检测段边界），但 stack 和 queue 本身不需要遍历，因此 deque 成为了它们的最佳默认搭档。
掌握这些底层原理，能帮助我们在实际开发中更合理地选择数据结构，提升程序性能。