模拟实现stack/queue

stack

之前的博客中介绍了栈和队列的相关功能，这里我们模拟实现一个栈和队列

大体框架

由于栈的特殊性，栈不支持迭代器访问，同时栈的实现可以使用链表也可以使用数组，因此这里定义的成员为容器类型，具体使用哪个容器可以自己传入，默认一般使用deque。

	template<class T,class Container = deque<T>>
	class stack
	{
	private:
		//vector<T> _v;
		Container _con;
	};

接口函数实现

这里上面的容器是vector、list或者deque这些有自己的构造函数，因此我们不需要再写构造函数和析构函数。其他常见的接口如下：

		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		} 

		const T& top() const 
		{
			return _con.back();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}

queue

大体框架

队列和栈类似，也是可以以不同的容器实现的，因此框架和stack一样，传入容器即可

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

	private:
		Container _con;
	};

接口函数

这里的接口函数与stack情况类似，只需要考虑栈和队列存放数据规则的不同即可，栈为后进先出，队列为先进先出。其中push等命令的实现可以直接使用容器（vector等）自身的接口函数进行复用即可，需要注意的是这种复用需要该容器本身有这个接口函数。

	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() const
		{
			return _con.front();
		}

		const T& back() const
		{
			return _con.back();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _con;
	};