初识C++ · 模拟实现stack和Queue

前言：

经历了list三个自定义类型的洗礼，来个简单的放松放松，即栈和队列：

文档记录的，栈和队列是一种容器适配器，它们不属于stl，但是它们的大体结构我们都是了解的，在数据结构初阶我们已经用了C语言进行实现，这里用C++进行实现。

1 Stack

根据文档，stack也是使用了模板，第一个参数是数据类型，那么第二个是？

我们在C语言阶段使用的是一个整型指针，一个size一个capacity来实现，如果我们在C++仍然这样实现就不用介绍了，没意思了就。

后面的参数deque是另一种结构，叫做双端队列，后面细说，为什么引入第二个模板参数呢？

因为我们有了vector list基础，完全可以复用的，为什么复用vector list，就和deque有关了。

1.1 双端队列

deque是双端队列，那么为什么在stack queue的模板参数里面都有这个结构呢？

因为这个结构集成了vector和list，但是不是只集成了它们的优点。

先简单谈谈deque的结构：

list的优点是插入删除效率很高，缺点是不好访问数据，vector的优点是访问任意数据的效率很高，缺点是插入删除数据如果在头部或者中间的效率很低。

所以惠普的大佬就寻思再来一个结构，可以当vector用也可以当list使用，这里因为是了解，所以就直接给结构了:

看起来就像是个大boss，当我们存数据的时候，该结构会开一块空间，比如叫buff，空间大小为16，当一直插入数据，该数据插满之后，不会扩容，会重新开一块空间，空间大小也是16，数据插好后，我们该如何快速访问呢？ 假定开的空间大小不变，我们想访问第i个数据，一块空间的大小为N，那么我们就应该先找到i数据在第几个空间的，在找该数据在第几个，找到在哪个空间可以i / N，第几个可以i % N，这样就可以快速访问了。

那么这么多空间应该如何管理？

这里使用的是中控指针，即再开一块空间，这块空间里面只有指针，指针指向不同的空间，但是指针是从中间开始存储的，因为涉及到头插。

但是对于deque的结构来说，只有两个迭代器，一个迭代器有4个指针，分别指向当前节点，头结果，尾节点和中控指针的节点，如果涉及到了插入删除数据，比如头插，就要先开一块空间，倒着存数据，那么此时找数据，i就要先减去这个不满的第一个数据块的数据个数，才能通过/ % 快速访问数据。中间插入数据的时候，有两个选择，一是重新开空间，二是在原来的空间上扩容，但是扩容之后，每个空间的大小不一样，找数据的效率就会降低了。

当涉及删除数据的时候，删除了之后，后面的数据往前移动，比较麻烦。

所以别看deque集成了list vector，缺点也蛮多的。

比如访问数据的效率不极致，中间插入删除数据也没list快，它就比较尴尬。。

这也是为什么，stack queue的模板参数默认是deque，这个"大哥"虽然有点缺点，但是用起来也算不错。

我们在stack实现的接口有入栈 出栈 size empty 返回栈顶元素，只有5个接口，这5个接口在vector里面都有，所以，直接使用：

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

}

这里有个很牛逼的点就是，模板参数也可以有缺省值，我们给上vector<int>，那么默认的用vector来实现stack。

测试代码如下：

#include "Stack.h"
using namespace Free3;
int main()
{
	Free3::stack<int, vector<int>> s1;
	Free3::stack<int> s2;
	s1.push(1);
	s1.push(2);
	s1.push(3);
	s1.push(4);	
	s2.push(1);
	s2.push(2);
	s2.push(3);
	s2.push(4);
	s2.push(5);
	while (!s2.empty())
	{
		cout << s2.top() << " ";
		s2.pop();
	}
	cout << endl;
	return 0;
}

2 Queue

队列这里还有点不一样，栈可以用vector也可以用list，但是队列不行，队列的出队，相当于是头删，如果非要用vector里面的erase来头删也可以，但是效率很差，是O(N)，这里就非常不推荐，所以队列就用list来实现。

namespace Free4
{
	template<class T>
	class Queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size()
		{
			return _con.size();
		}
		T& front()
		{
			return _con.front();
		}
		bool empty()
		{
			return _con.empty();
		}

	private:
		list<T> _con;
	};

}

感谢阅读！