一、deque介紹

deque(雙端佇列)：是一種雙開口的“連續”空間的資料結構，雙開口的含義是：可以在頭尾兩端進行插入和洗掉操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不必搬動資料；與list相比，空間利用比較高，

deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維陣列，其底層結構如下圖：

deque采用一塊所謂的map(注意：不是STL的map容器)作為主控，這里的map是一小塊連續空間，其中每個元素都是一個指標，指向另一段（較大的）連續線性空間，稱為緩沖區，緩沖區才是deque的存盤空間主體，SGI STL允許我們指定緩沖區大小，默認值0表示將使用用512bytes緩沖區，

deque資料結構：

template<class T,class Alloc=alloc,size_t BufSize = 0>
class deque{
public:
	iterator begin();
	iterator end();
	typedef T value_type;
	typedef value_type* pointer;
	...
protected:
	typedef pointer* map_pointer;// T**
protected:
	map_pointer map;	//指向map, map是塊連續空間，其內的每個元素都是一個指標，指向一個緩沖區
	size_type map_size;	//map內可容納多少指標
	...
}

我們可以發現，map其實是一個T **，也就是說它是一個指標，指向一個型別為T的一塊空間，

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

deque 迭代器資料結構：

template<class T,class Ref,class Ptr,size_t BufSiz>
struct __deque_iterator{
	typedef T** map_pointer;
	T* cur;				//此迭代器所指之緩沖區中的現行元素
	T* first;			//此迭代器所指之緩沖區的頭
	T* last;			//此迭代器所指之緩沖區的尾
	map_pointer node;	//指向管控中心，即中控器
}

deque迭代器的"++"、"- -"操作是遠比vector迭代器繁瑣，其主要作業在于緩沖區邊界，如何從當前緩沖區跳到另一個緩沖區，deque內部在插入元素的時候，如果map中的node數量全部使用完時，且node指向的緩沖區也沒有空間，這時會配置新的map（當前的2倍+2的數量）來容納更多的node，也就是可以指向更多的緩沖區，在deque洗掉元素時，也提供了元素的析構和空閑緩沖區空間的釋放等機制，

1.1、deque的缺點

與vector比較，deque的優勢是：頭部插入和洗掉時，不需要搬動資料，效率特別高，而且在擴容時，也不需要搬移大量的資料，因此效率比vector高，

與list相比，其底層是"連續"的，空間利用率較高，不需要存盤額外的欄位，

deque有一個致命的缺陷就是不適合遍歷，因為在遍歷的時候需要頻繁的去檢查是否需要移動到某段小空間的邊界，進而需要跳轉緩沖區，因此導致效率低下，而序列式場景中經常用到，所以在實際情況中，需要線性結構時我們會優先考慮vector和list，在STL中主要應用于stack和queue的默認配接器，

二、容器配接器

2.1、什么是配接器

配接器是一種設計模式，該種模式是將一個類的介面轉換成客戶希望的另外一個介面，

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

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

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

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

2.3、stack和queue的模擬實作

#include<deque>
namespace MySTL{
	template<class T,class Sequence=deque<T> >
	class stack{
	public:
		bool empty()const {return c.empty();}
		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();}
	private:
		Sequence c;
	};

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

2.4、stack和queue沒有迭代器

1、stack所有元素的進出都必須符合"先進后出"的條件，只有stack頂端的元素，才有機會被外界取用，stack不提供走訪功能，也不提供迭代器，

2、queue所有元素的進出都必須符合"先進先出"的條件，只有queue頂端的元素，才有機會被外界取用，queue不提供走訪功能，也不提供迭代器，

2.5、以list作為stack的底層容器

除了deque之外，list也是雙向開口的資料結構，上述stack源代碼中使用的底層容器的函式empty，size，back，push_back，list都具備，所以可以用list為底部結構并封閉其頭端開口，一樣能夠輕易形成stack，

#include<stack>
#include<list>

using namespace std;

int main() {
	stack<int, list<int>> istack;
	istack.push(1);
	istack.push(3);
	istack.push(5);
	istack.push(7);
	cout << istack.size() << endl;	// 4
	cout << istack.top() << endl;	// 7
	istack.pop();
	cout << istack.top() << endl;	// 5
	istack.pop();
	cout << istack.top() << endl;	// 3
	istack.pop();
	cout << istack.top() << endl;	// 1
	cout << istack.size() << endl;  // 1
	return 0;
}

2.5、以list作為queue的底層容器

除了deque之外，list也是雙向開口的資料結構，上述queue源代碼中使用的底層容器的函式empty，size，back，push_back，list都具備，所以可以用list為底部結構并封閉其頭端開口，一樣能夠輕易形成queue，

#include<queue>
#include<list>

using namespace std;

int main() {
	queue<int, list<int>> iqueue;
	iqueue.push(1);
	iqueue.push(3);
	iqueue.push(5);
	iqueue.push(7);
	cout << iqueue.size() << endl;	// 4
	cout << iqueue.front() << endl;	// 1
	iqueue.pop();
	cout << iqueue.front() << endl;	// 3
	iqueue.pop();
	cout << iqueue.front() << endl;	// 5
	iqueue.pop();
	cout << iqueue.front() << endl;	// 7
	cout << iqueue.size() << endl;  // 1
	return 0;
}