目錄

前言

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中三種重要的容器適配器，它們基于其他容器實現，提供了特定的數據訪問方式。理解它們的特性和底層實現原理，對于編寫高效、清晰的代碼非常重要。在實際開發中，根據具體需求選擇合適的容器，可以大大提高程序的性能和可維護性。