【C++】STL之适配器---用deque实现栈和队列

前言

一、deque

1、deque 的原理介绍

2、deque 的底层结构

前言

容器适配器，按字面意思理解的话，就是用来对一个容器进行匹配的。在C++STL中，容器有：vector，list，deque，map，set等。而在C++STL中不把stack和queue纳入容器的范围而是纳入容器适配器的范围是因为：

stack和queue没有下标随机访问等操作，只有普通的pop_front,push_back,pop_back()等操作，而这些函数在其他容器中完全可以有，栈和队列的实现完全可以将其他容器的操作进行复用，这就是stack和queue作为容器适配器的原因。

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

一、deque

1、deque 的原理介绍

deque (双端队列)：是一种双开口的 “连续” 空间的数据结构，双开口的含义是 deque 可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)；与vector比较，头插效率高，不需要搬移元素，与 list 比较，空间利用率比较高，“随机访问” 效率较高。

2、deque 的底层结构

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

3、deque 的迭代器

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此 deque 的迭代器设计就比较复杂，如下图所示：

4、deque 的优缺点

4.1、优点

具有 vector 的优点 ---支持随机访问、缓存命中率较高、尾部插入删除数据效率高；
同时具有 list 的优点 --- 空间浪费少、头部插入插入数据效率高；

4.2、缺点

deque 的随机访问效率较低 --- 需要先通过中控数据找到对应的buffer数组，再找到具体的位置 (假设偏移量为 i，需先 i/10 得到位于第几个buffer数组，再 i%10 得到 buffer 数组中的具体位置)，即 deque 随机访问时一次跳过一个buffer数组，需要跳多次才能准确定位，其效率比 list 高了不少，但比 vector 也低了不少；
deque 在中部插入删除数据的效率是比较低的 --- 需要挪动数据，但不一定后续 buffe 数组中的数据全部挪动，可以控制只挪一部分，即中间插入删除数据的效率高于 vector，但是低于 list。

所以综上分析， deque 结合了 vector 和 list 的优缺点，看似很完美，但是它单方面的性能是不如 vector 或者 list 的，因此 deque 在实际应用中使用的非常少。

STL 中选择 deque 作为 stack 和 queue 默认适配容器的原因：

stack 和 queue 不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在 stack 中元素增长时，deque 比 vector 的效率高(扩容时不需要搬移大量数据)；queue 中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

deque 特别适合需要大量进行头插和尾部数据的插入删除、偶尔随机访问、偶尔中部插入删除的场景；不太适合需要大量进行随机访问与中部数据插入删除的场景，特别是排序。

二、stack 的介绍和使用

1、stack 的介绍

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：empty：判空操作 back：获取尾部元素操作 push_back：尾部插入元素操作 pop_back：尾部删除元素操作；
标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

2、stack 的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测 stack 是否为空
size()	返回 stack 中元素的个数
top()	返回栈顶元素的引用
push()	将元素 val 压入 stack 中
pop()	将 stack 中尾部的元素弹出

下面是栈的使用操作：

int main()
{
	//构造空栈
	stack<int> s;

	//元素入栈
	s.push(1);
	s.push(2);

	//获取栈中元素个数
	int Size = s.size();
	cout << Size << endl;

	//获取栈顶元素的引用
	int sTop = s.top();
	cout << sTop << endl;

	//元素出栈
	s.pop();
	sTop = s.top();
	cout << sTop << endl;

	//判断栈是否为空
	cout << s.empty();

	return 0;
}

3、stack 的模拟实现

我们在这里为栈模板定义了两个模板参数：T 是栈中存储的元素的类型，Container 是栈模板使用的底层结构，Container 的默认值是 vector，如果你想要用别的，可以在这里进行设置。我就可以将适配器作为类的第二个模板参数，然后通过传递不同的适配容器来实现栈了：

//stack.h
template<class T, class Container>
class stack 
{
	//...
};
//test.cpp
void test_stack() 
{
	stack<int, vector<int>> st1;
	stack<int, list<int>> st2;
}

vector 和 list 都可以作为 stack 的适配容器，我们可以通过给定不同的第二个模板参数来使用不同的容器适配 stack；

经过前期的学习，显然更适合作为 stack 的适配容器，那么我们可以还可以将 vector 设置为 stack 的默认适配容器：

//stack.h
template<class T, class Container = vector<T>>
class stack 
{
	//...
};
//test.cpp
void test_stack() 
{
	//默认使用vector做适配容器
	stack<int> st1;  
	//使用其他容器做适配容器需要显式指定
	stack<int, list<int>> st2;  
}

有了适配容器之后，我们就可以更容易的通过调用适配容器的接口来实现 stack 的接口了。

namespace xx
{
	//适配器模式/配接器
	template <class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
	void test_stack()
	{
		//stack<int,vector<int>> st;//数组栈
		stack<int, list<int>> st;//链表栈
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);
		while (!st.empty())
		{
			cout << st.top() << " ";
			st.pop();
		}
		cout << endl;
	}
}

stack 可以使用 vector 或者 list 来实现，效率相当。插入数据就相当于尾插，删除栈顶元素就相当于尾删。

三、queue 的介绍和使用

1、queue 的介绍

队列是一种容器适配器，专门用于在 FIFO 上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty：检测队列是否为空 ; size：返回队列中有效元素的个数; front：返回队头元素的引用；back：返回队尾元素的引用；push_back：在队列尾部入队列；pop_front：在队列头部出队列；
标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。

2、queue 的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回 true，否则返回 false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素 val 入队列
pop()	将队头元素出队列

下面是队列的使用操作：

int main() 
{
	//构造空队列
	queue<int> q;

	//元素入队
	q.push(1);
	q.push(2);

	//返回有效元素个数
	int size = q.size();
	cout << size << endl;

	//检查队列是否为空
	cout << q.empty() << endl;

	//获取队头元素的引用
	int front = q.front();
	cout << front << endl;

	//获取队尾元素的引用 
	int back = q.back();
	cout << back << endl;

	//队头元素出队
	q.pop();
	return 0;
}

3、queue 的模拟实现

它的模拟实现过程和 stack 类似，vector 和 list 都可以作为 queue 的适配容器，但是由于 queue 需要大量在头部删除数据，所以使用 deque 作为 queue 的默认适配容器，那么 queue 模拟实现的代码如下：

namespace xx
{
	template <class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		const T& front()
		{
			return _con.front();
		}
		const T& back()
		{
			return _con.back();
		}
		bool size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
	void test_queue()
	{
		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;
	}
}

本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。