🔥個人主頁： Forcible Bug Maker
🔥專欄： STL || C++
目錄
- 🌈前言
- 🔥stack的模擬實現
- 🔥queue的模擬實現
- 🔥deque（雙端隊列）
- deque的缺陷
- 🌈為什么選擇deque作為stack和queue的底層默認容器
- 🌈結語
🌈前言
本篇博客的主要內容：STL庫中stack和queue的模擬實現以及deque的介紹。
這部分是名副其實的獎勵內容了，stack和queue作為容器適配器，是基于一些容器實現（如：vector，list以及deque）。內部結構實現起來很容易，但是需要多多關注模板的一些使用。deque作為容器，也被我們叫做雙端隊列，常用作棧和隊列的底層適配容器。
🔥stack的模擬實現
#pragma once
#include<iostream>
#include<vector>
namespace ForcibleBugMaker
{// 模板也可以給缺省類型template<class T,class Container = std::vector<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}
這樣使用模板，讓我們可以通過傳入不同的類型和容器從而生成不同的stack。
如下：
stack<int> st1;
stack<double, vector<double>> st2;
stack<int, list<int>> st3;
在本段代碼中，st1和st2的結構相同，但存儲的數據類型不相同；st1和st3存儲的數據相同，但是底層的結構卻天差地別了（一個是順序結構，一個是鏈式結構）。
🔥queue的模擬實現
#pragma once
#include<deque>
namespace ForcibleBugMaker
{template<class T,class Container = std::deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& front(){return _con.front();}const T& back(){return _con.back();}private:Container _con;};}
queue在這里也是同樣的道理，不過由于vector不支持頭刪（pop_front），所以在提供Container類型時不要使用vector容器。
🔥deque（雙端隊列）
deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。
上圖的雙端隊列是我們假象出來的邏輯結構，實際上在底層的存儲中，是分段連續的，物理結構如圖：
為維護其“整體連續”以及隨機訪問的假象，deque的迭代器設計就比較復雜，如圖：
一個迭代器類型就包含四個成員變量。
| 成員變量 | 作用 |
|---|---|
| cur | 指向當前數據位置 |
| first | 指向一個buffer的開始元素 |
| last | 指向一個buffer的結束元素的下一位 |
| node | 反向指向中控數組 |
deque借助迭代器維護其假象連續結構圖：
deque的缺陷
與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是比vector高的。
與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。
但是，deque有兩個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，同時，在對deque容器中間元素進行插入和刪除操作時，消耗較大，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。
🌈為什么選擇deque作為stack和queue的底層默認容器
stack是一種后進先出的特殊線性數據結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性數據結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list。但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：
- stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
- 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。
結合了deque的優點，而完美的避開了其缺陷。
🌈結語
本篇博客的內容到這里就要結束了，我們探索了stack和queue的底層實現，同時介紹了雙端隊列，在使用deque作為stack和list的底層默認容器時，結合了deque的優點而完美避開了其缺陷。在下一篇博客，我們將會繼續開始C++的語法學習，講解模板，繼承和多態等內容，敬請期待?
（更新中……）)