前言

本文章会和大家进行对SGI STL中的stack和queue进行讲解和模拟实现。从模拟中体会容器适配器的特点；体会两者数据结构的特点……

1. stack

1.1 stack数据结构

stack是一种先进后出（First In Last Out， FILO）的数据结构。它只有一个出口。（如下图）stack允许增加元素、移除元素、取得最顶元素。但是除了该出口以外，没有任何其它的方法可以存取stack的其它元素。也就是说，stack是一种不允许被遍历的容器。

1.2 stack模拟实现

• 我们发现，stack可以以某种既有的容器作为底部结构，将其的接口复用改变，使之接口变为适合“先进后出”的特性的接口。这对于我们来说是极其容易做到的……而deque这个容器恰恰提高了非常高效的双开口操作（我们使用一个开口就可以了）。因此，SGI STL中，便是以deque作为stack在缺省情况下的底部结构。

下面附上完整的模拟代码：

namespace LL
{
	template <class T, class Container = std::deque<T>>
	class stack
	{
		Container _c; //定义底层容器
	public:
		bool empty()
		{
			return _c.empty();
		}
		size_t size()
		{
			return _c.size();
		}
		T& top()
		{
			return _c.back(); //返回底层的最后一个元素
		}
		void push(const T& val)
		{
			_c.push_back(val);
		}
		void pop()
		{
			_c.pop_back();
		}
		//……其它接口
	};
}

2. queue

2.1 queue数据结构

queue是一种先进先出（First In First Out）的数据结构。它有两个开口（如下图）。queue和stack一致，允许新增元素、移除元素，取队头元素。且同stack一样，不能有遍历行为……

2.2 queue模拟实现

和stack一致的……

namespace LL
{
	template <class T, class Container = std::deque<T>>
	class queue
	{
		Container _c;
	public:
		//const属性下面没有添加
		bool empty()
		{
			return _c.empty();
		}
		size_t size()
		{
			return _c.size();
		}
		T& front()
		{
			return _c.front();
		}
		T& back()
		{
			return _c.back();
		}
		void push()
		{
			_c.push_back();
		}
		void pop()
		{
			_c.pop_front();
		}
		//……其它接口
	};
}

3. 总结

像stack和queue这样的以底部容器完成其工作，且具有这种“修改某物接口，形成另外一种风格”的性质，被称为adapter(适配器)，因此，像stack和queue这样的，一般不会被归为Container，而是归为：container adapter。