stack、queue、priority_queue的模擬實現

使用部分

對于stack和queue的使用其實是非常簡單的。當我們進行文檔的查閱的時候，會發現提供的接口其實并不算多，也沒有迭代器。這是因為棧只能在棧頂操作數據，隊列只能在隊尾隊頭操作數據。不能遍歷數據。

而priority_queue名稱是優先級隊列，看著很陌生，實際上我們早已經接觸過，其實就是我們以前實現的數據結構——堆。

對于它們三個的使用我們就不進行過多的介紹了，因為接口的使用是非常簡單的，且以往我們已經使用和實現過。所以自行查閱文檔使用即可：
queue的使用(包括priority_queue)
stack的使用

模擬實現

本篇文章的重點將放在三者的模擬實現上。這三者的實現和以往的模擬實現是有些不同的。

容器適配器

在以往學習list等容器的時候，我們會發現模板參數里面是有內存池的聲名：

即allocator< T >，這是內存池的聲名。

但是我們仔細翻看stack和queue的時候發現：


我們發現模板參數里面竟然聲明了一個Container類型，且給有缺省值deque< T >。這里就需要說一下，模板參數也是可以給缺省值的。

其實priorty_queue也是一樣的。也是使用這樣的模板聲名方式。

其實也就是說，其實stack和queue其實并不是像我們以前那樣自行開辟數組空間或者實現鏈式隊列一樣。再整出一些順序表來實現這些結構。

棧和隊列的本質就是線性表，只不過是有限制的線性表。只能在表的固定位置進行訪問和修改。而STL庫中已經實現好了vector和list這樣比較復雜的線性表，并且是有提供相關的接口進行操作的。

那也就是說，完全可以將已經實現好的線性表再進行一次封裝，只提供固定位置的修改和訪問操作的接口。那這樣子其實就很方便了，就不用再費時費力去手撕一個棧或隊列的代碼出來。

我們看文檔圖中被方框圈起來的字樣，Container Adaptor其實就是容器適配器的意思，其實就是通過對別的容器進行二次封裝后實現的容器。

只不過說，對于默認的適配容器，這里選擇了deque這個容器。其實很好理解，因為對于棧來說，使用vector最為方便，對于隊列來說，使用list最為方便。(在c語言數據結構部分就已經說過）。但是反過來就不方便了。

基于此，STL庫中實現了一種將vector和list的特性融合的容器，即為deque，我們可以理解為是二者的縫合怪。

deque的介紹

我們先來了解一下deque是什么。

原理

deque本質也是個容器，其內部結構比較復雜：

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

真實結構

這樣一看，那和vector也沒什么太大的區別嘛。就是多了一端進行插入刪除操作。

其實并不是這樣子的。實際上，deque是一段由一段的連續空間(緩沖區)存儲數據，然后這每一段空間的地址會放在一個叫中控數組的地方：

大致是這個樣子。中控數組存儲的是各個緩沖區的地址，各個緩沖區進行存儲數據。

這樣子是結合了vector和list的特點進行構造的數據結構。直到結構后，我們就得明白deque時如何訪問存儲的數據的，這樣子才能明白其對應的操作是如何進行的。

deque的迭代器

實現了list后我們肯定就知道，對于deque這么復雜的結構，使用原生指針肯定是不可能實現迭代器的功能的。肯定是需要對其進行封裝，我們來看看源碼：

迭代器有四個成員變量，有三個是指向緩沖區數據類型的指針，一個是指向緩沖區的指針。

具體的指向是怎么樣的呢？

對于first和last指針，分別指向的是緩沖區的開頭數據位置和末尾數據位置的下一個。我們可以認為是以原生指針形式實現的、每一小段緩沖區的迭代器。而cur指針是用來遍歷數據的，一旦達到了last的位置就需要遍歷到下一段緩沖區了。而node指針是用來找到當前緩沖區所處中控數組的位置的。

緩沖區的指針只需要存儲在這個中控器上，存儲的位置一定是從中間開始存儲一直擴散至兩側。因為需要頭插和尾插，放在中間肯定是更方便的。當中控數組位置不夠時擴容即可。對于中控數組的擴容代價是一點也不大的，只需要將地址復制到新中控器，將原中控器的指向置空再釋放即可。也就是說，使用淺拷貝就可以。

deque的操作

實現好這樣的迭代器之后，只需要通過迭代器來進行容器的一系列操作即可。這個結構我們只需做一些簡單的了解即可。不用去模擬實現。因為這個結構還是有那么一些的缺陷的。

deque容器中會存放兩個迭代器，一個是_start,指向第一個緩沖區，一個是_finish，指向最后一個緩沖區。可能還有有一些別的數據，如緩沖區個數等(即中控器中數據個數)。

尾插操作：就是在_finish這個迭代器的cur指針位置插入后，再將cur指針往后移動。如果當前cur指針和last指針是處于一個位置的時候，就需要移動至下一個緩沖區。也就是將node指針向后移動一個位置。再調整其余指針的位置后再執行上述操作。當然如果中控器位置不夠需要重新擴容。

頭插操作：過程與尾插相反，需要在_start這個迭代器的cur指針位置插入，只不過我們需要注意的是，對于區間的選擇，一般都是傾向于左閉右開，所以尾插的時候cur指針指向的是最后一個數據的下一個位置，而頭插的cur指針指向的是第一個數據。

且尾插是在緩沖區中是從前往后插入。頭插不一樣，是從后往前插入：

隨機訪問操作：deque是支持隨機訪問，也就是說它的迭代器是隨機類型。可以支持運算符[]的重載。想要訪問也是很簡單。比如訪問第25個數據(從第0個開始)，每個緩沖區有10個數據。可以先25 / 10 = 2算出當前是第幾個緩沖區，然后再25 % 10 = 5算出位于緩沖區的位置。然后通過中控器訪問，指向中控器的map是一個二級指針，經過解引用得到內部數據，就是指向緩沖區的一級指針，再經過解引用就可以得到數據，所以此時deque dq[25] = map[25 / 10][25 % 10] 就可以訪問到了，還是很簡單的。

置于其他的使用其實很簡單，只要前面的容器有認真學習和使用過都會用。因為底層都是將接口進行封裝了，我們只需要關心怎么用的。

deque的優缺點

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

還要說的是是中間位置插入的效率，對于deque來說，除了頭部尾部之外的插入其實都很麻煩，這是顯而易見的。所以一旦涉及到大量的中間位置的插入，我們都是可以選擇使用list，因為任意位置的插入是O(1)，且不挪動數據。但是由于其尾插頭插效率極高，甚至更甚vector一籌，所以對于棧和隊列這種只在一側或者兩側大量操作的容器，很明顯用deque是效率更高。

stack的模擬實現

了解完deque后，我們來實現一下stack，我們直接上代碼:

namespace MySpace {template<class T, class Container = deque<T>>class stack {public:stack() {}//一定要寫 會走初始化列表 如果是自定義類型會調用其默認構造函數stack(const initializer_list<T>& x){typename initializer_list<T>::iterator it = x.begin();while (it != x.end()) {push(*it); ++it;}} 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.front();}size_t size() const{return _con.size();}bool empty() const {return _con.empty();}private: Container _con;};}

當然，用initializer_list這個構造函數可以不寫，只寫那個空的即可。我寫只是為了創建對象的時候方便一些，便于大量測試。

那個空的構造函數是一定要寫的。我們來回顧一下：
因為即使是空的構造函數，成員變量也要走初始化列表的操作，對于內置類型，有傳參用傳參的，反之用缺省值，如果再沒有只能給隨機值了。而自定義類型不一樣了，會調用其默認構造函數，沒有就報錯。我們這里的stack是只有一個容器的，這個容器默認是STL 庫里面的deque，肯定是有其默認構造函數的。如果這里是我們自己整的容器那我們也要提供默認構造函數。

而后對于入棧出棧以及判空，獲取棧頂數據，獲取數據個數都是調用的容器內已有的接口。這十分方便。

按需實例化

很多人會好奇，既然是調用的容器的接口，但是對于有些容器來說，有些接口它是沒有的。就比如vector是沒有pop_front接口的。如果我們在類模板里面調用了這個接口，但是顯示實例化類對象的時候傳了vector這個容器怎么辦呢？

這個不用擔心，編譯器會報錯的。模板最大的特點就是按需實例化，如果有些接口我們不進行調用，寫在那里它并不會報錯。如果我們調用了那個接口，如果與當前容器不符，編譯器是能夠與檢查的出來的。

queue的模擬實現

queue的實現其實和stack也是很類似的，稍微修改一下就好：

namespace MySpace {template<class T, class Container = deque<T>>class queue {public:queue() {}queue(const initializer_list<T>& x) {typename initializer_list<T>::iterator it = x.begin(); while (it != x.end()) { push(*it);  ++it; } }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();}size_t size() const {return _con.size();}bool empty() const {return _con.empty();}private:Container _con;};}

這里就是剛剛說到的那種情況，我們調用了pop_front接口，當然deque和list<是有這樣的接口的，所以隊列的是新是不能用vector的，這其實也符合之前的判斷。因為用vector不適合頭刪數據。

priority_queue的模擬實現

priority_queue的模擬實現其實早已經實現過，但是在這里我們得引入一些新的用法。我們先來看看文檔中是怎么定義的：

我們發現，除了適配容器之外，模板參數中還多了一個叫Compare的參數，這個是什么呢？

這個其實是仿函數，其實也是一個類。

為何引入仿函數

還記得以前模擬實現堆這個數據結構的時候，我們可能需要通過手動調整向上調整算法和向下調整算法的的比較邏輯，從而達到是建大堆還是建小堆。

但這很明顯是非常不合理的。總不能每一次都要手動調整吧。但是在學習c語言的時候是沒有太多辦法解決這個問題，除了函數指針。

函數指針用來控制比較邏輯其實我們早已見過，就是使用c庫內自帶的qsort函數時，需要我們自己傳一個比較邏輯，這個比較邏輯按照庫中的要求就是排成升序。但是我們實現和庫要求相反的比較函數，就可以排升序。這些就不再多說，都是以前的知識。

但是c++中是不太喜歡使用函數指針這個東西的，因為函數指針還是比較復雜的，且代碼的可讀性一般。有沒有什么辦法能夠達到這樣的效果：
即我傳入一個類似小于號的東西，就建立大堆，傳入類似大于號的東西，就建立小堆。然后就使用這個傳入的內容去執行比較邏輯，復用這個邏輯建立大堆或者小堆呢？

答案是可以的，標準庫里面就是用仿函數實現的。至于為什么要規定小于號建大堆，大于號建小堆這是不用管的，標準庫中就是這樣玩的。

我們來看看仿函數是怎么寫的：

template<class T>
class less {
public:bool operator()(const T& x1, const T& x2) {return x1 < x2;}
};template<class T>
class greater {
public:bool operator()(const T& x1, const T& x2) {return x1 > x2;}
};

當前我們只需要簡單的了解一下仿函數怎么簡單的實現一個并且會使用即可。

仿函數其實就是一個空的類，沒有成員變量，內部有一個對()進行重載的函數，返回值是bool類型。注意這個空類的大小為1個字節，這是為了占位。這在類的大小部分說過。

這也是個類模板，其實很好理解，因為比較的內容可能不只是整形或者浮點型，各式各樣的都需要比較。STL內的容器也是可以比較的，因為內部都有重載比較邏輯的函數。

如果是我們自己實現的類比較，我們可以在內部自行實現比較邏輯。但是如果我們現在是傳入兩個指針指向兩個對象，那使用類內的比較邏輯可能就不是我們想要的。解決方法就是：要不然就是在內部重載一個專門針對指針的比較邏輯，要不然就是重載一個仿函數即可。

代碼實現

我們來看看代碼實現：

namespace MySpace {template<class T>class less {public:bool operator()(const T& x1, const T& x2) {return x1 < x2;}};template<class T>class greater {public:bool operator()(const T& x1, const T& x2) {return x1 > x2;}};template<class T, class Container = vector<T>, class Compare = less<T>> //默認less代表傳小于號 建大堆 反之相反class priority_queue {public: priority_queue() {}template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {InputIterator it = first;while (it != last) {push(*it);++it;}}template <class T>priority_queue(const initializer_list<T>& x) { typename initializer_list<T>::iterator it = x.begin(); while (it != x.end()) { push(*it);++it;  } }void push(const T& x) {_con.push_back(x);Adjustup(size() - 1);}void pop() {std::swap(_con[0], _con[size() - 1]);_con.pop_back();AdjustDown(0);}bool empty() const {return _con.empty();}size_t size() const {return _con.size();}T& top() const {return _con[0];}void Adjustup(size_t child) {int Child = child, Parent = (child - 1) / 2;while (Child > 0) {if (_cmp(_con[Parent], _con[Child])) {std::swap(_con[Parent], _con[Child]);Child = Parent;Parent = (Parent - 1) / 2;}else break;}}void AdjustDown(size_t parent) {size_t Parent = parent, Child = 2 * Parent + 1; while (2 * Parent + 1 < size()) {if (Child + 1 < size() && _cmp(_con[Child], _con[Child + 1])) ++Child; if (_cmp(_con[Parent], _con[Child])) {std::swap(_con[Parent], _con[Child]);Parent = Child; Child = Child * 2 + 1;}else break;}}private:Container _con;Compare _cmp;};}

雖然以前實現過這個數據結構，但是把它們放在類里面還是需要進行調整的。比如向上向下調整算法的參數就是被修改的。

從這里我們也看得出來為什么是仿函數了，因為調用的形式就和函數一樣，傳入兩個參數進行比較，表達式的返回值就是比較的結果。和函數是一樣的方法，但是我們還能通過外界控制整個邏輯。

當然由于引入了仿函數的機制，所以向上向下調整算法的邏輯可能稍微需要修改一下，和以往我們在c語言數據結構中實現的那個版本還是有一些區別的。但是換湯不換藥，我們可以將符號代入進去驗證即可。(STL庫中實現的是傳類less建大堆，反之小堆，默認建大堆)。

總的來說，這個部分的模擬實現還是非常簡單的，只需了解一下適配器模式和仿函數的概念即可輕松手撕這樣的容器出來。