容器适配器深度解析：从 STL 的 stack、queue 到优先队列的底层实现
1. 栈的介绍和使用
1.1 栈的介绍
栈（stack）是一种后进先出（LIFO）的数据结构，它允许在一端进行插入和删除操作。在 C++ STL 中，stack 是一个容器适配器，提供了一组特定的成员函数来访问其元素。
1.2 栈的使用
| 函数 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测 stack 是否为空 |
| size() | 返回 stack 中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素 val 压入 stack 中 |
| pop() | 将 stack 中尾部的元素弹出 |
最小栈实现
最小栈能够在 O(1) 时间内获取栈中的最小元素。
class MinStack {
public:
void push(int x) {
// 压栈时，先将元素保存到_elem
_elem.push(x);
// 如果 x 小于_min 中栈顶的元素，将 x 再压入_min 中
if (_min.empty() || x <= _min.top()) {
_min.push(x);
}
}
void pop() {
// 如果_min 栈顶的元素等于出栈的元素，_min 顶的元素要移除
if (_min.top() == _elem.top()) {
_min.pop();
}
_elem.pop();
}
int top() {
return _elem.top();
}
int getMin() {
return _min.top();
}
private:
std::stack<int> _elem; // 保存栈中的元素
std::stack<int> _min; // 保存栈的最小值
};
栈的弹出压入序列
验证一个序列是否是栈的弹出序列。
class StackPopValidator {
public:
StackPopValidator() {}
void push(int val) {
st.push(val);
if (minst.empty() || minst.top() >= val) {
minst.push(val);
}
}
void pop() {
if (st.top() == minst.top()) {
minst.pop();
}
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return minst.top();
}
private:
std::stack<int> st;
std::stack<int> minst;
};
逆波兰表达式求值
class Solution {
public:
int evalRPN(std::vector<std::string>& tokens) {
std::stack<int> s;
for (size_t i = 0; i < tokens.size(); ++i) {
std::string& str = tokens[i];
// str 为数字
if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
s.push(std::atoi(str.c_str()));
} else {
// 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;
}
}
}
return s.top();
}
};
1.3 stack 的模拟实现
以下是使用容器适配器模式实现的 stack，支持自定义底层容器（默认使用 deque）：
#pragma once
#include <deque>
namespace bit {
// container 适配器实现 stack
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() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() { return _con.empty(); }
private:
Container _con;
};
}
2. 队列的介绍和使用
2.1 队列的介绍
队列是一种先进先出（FIFO）的数据结构，元素从队尾入队列，从队头出队列。在 C++ STL 中，queue 是一个容器适配器。
queue 的特点：
- 队列是一种容器适配器，专门用于在 FIFO 上下文（先进先出）中操作
- 元素从队尾入队列，从队头出队列
- 底层容器可以是 deque 或 list，默认使用 deque
2.2 queue 的使用
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空 |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素 val 入队列 |
| pop() | 将队头元素出队列 |
2.3 queue 的模拟实现
使用容器适配器模式实现的 queue，支持自定义底层容器：
#pragma once
#include <deque>
namespace bit {
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() const { return _con.front(); }
const T& back() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() { return _con.empty(); }
private:
Container _con;
};
}
3. 优先队列的介绍和使用
3.1 priority_queue 的介绍
优先队列是一种容器适配器，它的第一个元素总是它所包含的元素中最大的（默认大堆）。
priority_queue 的特点：
- 第一个元素总是最大的（默认大堆）
- 类似于堆，可以随时插入元素，只能检索最大堆元素
- 默认使用 vector 作为底层容器
- 支持随机访问迭代器
3.2 priority_queue 的使用
| 函数声明 | 接口说明 |
|---|---|
| priority_queue() | 构造一个空的优先级队列 |
| priority_queue(first, last) | 用迭代器范围构造优先级队列 |
| empty() | 检测优先级队列是否为空 |
| top() | 返回优先级队列中最大 (最小) 元素 |
| push(x) | 在优先级队列中插入元素 x |
| pop() | 删除优先级队列中最大 (最小) 元素 |
使用示例：
#include <vector>
#include <queue>
#include <functional> // greater 算法的头文件
void TestPriorityQueue() {
// 默认情况下，创建的是大堆，其底层按照小于号比较
std::vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
std::priority_queue<int> q1;
for (auto& e : v) q1.push(e);
std::cout << q1.top() << std::endl; // 输出 9
// 创建小堆，将第三个模板参数换成 greater 比较方式
std::priority_queue<int, std::vector<int>, std::greater<int>> q2(v.begin(), v.end());
std::cout << q2.top() << std::endl; // 输出 0
}
注意：
- 默认情况下，priority_queue 是大堆
- 如果要创建小堆，需要指定第三个模板参数为
greater<T> - 如果存放自定义类型，需要在自定义类型中提供
>或<的重载
3.3 priority_queue 的模拟实现
以下是完整的优先队列模拟实现，包含大堆和小堆支持：
#pragma once
#include <vector>
namespace bit {
// 仿函数类：Less（升序/大堆）
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) {
return x < y;
}
};
// 仿函数类：Greater（降序/小堆）
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) {
return x > y;
}
};
// 优先队列实现
// 模板参数：
// T - 元素类型
// Container - 底层容器，默认 vector<T>
// Compare - 比较器，默认 Less<T>（大堆）
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_queue {
public:
// 向上调整（插入时使用）
void AdjustUp(int child) {
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0) {
// 使用仿函数进行比较
if (com(_con[parent], _con[child])) {
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
// 向下调整（删除时使用）
void AdjustDown(int parent) {
int child = parent * 2 + 1;
Compare com;
while (child < _con.size()) {
// 找出较大（或较小）的孩子
if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
++child;
}
// 如果父节点小于（或大于）孩子节点，交换
if (com(_con[parent], _con[child])) {
std::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() {
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
// 获取堆顶元素
const T& top() {
return _con[0];
}
// 获取元素个数
size_t size() const {
return _con.size();
}
// 判断是否为空
bool empty() const {
return _con.empty();
}
private:
Container _con;
};
}
4. 容器适配器
4.1 什么是适配器
适配器是一种设计模式，将一个类的接口转换成客户希望的另外一个接口。
4.2 STL 标准库中 stack 和 queue 的底层结构
stack 和 queue 在 STL 中称为容器适配器，它们只是对其他容器的接口进行了包装。STL 中 stack 和 queue 默认使用 deque 作为底层容器。
4.3 deque 的简单介绍
4.3.1 deque 的原理介绍
deque（双端队列）是一种双开口的"连续"空间的数据结构：
- 可以在头尾两端进行插入和删除操作，时间复杂度为 O(1)
- 与 vector 比较，头插效率高，不需要搬移元素
- 与 list 比较，空间利用率比较高
deqe 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际类似于一个动态的二维数组。
4.3.2 deque 的缺陷
- 不适合遍历，因为迭代器要频繁检测是否移动到小空间边界
- 在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list
- deque 的应用并不多，主要作为 stack 和 queue 的底层数据结构
4.4 为什么选择 deque 作为 stack 和 queue 的底层默认容器
- stack 和 queue 不需要遍历（因此没有迭代器），只需要在固定的一端或两端操作
- 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）
- queue 中的元素增长时，deque 不仅效率高，而且内存使用率高
4.5 容器适配器设计的关键点
从上面的模拟实现可以看出容器适配器的核心设计思想：
- 模板参数灵活性：
- stack 和 queue 都支持自定义底层容器
- priority_queue 支持自定义比较器，实现大堆/小堆切换
- 接口统一性：
- 所有适配器都提供 push、pop、top/front/back、size、empty 等标准接口
- 隐藏底层容器的具体实现细节
- 代码复用：
- 通过组合已有的容器实现新功能
- 减少代码重复，提高开发效率
总结
栈、队列和优先队列是三种基础且重要的数据结构，在 C++ STL 中通过容器适配器的方式实现。理解它们的底层原理、使用场景和实现方式，对于提高编程能力和解决实际问题都有重要意义。
通过模拟实现这些数据结构，我们可以：
- 深入理解容器适配器设计模式
- 掌握仿函数在泛型编程中的应用
- 理解堆算法的实现原理
- 学会如何设计灵活的、可扩展的数据结构
在实际开发中，根据具体需求选择合适的数据结构：
- 需要后进先出操作时选择栈
- 需要先进先出操作时选择队列
- 需要快速获取最大/最小值时选择优先队列
