=========================================================================
個人主頁點擊直達：小白不是程序媛
C++系列學習專欄：C++干貨鋪
代碼倉庫：Gitee
=========================================================================
目錄
stack的介紹和使用
stack的介紹
stack的使用
queue的介紹和使用
queue的介紹
queue的使用
容器適配器
什么是適配器
STL中stack和queue的底層結構
deque的介紹
deque的缺陷
為什么選擇deque作為stack和queue的底層默認容器？
stack的模擬實現
queue的模擬實現
stack的介紹和使用
stack的介紹
1. stack是一種容器適配器，專門用在具有后進先出操作的上下文環境中，其刪除只能從容器的一端進行元素的插入與提取操作。
2. stack是作為容器適配器被實現的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
3. stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下操作：
- empty：判空操作
- back：獲取尾部元素操作
- push_back：尾部插入元素操作
- pop_back：尾部刪除元素操作
4. 標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque。
?
?
stack的使用
| 函數名稱 | 函數作用 |
| stack() | 構造空的棧 |
| empty() | 檢測stack是否為空 |
| size() | 返回stack中元素的個數 |
| top() | 返回棧頂元素的引用 |
| push() | 將元素val壓入stack中 |
| pop() | 將stack中尾部的元素彈出 |
stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.size() << endl;while (!st.empty()){cout << st.top() << " ";st.pop();}
?
queue的介紹和使用
queue的介紹
?
1. 隊列是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。
2. 隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。
3. 底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操作:
- empty：檢測隊列是否為空
- size：返回隊列中有效元素的個數
- front：返回隊頭元素的引用
- back：返回隊尾元素的引用
- push_back：在隊列尾部入隊列
- pop_front：在隊列頭部出隊列
4. 標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque。?
queue的使用
| 函數名稱 | 函數作用 |
| queue() | 構造空的隊列 |
| empty() | 檢測隊列是否為空，是返回true，否則返回false |
| size() | 返回隊列中有效元素的個數 |
| front() | 返回隊頭元素的引用 |
| back() | 返回隊尾元素的引用 |
| push() | 在隊尾將元素val入隊列 |
| pop() | 將隊頭元素出隊列 |
queue<int> qu;qu.push(1);qu.push(2);qu.push(3);qu.push(4);qu.push(5);cout << qu.size() << endl;while (!qu.empty()){cout << qu.front() << " ";qu.pop();}
?
容器適配器
什么是適配器
適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。
STL中stack和queue的底層結構
雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque。
deque的介紹
deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口的含義是：
可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。?
deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維數組，?其底層結構如下圖所示：
雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜，如下圖所示：?
?
deque的缺陷
- 與vector比較，deque的優勢是：
頭部插入和刪除時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是必vector高的。
- 與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。
- 但是，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作為其底層容器，主要是因為：
1. stack和queue不需要遍歷(因此stack和queue沒有迭代器)，只需要在固定的一端或者兩端進行操作。
2. 在stack中元素增長時，deque比vector的效率高(擴容時不需要搬移大量數據)；queue中的元素增長時，deque不僅效率高，而且內存使用率高。
結合了deque的優點，而完美的避開了其缺陷。
stack的模擬實現
template<class T, class Container=deque<T>>class Stack{public:void push(const T& x){_con.push_back(x);}T& top(){return _con.back();}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};容器適配器默認缺省為deque，但是對于stack的特點：尾插尾刪；使用vector和list都可以。
queue的模擬實現
template<class T ,class Container=deque<T>>class Queue{public:void push(const T& x){_con.push_back(x);}T& front(){return _con.front();}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;queue和stack的默認缺省適配器也是deque，但是對于queue的特點：頭刪尾插；適配器可以使用list，不可以使用vector因為對于vector來說頭刪需要移動數據，不是很方便。
今天對適配器以及stack和queue的介紹、使用、模擬實現的分享到這就結束了，希望大家讀完后有很大的收獲，也可以在評論區點評文章中的內容和分享自己的看法。您三連的支持就是我前進的動力，感謝大家的支持！！?!
?
)
