目錄

一.stack 介紹

?二.stack 使用

三.stack 模擬實現

普通版本：

適配器版本：

四.queue的介紹

五. queue使用

六.queue模擬實現

七.deque介紹

1.容器適配器

2.deque的簡單介紹

3.deque的缺陷

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

---

一.stack 介紹

stack------reference

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 模擬實現

普通版本：

stack的模擬實現非常簡單，我們利用已經學過的vector去封裝他的幾個接口就可以了。

	template<class T>class Stack{public:Stack(){}const T& top(){return _v.back();}void pop(){return _v.pop_back();}void push(const T& val){_v.push_back(val);}size_t size(){return _v.size();}bool empty(){return _v.empty();}private:vector<T> _v;};int main(){Stack<int> st;st.push(100);st.push(200);st.push(300);st.push(400);while (!st.empty()){cout << st.top()<<" ";st.pop();}return 0;}

?這里我們使用的是vector做的底層容器，在std::stack中，底層容器是deque并且支持切換成其他容器，這也就是stack被叫做容器適配器的原因。

適配器版本：

容器適配器，我們僅僅需要利用一個類模板參數就可以了，一個類模板參數就可以控制底層存儲數據的容器類型，是vector還是list又或者是deque。

    //容器適配器class Container = vector<T>，class Container = list<T>....template<class T ,class Container >class Stack{public:Stack(){}const T& top(){return _v.back();}void pop(){return _v.pop_back();}void push(const T& val){_v.push_back(val);}size_t size(){return _v.size();}bool empty(){return _v.empty();}private:Container _v;};int main(){Stack<int,list<int>> st;st.push(100);st.push(200);st.push(300);st.push(400);while (!st.empty()){cout << st.top()<<" ";st.pop();}return 0;}

在類模板的哪里也是可以給缺省參數，就可以實現默認存儲容器。

template<class T ,class Container = deque<T>>

四.queue的介紹

queue-----reference

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模擬實現

因為queue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list來模擬實現queue，具體如下：

普通list版本：

    template<class T>class Queue{public:Queue(){}void push(const T& val){_q.push_back(val);}void pop(){_q.pop_front();}const T& front(){return _q.front();}const T& back(){return _q.back();}size_t size(){return _q.size();}bool empty(){return _q.empty();}private:list<T> _q;};

適配器版本：

    template<class T,class Container=list<T>>class Queue{public:Queue(){}void push(const T& val){_q.push_back(val);}void pop(){_q.pop_front();}const T& front(){return _q.front();}const T& back(){return _q.back();}size_t size(){return _q.size();}bool empty(){return _q.empty();}private:Container _q;};

?七.deque介紹

1.容器適配器

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

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

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

2.deque的簡單介紹

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

?同時從庫中提供的接口來看，deque還提供了下標的隨機訪問的功能，但是deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維數組，其底層結構如下圖所示：

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

? 3.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的優點，而完美的避開了其缺陷。