前言

在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;