stack和queue模拟实现

前言

上一期我们介绍了stack和queue的使用，本期我们来模拟实现一下他们！

本期内容介绍

容器适配器

deque介绍

为什么stack和queue的底层选择deque为默认容器？

stack 模拟现实

queue 模拟实现

什么是容器适配器？

适配器是一种设计模式，该种模式是将一个类的接口转换为用户希望的另一个接口！

什么是设计模式？

设计模式是一套被反复使用的，多数人知晓的，经过分类编目的，代码设计经验的总结。

总结：设计模式就是一种常用的编程套路，该套路被很多人知晓和使用，具有可靠性！

常见的设计模式有：单例设计模式、工厂设计模式等。

举个例子：

你平时手机没电了，你是拿充电器先到插板上去充，而不是直接去拿电线充。因为电线直接充是不符合我们的需求的（一下子弄不好你就被干没了）！我们要用插板提供的接口插充电器才可以充！其实本质你手机充的还是电线里面的电。只是把他转换了一下！充电器就像是一个适配器，将电源的接口转换成手机充电口的接口，使得手机可以与电源连接起来充电。同样地，容器适配器也起到了类似的作用，它将一个容器的接口转换成另一个容器的接口，使得原本不兼容的容器能够协同工作。

deque介绍

stack和queue中虽然也可以存放元素，但是STL并没有将他们划分到容器的行列里面！而是将其称为：容器适配器，这里是因为stack和queue只是对其他的容器进行了包装，STL中stack和queue底层默认deque， deque就是我们在上一期介绍stack和queue的时候，看到了他们的模板参数多了一个的那个容器类型的默认容器！

什么是deque?

deque到底是什么呢？上一期专门没有介绍，就等到这一期来介绍！

deque叫双端队列！是一种双开口的"连续"空间的数据结构。双开口的含义是：可以在头和尾两端进行插入和删除操作！而且时间复杂度为O(1)，与vector相比头插效率高，不需要在头删时挪动大量的数据了，与list相比，空间利用率比较高！所以我们可以认为他是list和vector的结合版！可以支持元素的随机访问。支持头尾的插入删除，而且效率很高！

注意：duque并不是真的连续的空间！而是由一段段连续的小空间拼接而成，实际的deque类似于一个动态的二维数组！

这个中控数组实际上一个数组指针！里面存的就是每个小段的数组的地址！这个中控数组是可以扩容的！！

所以双端队列的底层是一段假象的连续空间，实际上是分段连续的，为了维护其“整体连续”以及随机访问的假象，重任就落在了deque的迭代器身上了！

deque的迭代器也很复杂：

deque是如何借助迭代器维护其假想的连续结构的呢？

它的底层搞了两个迭代器start和finish一个指向第一个buffer小段数组，另一个指向最后一个buffer小数组，遍历时，从第一个buffer开始，如果不到最后一个buffer的最后一个位置即finish的最后一个end就到下一个buffer继续遍历！直到遍历完！

deque是如何用下标+[]来访问的？

因为中控数组中的每个小buffer数组的长度都是一样大的！所以我们在访问第i个位置时，通过 i / N 获取他是在那个buff数组，再根据 i % N来确定他是在第几个！从而实现了下标遍历~！

deque的缺陷

与vector相比，deque的优势是：在头部插入和删除的时候，不需要移动元素，效率特别高，而在扩容时也不需要移动大量的元素，因此这里是效率比vector高的！

与list相比，它的底层的空间是连续的，空间利用率高，不需要额外的存储字段！

但是，deque也有很致命的缺陷：

不适合遍历，一位在遍历时，deque的迭代器要频繁的去检测其是否移动到了都一小段的边界，导致效率下降！所以在实际中，需要线性结构中一般优选的是vector和list！

不适合在中间插入删除、因为你在某个中间的buffer插入时，如果满了得扩容，删除时怎么删？？你不可能说--size吧，人家下标可不管这些，解决的办法就是删除时缩容，但是缩容后就有新问题，如何知道第i个位置的元素？导致效率降低！

以及它的[]的效率很一般！下面有代码验证：

void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	deque<int> dq;
	vector<int> v;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		v.push_back(e);
		dq.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	sort(dq.begin(), dq.end());
	int end2 = clock();

	printf("vector:%d\n", end1 - begin1);
	printf("deque:%d\n", end2 - begin2);
}

我们知道sort的底层会大量的用到[]，结果差了三倍多！！！

第二个：

void test_op2()
{
	srand(time(0));
	const int N = 1000000;

	deque<int> dq1;
	deque<int> dq2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(dq1.begin(), dq1.end());
	int end1 = clock();

	int begin2 = clock();
	// vector
	vector<int> v(dq2.begin(), dq2.end());
	sort(v.begin(), v.end());
	dq2.assign(v.begin(), v.end());
	int end2 = clock();

	printf("deque sort:%d\n", end1 - begin1);
	printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}

这个是把一个deque的数据拷贝到vector排完了再拷回来，都比deque快：

所以ton过这两个栗子足以证明deque的[]效率可见一般了~！

为什么stack和queue的底层选择deque为默认容器？

STL选择让他默认为栈和队列的原因有两个：

1、stack和queue不需要遍历，他们根本没有迭代器。只是需要在固定的一端或两端进行插入和删除操作！

2、在stack中元素增加时，与vector相比deque的扩容效率更高（deque扩容不需要移动大量的数据）。

综上两点，deque完美的解决stack和queue的问题，而且正好弥补了用vector和list的缺陷！所以STL就选择了他作为默认的容器！

OK，我们来看看它的接口：

直接包含了vector和list所有的好用接口！！！

stack的模拟实现

我们以前在数据结构的时候，实现栈使用的是单链表或顺序表！这里你也可以接着这样玩，直接用vector和list。但是我这里就不这样玩了，我直接来使用deque！

    template<class T, class Container = deque<T>>
	class stack
	{
	public:
		stack()
		{}

		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()
		{
			assert(!empty());
			_con.pop_back();
		}

	private:
		Container _con;
	};

这里都很简单不在逐一解释！

需要注意的是：你可以不用写这个stack的默认构造！因为stack这个类里面只有一个自定义类型的变量！所以你不写编译器默认生成的那个就自己去调用调他自己成员的默认构造了！

另外，这里选择的是尾部实现的，你也可以选择头部实现！

queue模拟实现

同样的队列这里你也可以和数据结构那样搞个链表玩！介绍了deque那必然用它~！

    template<class T, class Container = deque<T>>
	class queue
	{
	public:
		queue() 
		{}

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

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

		T& front() 
		{
			return _con.front();
		}

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

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

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

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

	private:
		Container _con;
	};