STL容器 ——stack和queue的模拟实现

前言： stack和queue两大容器的实现，还需要我们模拟实现它的构造，析构之类的吗？换言之：还需要手动的造轮子吗？我们可以复用其他的容器吗？stack要求先进后出，无非就是vector的尾插尾删；queue要求先进先出，无非就是list的头删尾插，这个不用vector的原因是：vector的头删效率较低，它得挪动数据，对吧。其实stack和queue底层复用得是deque，这个一会简单介绍一下。

---

1. 容器适配器

适配器是一种设计模式，它是将一种接口封装成我们所需得接口。stack和queue就是利用了容器适配器这种思想，它俩是对deque的封装使用。
可以看一下它俩实现的模板参数：


非常清楚的看到，模板参数默认传的是deque，当然我们也可以传其他的容器，比如传vector，list。如果传的容器不能够支持stack，queue的功能，在使用时会报错。

所以总结来说，stack和queue是利用了适配器这这设计模式进行的设计.。

---

2. stack的模拟实现

stack我们要求：只能从栈顶取出数据，从栈顶压入数据。

所以利用vector的尾插尾删就可以了。当然list也是满足需求的。

#include
namespace ly
{
	template<class T>
	class stack
	{
	public:
	    //压入数据
		void push(const T& val)
		{
			_stack.push_back(val);
		}
		//出栈
		void pop()
		{
			_stack.pop_back();
		}
		//求size
		size_t size() const
		{
			return _stack.size();
		}
		//栈顶数据
		const T& top() const
		{
			return _stack.back();
		}
		//判空
		bool empty() const 
		{
			return _stack.empty();
		}

	private:
	    //vector来实现stack，也可以是list
		std::vector<T> _stack;
	};
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

3. queue的模拟实现

queue要求：先进先出，也就是尾插，头出。

这个使用vector来实现就有点挫了，因为vector的头删复杂度是O(n)，需要挪动数据，所以使用lis来实现是满足需求的。

#include
namespace ly
{
	template<class T>
	class queue
	{
	public:
	    //插入数据
		void push(const T& val)
		{
			_queue.push_back(val);
		}
		//出队列
		void pop()
		{
		     //头出 
			_queue.pop_front();
		}
		// 求size
		size_t size() const
		{
			return _queue.size();
		}
		// 查看队列顶部数据
		const T& front() const
		{
			return _queue.front();
		}
		//判空
		bool empty() const
		{
			return _queue.empty();
		}

	private:
		std::list<T> _queue;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

4.deque的简易了解

deque设计的初衷是：既能支持随机访问，又能支持O(1)的插入操作，而且扩容也要求不能过于浪费空间。哇塞，想到这，这个deque也太牛了。简直完全可以去替代vector和list了，而且比它俩都牛。但是其实并不能替换vector或list。

deque是一个双端队列，也就是说它的头和尾都能够进行插入和删除。

(1) 它的物理空间是增么做到连续的呢？
其实也没有那么连续。它是由多个小的双端队列构成，每个双端队列的指针由一个中驱数组保存。

(2) 如何支持下标随机访问的？

每个双端队列的大小都一样，所以支持下标访问也就可以了，比如 a[10],每个双端队列的大小为4，用10去除以4，等于2，余数为2。也就是第二个双端队列的第二个元素。

(3) 如何扩容？

像vector每次扩容都是2倍扩容(Linux)或是1.5倍扩容(window)。假如我需求存1001个数据，它的空间是1000，为了存那一个数据，它有可能会扩容到2000，也就是说它浪费了999个空间。但deque这个时候的优势就显出来了，它每次只扩容一个双端队列，注意双端队列一般不大，所以一定程度上降低了空间的浪费。

(4) 缺点

deque有一个非常大的缺陷，就是它的遍历很麻烦。下标访问，每次都得计算后，才能找到对应的数据，还有它的迭代器需要不断的判断是否越界。这就导致遍历的效率较低了。所以线性结构一般都会用list或vector，而不是deque；为什么呢?因为线性结构应用场景下，多数需要进行多次的遍历。目前deque的应用，就是作为stack和queue的底层数据结构。

(5) deque作为stack和queue的底层数据结构的原因

• stack和queue都不需要遍历。这就很符合deque的尿性
• 在扩容方面，比vector要好
• 在空间利用率方面，比list要好

还有一点我一直说是双端队列，但并不是队列，队列要求先进先出，而它是两端都可进可出。
它文档中写的是double ended queue，所以译成双端队列，也没毛病。

---

5. 有默认容器参数的stack和queue

上面的版本，我完成的比较粗暴，但是看到STL中的实现是有默认容器参数的。所以在对deque有一定了解的前提下，咱们来加上这个默认容器参数。

（1）stack的模拟实现

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

	private:
		container _stack;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

（2）queue的模拟实现

namespace ly
{
	template<class T,class container = deque<T>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_queue.push_back(val);
		}
		void pop()
		{
			_queue.pop_front();
		}
		size_t size() const
		{
			return _queue.size();
		}
		const T& front() const
		{
			return _queue.front();
		}
		bool empty() const
		{
			return _queue.empty();
		}

	private:
		container _queue;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

所以我们在使用stack和queue时，可以这样调用：

stack<int,vector<int>> s;
stack<int>s1;

queue<int,list<int>> q;
queue<int>;
1
2
3
4
5

如果有想实验的小伙伴，我觉得queue也可以适配vector。那么给大家看看结果：

queue<int,vector<int>> ss;
1

很明显出错了，我还是用的STL中的queue来实验的。
它不支持头删除这个接口，如果我们自己非要用vector来模拟实现也是可以的，那就需要用到内部调用insert()。

---

结尾语：以上就是本篇内容，相信大家会加深对stack和queue的理解。