📝前言：
這篇文章我們來講講STL中的stack和queue。因為前面我們已經有了string、vector和list的學習基礎，所以這篇文章主要關注一些stack和queue的細節問題，以及了解一下deque（縫合怪）和priority_queue ，并且模擬實現priority_queue。

🎬個人簡介：努力學習ing
📋個人專欄：C++學習筆記
🎀CSDN主頁 愚潤求學
🌄其他專欄：C語言入門基礎，python入門基礎，python刷題專欄

---

一，Stack && queue

1. stack和queue其實是container adaptor（容器適配器）
   
   在STL里面他們是用deque來適配的。也就是通過deque來封裝，內部實際上用的是deque的接口。

2. stack.top()返回的是棧頂元素的引用，queue.front()一樣

3. stack.pop()并不會返回值，而是直接pop掉棧頂元素，queue.pop()一樣

除了deque能做適配器以外，其他的容器也都可以，比如vector和list

1. 用vector 適配 Stack

對于Stack而言，要實現的是同一邊刪除與插入的操作，而vector里面正好有pop_back和push_back 這樣的接口。

#include<vector>namespace tr
{template<typename T>class stack{public:stack(){}void push(const T& x) { _a.push_back(x); }void pop() { _a.pop_back(); }const T& top() const { return _a.back(); }T& top() { return _a.back(); }size_t size() { return _a.size(); }bool empty() { return _a.empty(); }private:std::vector<T> _a; // 棧的底層用數組};
}

測試代碼：

#include<iostream>
#include<vector>
#include"Stack.h" using namespace std;void test_Stack() {tr::stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout << st.top() << endl;st.pop();}cout << st.empty() << st.size() << endl;
}int main() {test_Stack();return 0;
}

注意頭文件和using namespace std;的位置問題：頭文件展開時會向上找標識符，比如“Stack.h”用了一個cout，但是using namespace std;在下面，向上找不到就會報錯編譯錯誤：“未定義標識符”

---

2. 用list模擬實現queue

list要滿足的要求是一邊插入一邊刪除，由于vector沒有頭刪，所以這時候選擇list是更好的

模擬實現：

#pragma once
#include<list>namespace tr
{template<typename T>class queue{public:queue() {}void push(const T& x) { _a.push_back(x); }const T& front() const { return _a.front(); }T& front() { return _a.front(); }void pop() { _a.pop_front(); } // 頭刪size_t size() { return _a.size(); }bool empty() { return _a.empty(); }private:std::list<T> _a;};}

測試代碼：

#include<iostream>
#include"Queue.h" using namespace std;void test_Queue() {tr::queue<int> ls;ls.push(1);ls.push(2);ls.push(3);ls.push(4);ls.push(5);while (!ls.empty()){cout << ls.front() << endl;ls.pop();}cout << "empty: " << ls.empty() << endl << "size: " << ls.size() << endl;
}int main() {test_Queue();return 0;
}

運行結果：

---

3. 簡單認識deque

deque是雙端隊列，即兩邊都可以插入和刪除

deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個
動態的二維數組，其底層結構如下圖所示：

map中控是一個指針數組，每個指針指向一個數組（每個數組大小一樣），這些數組才是存儲數據真正的地方。
迭代器由四個部分組成：

• 給定一個“下標” x 找到容器中對應的數據：先 x / n：找到對應的數組編號，再 x % n 找到在組內的位置
• 判斷是否到達一個數組的尾部：cur == last

deque 和 vector 以及 list 的比較：

1. 頭插尾插效率更高
2. 下標隨機訪問比vector差一點
3. 中間插入數據效率低，因為要移動數據

由因為：

1. stack和queue沒有迭代器，不需要訪問
2. 實現stack時：deque的擴容效率比vector高
3. 實現queue時：一次性申請一塊數組，在queue元素個數增長時，不需要想list一樣一個個申請，效率更高，且內存利用率更高

所以，stack和queue用了deque做適配器。

---

二，priority_queue

1. 認識優先級隊列

priority_queue：優先隊列，也在頭文件< queue > 里面
意思是：在使用top()和pop()的時候會取優先級高的，默認是大的元素優先級高。（簡單來說就是降序）
底層實現時堆，而堆的底層是數組。

簡單使用一下：

int main() {priority_queue<int> pq;pq.push(3);pq.push(2);pq.push(6);pq.push(1);pq.push(8);while (!pq.empty()){cout << pq.top();pq.pop();}return 0;
}

運行結果：

---

2. 仿函數

仿函數是一個類，但是可以像調用函數一樣去調用這個類，作為回調函數使用。通過重載()來實現

仿函數使用示例：

class Adder {
public:// 重載 () 運算符int operator()(int a, int b) const {return a + b;}
};int main() {Adder adder;// 像調用函數一樣調用仿函數對象int result = adder(3, 4); // 或者用匿名對象：Adder()(3, 4) Adder()——創建匿名對象，(3 ,4)調用重載的()std::cout << "Result: " << result << std::endl;return 0;
}

---

3. 模擬實現priority_queue

priority_queue頭文件：

#pragma once
#include<iostream>
#include<vector>
using namespace std;template<class T>
class Less
{
public:bool operator()(const T& a, const T& b){return a < b;}
};template<class T>
class Greater
{
public:bool operator()(const T& a, const T& b){return a > b;}
};namespace tr
{template<class T, class Container = vector<T>, class Compare = Less<T>>// Compare 就是比較方法class priority_queue{public:void Adjustup(size_t child){Compare com; // 構造仿函數對象size_t parent = (child - 1) / 2;while (child > 0){if (com(_a[child], _a[parent])) // 用仿函數對象調用仿函數{std::swap(_a[child], _a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}void Adjustdown(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _a.size()){if (child + 1 < _a.size() && com(_a[child + 1], _a[child])){child++;}if (com(_a[child], _a[parent])) // 相當于孩子節點小于父親{std::swap(_a[child], _a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}priority_queue(){}void push(const T& x){_a.push_back(x);Adjustup(_a.size() - 1);}T& top(){return _a[0];}const T& top() const{return _a[0];}void pop(){std::swap(_a[0], _a[_a.size() - 1]);_a.pop_back();Adjustdown(0);}size_t size() { return _a.size(); }bool empty() { return _a.empty(); }private:Container _a;};};

測試代碼：

#include"priority_queue.h"
int main() {tr::priority_queue<int, vector<int>, Greater<int>> pq; // 傳入的不是less，而是Less<int>，類模板傳的是類型，函數模板傳才是參數pq.push(3);pq.push(2);pq.push(6);pq.push(1);pq.push(8);while (!pq.empty()){cout << pq.top();pq.pop();}cout << endl;return 0;
}

運行結果（大根堆，降序）：

補充小知識點：編譯器對模板是按需實例化，首先編譯時：只會檢查模板的大框架，不會檢查類里面函數的內部。第二，當沒有使用到類中的成員函數時，編譯器在實例化的時候就不會實例化這些函數。（所以有的時候可能類的成員函數有問題，只是沒使用到）

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！