目录

一、deque的简单介绍 

1.deque的物理结构 

2.deque的内部结构

二、deque的迭代器

三、为何要选用deque作为stack和queue的默认容器 

四、stack的模拟实现

五、queue的模拟实现

---

一、deque的简单介绍 

1.deque的物理结构 

        deque是一种双向开口的连续性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。

2.deque的内部结构

        deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

        从deque的结构图来看map就是一个指针数组， 数组中的每个元素是一个地址，地址分别对应了一块较大的连续空间，用来存储数据。

        需要注意：map中的元素我们称之为一个一个的buffer，当开辟第一个buffer时并不是从头开辟的，而是在从中间去开辟，当这个buffer指向的空间所存储的数据已满时，想要在这个这个buffer所指向的空间前插入元素时，就会在前面开辟一块同样大小的空间，在map数组中前一个buffer就会指向这段空间，以此类推。

        deque是如何访问元素的呢？

//假设有如下定义
deque<int> dq;

二、deque的迭代器

deque的迭代器是一个start类和finish类，分别包含了四个指针cur、first、last、node;

迭代器strart中:

cur     ----- 指向此迭代器所指缓冲区中的现行元素开头

first    ----- 指向此迭代器所指缓冲区的头

last     ----- 指向此迭代器所指缓冲区的尾（含备用空间）

node  ----- 指向的是管控中心

迭代器finish中:

cur     ----- 指向此迭代器所指缓冲区中的现行元素结尾

first    ----- 指向此迭代器所指缓冲区的头

last     ----- 指向此迭代器所指缓冲区的尾（含备用空间）

node  ----- 指向的是管控中心

通过cur指针来访问元素，当第一个buffer访问至结束时，通过node指针++操作，进入到第二个buffer，此时first、last也同时管控新的buffer；

三、为何要选用deque作为stack和queue的默认容器 

stack和queue的默认容器是deque，我们仔细思考一下，在没有deque的情况下：

对于stack：我们也可以用 vector 和 list ；对于queue：我们只能使用 list ；

问题1：stack如果选用vector，相比选用deque，哪一个更好？为什么？

deque的优势在于：扩容代价不大，不需要拷贝数据，浪费空间也不大

问题2：stack&queue如果选用list，相比选用deque，哪一个更好？为什么？

deque的优势在于：cpu高速cache命中高，以为是一段连续的空间；此外，list需要频繁的申请小块空间。从申请和释放空间上来看，deque申请和释放空间次数少，代价低，唯一需要扩容的就是中控数组（map），但代价也很小。

总结：deque适合头尾的插入删除，但是中间插入删除和随机访问效率都差强人意。所有要高频随机访问还得是vector，要任意位置插入，还得是list；

四、stack的模拟实现

        结合上面的分析，总结下来deque在设计出来的时候还是考虑到很多地方的，在模拟实现上，我们给模板的第二个参数加上Container，它接收的是容器，如vector、list

#include<vector>
#include<list>
 
// 适配器模式
namespace mlg
{
    // 为了能够实现接收以下其他容器，模板参数需要加上Container
	// stack<int, vector<int>> s;
	// stack<int, list<int>> s;
 
	template<class T, class Container = deque<T>>//模板增加一个容器参数，给到缺省值
	class stack
	{
	public:
        //判断栈是否为空
		bool empty() const {return _con.empty();}
 
        //计算当前栈中有效元素的个数
		size_t size() const {return _con.size();}
 
        //取栈顶的元素
		const T& top() const {return _con.back();}
 
        //尾插（元素入栈）
		void push(const T& x) {_con.push_back(x);}
 
        //尾删（元素出栈）
		void pop() {_con.pop_back();}
 
	private:
		Container _con;//成员变量是未知的容器
	};
 
	void test_stack()
	{
		//stack<int, std::vector<int>> s;
		//stack<int, std::list<int>> s;
		stack<int> s;
 
		s.push(1);
		s.push(2);
		s.push(3);
		s.push(4);
 
		while (!s.empty())//判断栈是否为空
		{
			cout << s.top() << " ";//取栈顶的元素
			s.pop();//删除栈顶的元素，两个函数结合就能实现栈中元素出栈效果
		}
		cout << endl;
	}
}

五、queue的模拟实现

#include<vector>
#include<list>
 
namespace mlg
{
    // 为了能够实现接收以下其他容器，模板参数需要加上Container
	// stack<int, vector<int>> s;
	// stack<int, list<int>> s;
 
	template<class T, class Container = deque<T>>//模板增加一个容器参数，给到缺省值
	class queue
	{
	public:
 
        //判断队列是否为空
		bool empty() const {return _con.empty();}
 
        //计算当前队列中有效的元素个数
		size_t size() const {return _con.size();}
 
        //取队头的元素
		const T& front() const {return _con.front();}
 
        //取队尾的元素
		const T& back() const {return _con.back();}
 
        //队尾入数据
		void push(const T& x) {_con.push_back(x);}
 
        //队头出数据
		void pop() {_con.pop_front();}
 
	private:
		Container _con;//成员变量是未知的容器
	};
 
	void test_queue()
	{
		//queue<int, vector<int>> q;
		//queue<int, list<int>> q;
		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;
	}
}

        最后，对于STL之前的几篇博客还要一个知识点未曾提及，那就是迭代器相关的，将会在后续的博客中进行介绍。