STL--stack、queue实现

STL中，vector、list 是容器，自己存储一系列的数据进行增删查改，而 stack、queue 是一种特殊的容器，叫容器适配器，提供一种特定的接口来访问底层容器。

STL--stack实现

template<class T, class Container = deque<T>>
	class stack
	{
	public:
		stack()
		{}
		void push(const T& x)
		{
			return _con.push_back(x);
		}
		void pop()
		{
			return _con.pop_back();
		}
		size_t size()
		{
			return _con.size();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

STL--queue实现?

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

stack可以使用 vector、list、deque 来适配；queue只能通过 list、deque来适配，因为 queue 的 pop相当于是头删，vector中没有头删这个功能！

容器适配器默认参数?deque

deque叫双端队列，但它不是队列，它的意思是进行头部和尾部插入、删除比较方便。

deque的内部是由多个 buff 子数组和一个中控指针数组，当中控数组满了之后才需要扩容，并且扩容的代价极低（新开空间后，只需要拷贝指针即可）

虽然 deque 也可以进行任意位置的插入和删除，但效率却不是很高。

中间插入删除：当每个 buff数组 一样大，需要整体挪动数据，中间插入删除效率低，但下标的随机访问 [ ] 快很多！因为?当每个buff 数组一样大时，可以直接计算出数据的下标；当每个 buff 数组不一样大时，中间插入删除不需要整体挪动数据，只需要对buff 单独操作即可，但下标的计算将会困难很多！