前言

本章我們會結合C++標準庫重點講解容器適配器以及如何用容器適配器快速實現棧和隊列。

什么是容器適配器？

首先我們看一下電源適配器，它可以將只適用于本國插頭的插座適配出適用于他國不同頻率插頭的插座。

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

觀察庫中的源碼

• 觀察庫中棧和隊列的模板，我們發現都存在Class Container=其他容器<T>,這就是利用了其他容器去實現本容器的操作即：容器適配器。
• 雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stackqueue默認使用deque，比如
  
  

那么該如何使用容器適配器呢？

我們可以先去看一下庫中棧和隊列的源碼

#include<deque>
namespace bite
{
template<class T, class Con = deque<T>>
//template<class T, class Con = vector<T>>
//template<class T, class Con = list<T>>
class stack
{
public:stack() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}
private:Con _c;
};
}#include<deque>
#include <list>
namespace bite
{
template<class T, class Con = deque<T>>
//template<class T, class Con = list<T>>
class queue
{
public:queue() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_front();}T& back() {return _c.back();}const T& back()const {return _c.back();}T& front() {return _c.front();}const T& front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}
private:Con _c;
};
}

• 可以發現庫中的棧和隊列并沒有自己原生實現各類接口，而是去調用其他容器的接口去快速實現本接口功能。
• 我們還發現了這里的其他容器默認都是deque，這是為什么呢？

想知道這些我們要先了解一下deque

deque的簡單介紹(了解)

deque的原理介紹

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

deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際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.h

#pragma once
#include<vector>
#include<deque>
#include<list>
namespace dhb
{//利用容器適配器快速實現棧template<class T, class Container = deque<T>>class stack{public:void push(const T& x){return _con.push_back(x);}void pop(){return _con.pop_back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}T& top(){return _con.back();}const T& top()const{return _con.back();}private:Container _con;};
}

queue.h

#pragma once
#include<vector>
#include<deque>
#include<list>
namespace dhb
{template<class T,class Container =deque<int>>class queue{public:void push(const T& x){return _con.push_back(x);}void pop(){return _con.pop_front();}bool empty(){return _con.empty();}T& front(){return _con.front();}T& back(){return _con.back();}const T& front()const{return _con.front();}const T& back()const{return _con.back();}size_t size(){return _con.size();}private:Container _con;};
}