???????棧（Stack）、隊列（Queue）是C++ STL中的經典容器適配器
容器適配器特性
- 不是獨立容器，依賴底層容器（deque/vector/list）
- 通過限制基礎容器接口實現特定訪問模式
- 不支持迭代器操作（無法遍歷元素）
- 時間復雜度：
- 棧/隊列操作均為O(1)
- 底層容器影響性能：
- vector實現棧可能導致擴容拷貝
- list實現隊列保證穩定性能
典型應用場景：
- 棧：函數調用棧、括號匹配、表達式求值
- 隊列：消息隊列、BFS算法、緩沖機制
（棧和隊列前面C語言寫過，這里直接貼C++代碼）
雙端隊列：
?（不常用，簡單介紹和理解）
STL標準庫里面默認適配器使用的是deque這個容器，
? ? deque（雙端隊列）是C++標準庫中的順序容器，全稱"double-ended queue"，支持在頭尾兩端高效插入/刪除元素。
?????????
- 分段連續存儲：由多個固定大小的存儲塊（稱為緩沖區buffer）構成
- 中控器結構：使用指針數組（map）管理存儲塊的地址
優勢：
- 任意位置（頭尾插入）插入刪除
- 可以隨機訪問
缺陷：
- operator[]，計算稍顯復雜，大量使用，性能下降。
- 中間插入刪除效率不高
- 底層角度選代器會很復雜
cur 表示當前數據
first 和 last 表示 buffer 的開始和結束
node 反向指向中控位置，方便遍歷時找下一個buffer
棧：
template<class T,class Container=deque<T>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop();T& top(){return _con.back();}bool empty()const{return _con.empty();}size_t size(){return _con.size();}private:Container _con;};template<class T, class Container>
inline void stack<T, Container>::pop()
{_con.pop_back();
}
隊列：
template<class T, class Container = deque<T>>
class queue
{
public:void push(const T& x);void pop(){_con.pop_front();}T& back(){return _con.back();}T& front(){return _con.front();}bool empty()const{return _con.empty();}size_t size(){return _con.size();}private:Container _con;};template<class T, class Container>
inline void queue<T, Container>::push(const T& x)
{_con.push_back(x);
}仿函數：
????????仿函數（Functor），也稱為函數對象，是通過重載operator()運算符使得類對象可以像函數一樣被調用的技術。它常用于STL算法中，提供靈活且可定制的操作邏輯。
? ? ? ? 仿函數設計出來是用來替代函數指針的。
template<class T>
struct greater
{bool operator()(const T& l, const T& r) const {return l > r;}
};template<class T>
struct less
{bool operator()(const T& l, const T& r) const {return l < r;}
};
????????
優先級隊列（priority_queue）：
????????優先級隊列（priority_queue）是C++標準庫中的容器適配器，它基于堆數據結構實現，能夠保證隊列頭部始終是最大（默認）或最小值的元素。
? ? ? ? 底層的數據結構實際為堆（Heap）。
#include <queue>
priority_queue<int> pq; // 默認大頂堆
priority_queue<int, vector<int>, greater<int>> min_pq; // 小頂堆PS：
- Compare 進行比較的仿函數????????less->大堆
- Compare 進行比較的仿函數? ? ? ? greater->小堆
//compare進行比較的仿函數 less->大堆
template<class T, class Container = vector<T>, class Compare=std::less<T>>
class priority_queue
{
public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first!=last){_con.push_back(*first);++first;}//建堆for (int i = (_con.size()-1-1)/2;i>=0;--i){adjust_down(i);}}void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent] ,_con[child])) { //默認less 向上調整建大堆std::swap(_con[child] , _con[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()) {//選出左右孩子大的那一個 默認less 向下調整建小堆if (child + 1 < _con.size() && com(_con[child],_con[child+1])) {++child;}if (com(_con[parent], _con[child])) {std::swap(_con[child] , _con[parent]);parent = child; child = parent * 2 + 1;}else {break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T &top()const{return _con[0];}private:Container _con;
};
? ? ? ? 代碼幾乎都是前面寫過的，關鍵是C++讓其封裝起來了。
代碼還是有幾個要注意的點：
????????STL庫里面priority用greater(大于) 比較建立小堆，less(小于)比較建立小堆。所以這里要跟標準庫里面保持一致，所以要注意比較時，代碼的順序。
? ? ? ? 而這里影響位置順序的地方在向上調整和向下調整的函數上。
void adjust_up(size_t child)
{Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent] ,_con[child])) { std::swap(_con[child] , _con[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void adjust_down(size_t parent)
{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])) {std::swap(_con[child] , _con[parent]);parent = child; child = parent * 2 + 1;}else {break;}}
}構建堆的復雜度差異：
- 自底向上建堆：時間復雜度為 O(n)，因為大多數節點位于低層。
- 自頂向下建堆：時間復雜度為 O(n log n)，因為每個元素插入時都可能需要 O(log n) 調整。
所以這里使用自底向上建堆。
_con[parent] > _con[child]
等價于
_con[child] < _con[parent] _con[parent] < _con[child]
等價于
_con[child] > _con[parent] ? ? ? ? 這里寫法順序的不同，會導致代碼的意思不同。這里要跟庫里面最好保持一直。庫里面是greater(大于)建立小堆，所以這里 > 保持不變的情況下，_con[parent] 要放在左邊，?_con[child]?要放在右邊?(自頂向下建堆)?。
? ? ? ? 根據代碼的意思就可以知道，如果?_con[parent] >?_con[child]，則交換父子節點的數據，那么一直到根節點，數據變成了上面下，下面大的結構，就建成了小堆。同理 如果是 ?_con[child] > _con[parent]，則變成了數據上面大，下面小的結構，會建成大堆。
