目录
C++ 容器适配器详解：stack、queue 与 priority_queue
3.3 自定义类型在 priority_queue 中的使用
C++ 容器适配器详解：stack、queue 与 priority_queue
引言
在 C++ 标准模板库(STL)中，容器适配器是一类特殊的容器，它们基于现有的容器类进行封装，提供特定的接口来满足不同的数据结构需求。本文将深入探讨三种主要的容器适配器：stack（栈）、queue（队列）和 priority_queue（优先队列），包括它们的使用方法、实现原理以及底层容器选择。
1. stack（栈）
1.1 stack 简介
栈是一种后进先出(LIFO)的数据结构，只允许在容器的一端进行插入和删除操作。在 C++ 中，std::stack 是一个容器适配器，它基于其他容器（如 deque 或 vector）实现。
#include <stack>
#include <vector>
std::stack<int> s1; // 默认使用 deque 作为底层容器
std::stack<int, std::vector<int>> s2; // 使用 vector 作为底层容器1.2 stack 的基本操作
push(): 将元素压入栈顶pop(): 弹出栈顶元素top(): 访问栈顶元素empty(): 检查栈是否为空size(): 返回栈中元素数量
1.3 有关栈的几个oj题（原题查力扣or牛客）
栈的弹出压入序列验证
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
if(pushV.size() != popV.size())
return false;
int outIdx = 0;
int inIdx = 0;
stack<int> s;
while(outIdx < popV.size()) {
while(s.empty() || s.top() != popV[outIdx]) {
if(inIdx < pushV.size())
s.push(pushV[inIdx++]);
else
return false;
}
s.pop();
outIdx++;
}
return true;
}逆波兰表达式求值
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (const auto& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
if (token == "+") s.push(a + b);
else if (token == "-") s.push(a - b);
else if (token == "*") s.push(a * b);
else s.push(a / b);
} else {
s.push(stoi(token));
}
}
return s.top();
}1.4 stack 的模拟实现
#include <vector>
namespace bite {
template<class T, class Container = std::vector<T>>
class stack {
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_back(); }
T& top() { return _c.back(); }
const T& top() const { return _c.back(); }
size_t size() const { return _c.size(); }
bool empty() const { return _c.empty(); }
private:
Container _c;
};
}2. queue（队列）
2.1 queue 简介
队列是一种先进先出(FIFO)的数据结构，元素从一端（队尾）插入，从另一端（队头）删除。std::queue 也是一个容器适配器。
#include <queue>
std::queue<int> q1; // 默认使用 deque 作为底层容器
std::queue<int, std::list<int>> q2; // 使用 list 作为底层容器2.2 queue 的基本操作
push(): 在队尾插入元素pop(): 删除队头元素front(): 访问队头元素back(): 访问队尾元素empty(): 检查队列是否为空size(): 返回队列中元素数量
2.3 queue 的模拟实现
由于 queue 需要支持头删和尾插，使用 vector 效率较低，通常使用 list 实现：
#include <list>
namespace bite {
template<class T, class Container = std::list<T>>
class queue {
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& front() { return _c.front(); }
const T& front() const { return _c.front(); }
T& back() { return _c.back(); }
const T& back() const { return _c.back(); }
size_t size() const { return _c.size(); }
bool empty() const { return _c.empty(); }
private:
Container _c;
};
}3. priority_queue（优先队列）
3.1 priority_queue 简介
优先队列是一种特殊的队列，其中元素按优先级排序，第一个元素总是优先级最高的（默认是大顶堆）。
#include <queue>
std::priority_queue<int> pq1; // 默认大顶堆，使用 vector 作为底层容器
std::priority_queue<int, std::vector<int>, std::greater<int>> pq2; // 小顶堆3.2 priority_queue 的基本操作
push(): 插入元素pop(): 删除顶部元素top(): 访问顶部元素empty(): 检查是否为空size(): 返回元素数量
3.3 自定义类型在 priority_queue 中的使用
class Date {
public:
Date(int year, int month, int day)
: _year(year), _month(month), _day(day) {}
bool operator<(const Date& d) const {
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d) const {
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d) {
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueue() {
// 大堆，需要用户在自定义类型中提供<的重载
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout << q1.top() << endl;
// 小堆，需要用户提供>的重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout << q2.top() << endl;
}3.4 priority_queue 的模拟实现
#include <vector>
#include <algorithm>
namespace bite {
template<class T, class Container = std::vector<T>, class Compare = std::less<T>>
class priority_queue {
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _c(first, last) {
std::make_heap(_c.begin(), _c.end(), _comp);
}
void push(const T& x) {
_c.push_back(x);
std::push_heap(_c.begin(), _c.end(), _comp);
}
void pop() {
std::pop_heap(_c.begin(), _c.end(), _comp);
_c.pop_back();
}
T& top() { return _c.front(); }
const T& top() const { return _c.front(); }
size_t size() const { return _c.size(); }
bool empty() const { return _c.empty(); }
private:
Container _c;
Compare _comp;
};
}4. 容器适配器与底层容器
4.1 什么是容器适配器
容器适配器是一种设计模式，它将一个类的接口转换成客户希望的另外一个接口。STL 中的 stack、queue 和 priority_queue 都是容器适配器，它们基于其他容器实现特定的数据结构行为。
4.2 为什么选择 deque 作为默认底层容器
STL 选择 deque 作为 stack 和 queue 的默认底层容器，主要基于以下考虑：
stack 的需求：
- 需要支持
push_back()和pop_back() - vector 和 list 都可以满足
- deque 在元素增长时比 vector 效率更高（不需要搬移大量数据）
- 需要支持
queue 的需求：
- 需要支持
push_back()和pop_front() - list 可以满足
- deque 不仅效率高，而且内存使用率更高
- 需要支持
共同优势：
- stack 和 queue 都不需要遍历（因此没有迭代器）
- deque 完美避开了其遍历效率低的缺陷
4.3 deque 的简单介绍
deque（双端队列）是一种双开口的"连续"空间数据结构：
优点：
- 头尾插入和删除操作时间复杂度为 O(1)
- 与 vector 比较，头插效率高，不需要搬移元素
- 与 list 比较，空间利用率比较高
缺点：
- 不适合遍历，迭代器需要频繁检测小空间边界
- 中间插入删除效率较低
deque 的底层结构由一段段连续的小空间拼接而成，类似于动态的二维数组：
5. 总结
stack：
- LIFO 数据结构
- 基于 deque 或 vector 实现
- 适用于需要后进先出的场景，如函数调用栈、括号匹配等
queue：
- FIFO 数据结构
- 基于 deque 或 list 实现
- 适用于需要先进先出的场景，如任务调度、消息队列等
priority_queue：
- 优先级队列，默认大顶堆
- 基于 vector 实现
- 适用于需要按优先级处理的场景，如任务调度、Dijkstra 算法等
容器适配器选择：
- 根据操作需求选择底层容器
- 默认情况下，STL 做出了最优选择
- 特殊需求时可以自定义底层容器
通过合理使用这些容器适配器，可以大大提高 C++ 程序的开发效率和运行性能。理解它们的底层实现原理，有助于我们在实际开发中做出更合理的选择和优化。