C++學習第十三天——stack/queue的使用及底層剖析雙端隊列容器適配器

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?少年的旅途應是星辰大海? ? ? ? 🌏?

📃個人主頁：island1314

🔥個人專欄：C++學習

🚀?歡迎關注：👍點贊 👂🏽留言 😍收藏??💞 💞 💞

🚀前言

點擊跳轉到文章【C++學習第十二天——list容器的深度剖析及底層實現】

前面我們已經學習了list容器的相關知識，本文主要介紹STL中另外兩種重要的結構，stack和queue。但是在STL中這兩者并沒有劃分在容器范圍內，而是將其稱為容器適配器。

💥一、容器適配器

1、什么是容器適配器？

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

2、STL標準庫中stack和queue的底層適配？

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

💥二、雙端隊列deque的介紹

1、deque的原理介紹

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

deque在功能上是vector和list的結合體，如圖：

? ? ?deque并不是真正連續的空間，而是由一小段一小段連續的buff小數組和中控數組(指針數組)構成，實際deque類似于一個動態的二維數組，其底層結構如下圖所示：

? ? ? ?小數組滿了之后不擴容，而是再開辟一小段空間做buff，并且開辟buff數組時并不是從中控數組的開頭開始申請的，而是在中間，頭插尾插時才向兩邊申請。

比如：

? ?

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

2、deque的缺陷

? （1）與vector比較，deque的優勢是：頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的。

??（2）與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。

? （3）但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，并且deque的中間位置的insert 和erase 也要挪動數據，效率并不高。而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。

3、為什么選擇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的優點，而完美的避開了其缺陷。

💥三、對于stack和queue的使用和模擬實現

1、stack和queue的使用

首先，使用stack和queue需要包含頭文件< satck > 和 < queue >。

stack和queue的主要接口十分簡單：

代碼如下：

#include<stack>
#include<queue>int main()
{	//stack的使用stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;//queue的使用queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;return 0;
}

2、stack的模擬實現

//template <class T,class Con = list<T>>
//template <class T,class Con = vector<T>>
template <class T,class Con = deque<T>>
class stack
{
public: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.back();}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}private:Con _con;
};

3、queue的模擬實現

//template<class T, class Con = list<T>>
template<class T, class Con = deque<T>>
class queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& back(){return _con.back();}const T& back()const{return _con.back();}T& front(){return _con.front();}const T& front()const{return _con.front();}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}private:Con _con;
};