目录

前言

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中三种重要的容器适配器，它们基于其他容器实现，提供了特定的数据访问方式。理解它们的特性和底层实现原理，对于编写高效、清晰的代码非常重要。在实际开发中，根据具体需求选择合适的容器，可以大大提高程序的性能和可维护性。