C++算法
容器适配器深度解析：STL 栈、队列与优先队列底层实现
深入解析 C++ STL 中的容器适配器，涵盖栈（stack）、队列（queue）及优先队列（priority_queue）。介绍了它们的数据结构特性、接口使用及底层实现原理。重点阐述了 deque 作为 stack 和 queue 默认底层容器的原因，以及 vector 在优先队列中的应用。通过模拟实现展示了模板参数灵活性、接口统一性及代码复用等设计关键点，帮助读者掌握仿函数、堆算法及泛型编程在数据结构中的应用。
深入解析 C++ STL 中的容器适配器，涵盖栈（stack）、队列（queue）及优先队列（priority_queue）。介绍了它们的数据结构特性、接口使用及底层实现原理。重点阐述了 deque 作为 stack 和 queue 默认底层容器的原因，以及 vector 在优先队列中的应用。通过模拟实现展示了模板参数灵活性、接口统一性及代码复用等设计关键点，帮助读者掌握仿函数、堆算法及泛型编程在数据结构中的应用。
栈（stack）是一种后进先出（LIFO）的数据结构，它允许在一端进行插入和删除操作。在 C++ STL 中，stack 是一个容器适配器，提供了一组特定的成员函数来访问其元素。
| 函数 | 接口说明 |
|---|---|
| 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();
}
};
以下是使用容器适配器模式实现的 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;
};
}
队列是一种先进先出（FIFO）的数据结构，元素从队尾入队列，从队头出队列。在 C++ STL 中，queue 是一个容器适配器。
queue 的特点：
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空 |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素 val 入队列 |
| pop() | 将队头元素出队列 |
使用容器适配器模式实现的 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;
};
}
优先队列是一种容器适配器，它的第一个元素总是它所包含的元素中最大的（默认大堆）。
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
}
注意：
greater<T>> 或 < 的重载以下是完整的优先队列模拟实现，包含大堆和小堆支持：
#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;
parent = (child - ) / ;
(child > ) {
((_con[parent], _con[child])) {
std::(_con[child], _con[parent]);
child = parent;
parent = (child - ) / ;
} {
;
}
}
}
{
child = parent * + ;
Compare com;
(child < _con.()) {
(child + < _con.() && (_con[child], _con[child + ])) {
++child;
}
((_con[parent], _con[child])) {
std::(_con[child], _con[parent]);
parent = child;
child = parent * + ;
} {
;
}
}
}
{
_con.(x);
(_con.() - );
}
{
std::(_con[], _con[_con.() - ]);
_con.();
();
}
{
_con[];
}
{
_con.();
}
{
_con.();
}
:
Container _con;
};
}
适配器是一种设计模式，将一个类的接口转换成客户希望的另外一个接口。
stack 和 queue 在 STL 中称为容器适配器，它们只是对其他容器的接口进行了包装。STL 中 stack 和 queue 默认使用 deque 作为底层容器。
deque（双端队列）是一种双开口的"连续"空间的数据结构：
deqe 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际类似于一个动态的二维数组。
从上面的模拟实现可以看出容器适配器的核心设计思想：
栈、队列和优先队列是三种基础且重要的数据结构，在 C++ STL 中通过容器适配器的方式实现。理解它们的底层原理、使用场景和实现方式，对于提高编程能力和解决实际问题都有重要意义。
通过模拟实现这些数据结构，我们可以：
在实际开发中，根据具体需求选择合适的数据结构：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online