1、priority_queue

1.1 priority_queue的介紹和使用

priority_queue文檔介紹

翻譯：
1. 優先隊列是一種容器適配器 ，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。
2. 此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優先隊列中位于頂部的元素)。
3. 優先隊列被實現為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優先隊列的頂部。
4. 底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問，并支持以下操作：
empty()：檢測容器是否為空
size()：返回容器中有效元素個數
front()：返回容器中第一個元素的引用
push_back()：在容器尾部插入元素
pop_back()：刪除容器尾部元素
5. 標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用 vector。
6. 需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數make_heap、push_heap和pop_heap來自動完成此操作。

1.2 priority_queue的使用

優先級隊列默認使用vector作為其底層存儲數據的容器，在vector上又使用了堆算法將vector中元素構造成堆的結構，因此 priority_queue就是堆加粗樣式， 所有需要用到堆的位置，都可以考慮使用priority_queue。注意： 默認情況下priority_queue是大堆。

函數聲明	接口說明
priority_queue()/priority_queue(first,last)	構造一個空的優先級隊列
empty( )	檢測優先級隊列是否為空，是返回true，否則返回false
top( )	返回優先級隊列中最大(最小元素)，即堆頂元素
push()	在優先級隊列中插入元素x
pop()	刪除優先級隊列中最大(最小)元素，即堆頂元素

注意：
1、默認情況下，priority_queue是大堆。

#include <vector>
#include <queue>
#include <functional> // greater算法的頭文件int main()
{// 默認情況下，創建的是大堆，其底層按照小于號比較vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1;for (auto& e : v) q1.push(e);while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;// 如果要創建小堆，將第三個模板參數換成greater比較方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());while (!q2.empty()){cout << q2.top() << " ";q2.pop();}cout << endl;return 0;
}

2、如果在priority_queue中放自定義類型的數據，用戶需要在自定義類型中提供 > 或者 < 的重載。

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};void TestPriorityQueue()
{// 大堆，需要用戶在自定義類型中提供<的重載priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要創建小堆，需要用戶提供>的重載priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;
}int main()
{TestPriorityQueue();return 0;
}

模擬實現：

我們剛已經了解到，priority_queue就是堆，并且默認是大堆，底層容器封裝的是vector，因此我們模擬實現priority_queue也是比較簡單的。

#include<vector>
#include<functional>
using namespace std;namespace lcx
{// 仿函數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 = Greater<T>>class priority_queue{public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjust_down(i);}}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T& top() const{return _con[0];}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}private:void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])if(comp(_con[child], _con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else break;}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size()//      && _con[child + 1] > _con[child])if(child + 1 < _con.size()&& comp(_con[child + 1], _con[child])){child++;}//if (_con[child] > _con[parent])if (comp(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else break;}}private:Container _con;Compare comp;};
};

這里如果還有對堆不熟悉的同學我們可以看看我的另外一篇文章，專門講解堆的：C語言實現堆詳細版本

2、容器適配器

2.1 什么是適配器

適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。

2.2 STL標準庫中stack和queue的底層結構

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器， 這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque，比如：

3、deque

3.1 deque的原理介紹

deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

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

雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜，如下圖所示：

那deque是如何借助其迭代器維護其假想連續的結構呢？

3.2 deque的缺陷

與vector比較，deque的優勢是：頭部插入和刪除時，**不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，**因此其效率是必vector高的。
與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。
deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下。
而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。

4、為什么選擇deque作為stack和queue的底層默認容器

stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；
queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：
1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。
結合了deque的優點，而完美的避開了其缺陷。