深入理解C++中的stack、queue和priority_queue
目录
前言
1. stack（栈）
1.1 基本概念
1.2 常用接口
1.3 应用示例：最小栈
1.4 模拟实现
2. queue（队列）
2.1 基本概念
2.2 常用接口
2.3 模拟实现
3. priority_queue（优先队列）
3.1 基本概念
3.2 常用接口
3.3 自定义比较方式
3.4 自定义类型使用
4. 容器适配器
4.1 什么是适配器
4.2 为什么选择deque作为默认底层容器
5. 实际应用
5.1 栈的应用
5.2 队列的应用
5.3 优先队列的应用
总结
前言
在C++标准模板库(STL)中，stack、queue和priority_queue是三种非常重要的容器适配器。它们建立在其他基础容器之上，提供了特定的数据访问方式。本文将详细介绍这三种容器适配器的特性、使用方法和底层实现原理。
1. stack（栈）
1.1 基本概念
stack是一种后进先出(LIFO)的数据结构，只允许在容器的一端进行插入和删除操作。它作为容器适配器实现，底层可以使用vector、deque或list等容器。
#include <stack>
std::stack<int> s; // 默认使用deque作为底层容器1.2 常用接口
- `push()`: 压栈
- `pop()`: 出栈
- `top()`: 访问栈顶元素
- `empty()`: 判断是否为空
- `size()`: 返回元素个数
1.3 应用示例：最小栈
class MinStack {
public:void push(int x) {_elem.push(x);if(_min.empty() || x <= _min.top())_min.push(x);}void pop() {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;
};
1.4 模拟实现
template<class T, class Con = std::deque<T>>
class stack {
public:void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }size_t size() const { return _c.size(); }bool empty() const { return _c.empty(); }
private:Con _c;
};
2. queue（队列）
2.1 基本概念
queue是一种先进先出(FIFO)的数据结构，允许在一端插入元素，在另一端删除元素。它同样作为容器适配器实现，底层可以使用deque或list。
#include <queue>
std::queue<int> q; // 默认使用deque作为底层容器
2.2 常用接口
- `push()`: 入队
- `pop()`: 出队
- `front()`: 访问队头元素
- `back()`: 访问队尾元素
- `empty()`: 判断是否为空
- `size()`: 返回元素个数
2.3 模拟实现
template<class T, class Con = std::deque<T>>
class queue {
public:
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& front() { return _c.front(); }
T& back() { return _c.back(); }
size_t size() const { return _c.size(); }
bool empty() const { return _c.empty(); }
private:
Con _c;
};
3. priority_queue（优先队列）
3.1 基本概念
priority_queue是一种特殊的队列，它的第一个元素总是最大的（默认大顶堆）。底层通常使用vector实现，并通过堆算法维护结构。
#include <queue>
std::priority_queue<int> pq; // 默认大顶堆
3.2 常用接口
- `push()`: 插入元素
- `pop()`: 删除堆顶元素
- `top()`: 访问堆顶元素
- `empty()`: 判断是否为空
- `size()`: 返回元素个数
3.3 自定义比较方式
// 小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
3.4 自定义类型使用
class Date {
public:// ... 构造函数等 ...bool operator<(const Date& d) const { /* 比较逻辑 */ }bool operator>(const Date& d) const { /* 比较逻辑 */ }
};// 使用
std::priority_queue<Date> pq; // 大顶堆
std::priority_queue<Date, std::vector<Date>, std::greater<Date>> min_pq;
4. 容器适配器
4.1 什么是适配器
适配器是一种设计模式，它将一个类的接口转换成客户希望的另一个接口。STL中的stack、queue和priority_queue都是容器适配器，它们基于其他容器（如deque、vector）实现特定功能。
4.2 为什么选择deque作为默认底层容器
1. stack和queue不需要遍历，只需要在固定端操作
2. deque在元素增长时比vector高效（不需要搬移大量数据）
3. 相比list，deque空间利用率更高
5. 实际应用
5.1 栈的应用
- 逆波兰表达式求值
- 括号匹配
- 函数调用栈
5.2 队列的应用
- 广度优先搜索(BFS)
- 任务调度
- 消息队列
5.3 优先队列的应用
- 任务优先级调度
- Dijkstra算法
- 哈夫曼编码
总结
stack、queue和priority_queue是C++ STL中三种重要的容器适配器，它们基于其他容器实现，提供了特定的数据访问方式。理解它们的特性和底层实现原理，对于编写高效、清晰的代码非常重要。在实际开发中，根据具体需求选择合适的容器，可以大大提高程序的性能和可维护性。