C++stack和queue

容器适配器：

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

STL标准库中stack和queue的底层结构：stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，如：

deque双端队列：

deque其实是list和vector的结合体，具有两种结构的优点

vector的优势：下标访问，效率高

劣势：扩容，头部插入删除效率很低

list的优势：按需申请释放空间，任意位置插入删除效率都很不错

劣势：下标访问效率低

deque的结构。下标访问，数量少访问还行，但是大量访问的话，效率不高,并且中间位置的插入删除要考虑挪动数据，效率不高，但deque得头尾插入删除很不错，所以做stack和queue的默认适配容器是很适合的

 选取deque做stack和vector适配器原因：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。

2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长 时，deque不仅效率高，而且内存使用率高。

stack的模拟实现：

	//queue和stack都不支持迭代器，防止随机访问
	
	//适配器,提供了统一访问容器的方式，封装屏蔽了底层的细节
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		T& top()
		{
			return _con.back();
		}
		const T& top() const
		{
			return _con.back();
		}
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_back();
		}
	private:
		Container _con;//调用自定义类型的默认构造
	};

 queue:

template<class T, class Container = deque<T>>//vector不支持头删，效率太低
	class queue
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& front()
		{
			return _con.front();
		}
	const	T& back()
		{
			return _con.back();
		}
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
	private:
		Container _con;
	};

 stack和queue的实现相较于之前list和vector很轻松，原因就是我们在这里使用了适配器