文章目錄
- 一、stack和queue
- 1. 概述
- 2. 使用
- 3. 模擬實現
- 二、deque
- 三、priority_queue
- 1. 概述和使用
- 2. 模擬實現
- 四、仿函數
一、stack和queue
1. 概述
我們之前學習的vector和list，以及下面要認識的deque，都屬于STL的容器（containers）組件。而stack和queue，屬于STL的配置器（或稱為配接器）（adapters）組件，或者歸類為容器配置器（container adapters），它們可以修飾容器的接口而呈現出全新的容器性質，即stack的“先進后出”和queue的“先進先出”特點。
2. 使用
stack的所有元素的進出都必須符合“先進后出”的條件，queue的所有元素的進出都必須符合“先進先出”的條件。換句話說，只有stack的棧頂元素和queue的隊頭元素才有機會被移除，因此stack和queue不提供遍歷的功能，也不提供迭代器。
除此之外，stack和queue的功能和使用也都很好理解了，之前我們已經學過棧和隊列。
- stack：
| 函數聲明 | 接口說明 |
|---|---|
| stack() | 構造空的棧 |
| empty() | 檢測棧是否為空 |
| size() | 返回棧中元素個數 |
| top() | 返回棧頂元素的引用 |
| push() | 在棧頂入棧 |
| pop() | 將棧頂元素出棧 |
使用演示：
- queue：
| 函數聲明 | 接口說明 |
|---|---|
| queue() | 構造空的隊列 |
| empty() | 檢測隊列是否為空 |
| size() | 返回隊列中元素個數 |
| front() | 返回隊頭元素的引用 |
| back() | 返回隊尾元素的引用 |
| push() | 在隊尾入隊列 |
| pop() | 將隊頭元素出隊列 |
使用演示：
3. 模擬實現
STL庫中的stack和queue的模板實際上有兩個模板類型：
第一個就是要存儲的數據類型了。第二個代表它們所修飾的容器類型，前面說過，它們不是獨立的容器，而是容器配置器，要依靠別的容器才能實現它們，這就是第二個模板參數的意義。我們可以用vector或list來實現出stack和queue，如stack<int, vector<int>>或queue<char, list<char>>，我們在上層使用stack和queue時是感受不到vector或list的區別的。不論是哪種容器，都有push、pop、front、back、empty等相關操作，得以再封裝成stack和queue的功能。
模板參數也是可以有缺省值的，我們能看到STL標準庫中的stack和queue的Container模板類型默認給了deque，deque也是一種容器，我們一會再介紹它。
除了這一點，stack和queue的模擬實現就很簡單了，遵循它們的特性就好：
namespace lydly
{template<class T, class Container = deque<T>>class queue{private:Container _con;public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}};template<class T, class Container = deque<T>>class stack{private:Container _con;public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}};
}
二、deque
關于deque，簡單了解就好。
對比一下vector和list的優缺點：
| 容器 | 優點 | 缺點 |
|---|---|---|
| vector | 支持下標隨機訪問、CPU高速緩存命中率高 | 頭部或中部插入刪除數據效率低、擴容有一定成本，存在一定浪費 |
| list | 任意位置插入刪除數據效率高、不用擴容，按需申請空間，不存在浪費 | 不支持下標隨機訪問、CPU高速緩存命中率低 |
可見，vector和queue都有各自的優缺點，deque包含了兩種容器的優點，是一種雙向開口的線性連續空間
deque有一個中控器，存放著指向不同節點的指針，每一個節點是一個緩沖區buffer，是一個數組用于存放數據。執行尾插時，就在當前buffer的尾部插入數據，若當前buffer已滿，就去中控器的下一個節點指向的buffer的第一個位置存放；執行頭插時，要倒著看，當前buffer頭部沒有空間，就去中控器的上一個節點指向的buffer的最后一個位置存放，再頭插一次就存放到倒數第二個位置，以此類推。頭刪和尾刪也是一樣的道理。
deque并不是真正完全連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似一個動態的二維數組，deque的迭代器的結構就更為復雜了。
所以，deque與vector相比，頭部插入效率更高，不需要挪動元素；與list相比，空間利用率更高。但是，deque不適合遍歷，因為在遍歷時迭代器需要頻繁檢測每一個buffer是否到達邊界，導致效率低下。而在序列式場景中，可能經常需要遍歷，所以實際需要線性數據結構時，大多數情況下優先考慮vector和list，deque的應用并不多，目前能看到的一個應用就是STL用它作為stack和queue的底層數據結構。
而STL選擇deque作為stack和queue的底層，主要原因也是stack和queue不需要遍歷，只在固定的一端或兩端進行操作，以及deque結合vector和list的優點了。
三、priority_queue
1. 概述和使用
priority_queue，意為優先級隊列，是queue的一種，帶有權值觀念，其內的元素并非按照入隊列的順序排列，而是按照元素的權值排列，默認權值較高的元素排在前面。
舉個栗子：
有沒有發現，優先級隊列其實就是我們之前學過的堆。
優先級隊列默認使用vector作為其底層存儲數據的容器，在vector上又使用了堆算法將vector中元素構造成堆的結構，因此priority_queue就是堆，所有需要用到堆的場景，都可以考慮使用優先級隊列。默認情況下，優先級隊列是大堆。
| 函數聲明 | 接口說明 |
|---|---|
| priority_queue() | 構造空的優先級隊列 |
| empty() | 檢測優先級隊列是否為空 |
| size() | 返回優先級隊列中元素個數 |
| top() | 返回優先級隊列中的最大（最小）元素，即堆頂元素 |
| push() | 在優先級隊列中插入元素 |
| pop() | 刪除優先級隊列中的最大（最小）元素，即堆頂元素 |
2. 模擬實現
既然優先級隊列就是堆，那么實現優先級隊列也就和實現堆道理類似了：
傳送門：https://blog.csdn.net/2402_86681376/article/details/145808942?spm=1011.2415.3001.5331（堆的講解
要用到的向上調整算法、向下調整算法，我們都學習過了。
namespace lydly
{template<class T, class Container = vector<T>>class priority_queue{private:Container _con;public:priority_queue(){}void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:void adjustup(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}};
}
問題來了，我們想讓優先級隊列降序排列元素，再重載一次·未必太麻煩了，怎么辦呢？這里就需要用到仿函數。
四、仿函數
在STL標準庫中，我們看到優先級隊列的模板參數中還有一個Compare，這個就是仿函數。
仿函數是一種類對象，顧名思義，它可以“模仿函數”，允許用戶“以模板參數來指定所要采取的策略”。在priority_queue中，它的第三個模板類型參數就是仿函數，默認給了一個less，less其實是這樣的：
template<class T>
class less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
less是一個類，less<typename Container::value_type>就是一個匿名對象，它的里面重載了()，這樣一來，倘若有less<T> Com;那我們就可以寫出Com(a, b)，（a，b是T類型的）這個表達式的意思就是a < b！
舉一反三，STL中還有greater的仿函數：
template<class T>
class greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};
倘若有greater<T> Com;那我們就可以寫出Com(a, b)，這個表達式的意思就是a > b！
大堆和小堆的區別在于AdjustUp和AdjustDown中幾處<或>的不同，有了上面的兩種仿函數，我們就能在創建優先級隊列時根據需要，模板參數傳less或greater，區分大堆和小堆。具體是<還是>，就可以依靠傳的是less還是greater來分別。STL的仿函數中的less和greater，就可以傳給priority_queue的模板：
我們的模擬實現也按照這個思路來完成：
namespace lydly
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{private:Container _con;public:priority_queue(){}void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:void adjustup(int child){//構造一個less或greater的對象Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);// child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){//構造一個less或greater的對象Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}};
}
關于less，我們還可能會遇到其他情況：
- 當想要比較的是自定義類型時，就需要這個自定義類型中重載<和>運算符，這一點很好理解。
- 當傳入指針時，一般我們應該是想要比較的是指向的內容，但如果只把less寫成剛才那樣，會被解析成直接比較兩個地址的值。這時，需要寫成這樣：
template<class T>
class less<T*>
{
public:bool operator()(const T* const & x, const T* const & y){return *x < *y;}
};
![[C++] 一個線程打印奇數一個線程打印偶數](http://pic.xiahunao.cn/[C++] 一個線程打印奇數一個線程打印偶數)
