C++：deque的概念以及stack和queue的模拟实现

本篇主要总结的是stack和queue的模拟实现以及deque的原理

stack的模拟实现

和前面的模拟实现相同，首先要看官方实现的功能

这里引入了Container的概念，从字面意思来看，也就是说，在实例化模板的时候实际上是需要实例化两个参数的，一个是栈内元素的数据类型，一个是容器的类型，这里通过缺省参数给定了一个deque，因此平时使用的时候不需要实例化第二个参数，关于deque的概念后面再进行讲解

从中可以看出，stack的实现是以一个容器为模板，在这个模板的基础上引申出了栈的概念，因此在模拟实现的过程中相对容易一些

#include 
#include 
#include 
#include 

namespace mystack
{
	template <class T,class Container>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		bool empty()
		{
			return _con.empty();
		}
		int size()
		{
			return _con.size();
		}
		const T& top()
		{
			return _con.back();
		}
	private:
		Container _con;
	};
}
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

但是在实际的栈的实现中，是使用带有缺省参数的模板参数，在容器的实现中是使用的是deque，因此在使用STL中的模板实例化只需要实例化第一个参数即可，默认是使用的是deque，也可以实例化为vector和list

#include "stack.h"
#include 


// 采用vector来当容器生成栈
int main()
{
	std::stack<int, std::vector<int>> s;

	// 入栈
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	// 出栈
	while (!s.empty())
	{
		std::cout << s.top() << " ";
		s.pop();
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include "stack.h"
#include 


// 采用list来当容器生成栈
int main()
{
	std::stack<int, std::list<int>> s;

	// 入栈
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	// 出栈
	while (!s.empty())
	{
		std::cout << s.top() << " ";
		s.pop();
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

deque

那么下面引入deque的概念，什么是deque，它的用法又是什么？

还是从cplusplus中查阅它的概念

deque的概念

deque也被叫做双端队列，从名字可以看出通俗来说它就是在两端都可以进出的队列，因此可以随意的头插头删尾插尾删

deque的底层实现方式

从上面的内容可以知道，deque可以实现在容器两端进行插入删除的操作，那其内部是如何进行工作的？

上面是两个容器的不同点，其实可以看出vector的优点其实就对应的是list的缺点，而list的优点就对应了vector的缺点，因此才需要根据不同的实验需求选择对应的容器来使用

deque的原理

deque的原理就是采用了一个中控数组用来管理每一个小数组，所以中控数组是一个指针数组，其中存储的是每一个小数组的指针，当需要插入元素的时候，就在这个中控数组的中间部分的指针指向的元素中进行插入，这样的模式就导致它具备了向前面插入数据，也具备了向后面插入数据的能力

向头部和尾部插入数据：

---

如果头部有数据继续头插，那么就会开辟额外的小数组用来存储

但是这样就产生了一个问题，如果中控数组控制的小数组已经排满了数据，但是我还要实施插入的操作应该如何实现？

1. 可以整体挪动数据，把所有数组向后挪动一位
2. 可以对单个小数组进行扩容，使得每一个小数组的长度不一样

这是两种扩容的思路，如果采用第一种思路，那么在挪动数据的时候效率会很低，但是优势是进行下标的随机访问的时候拥有更高效的功能
如果采用的是第二种思路，那么在插入数据的时候成本很低，但是在访问的时候就有较高的计算成本

因此两种扩容思路都有其好的一点和坏的一点，具体如何实施看对于容器的需求如何

在实际的使用场景中，对于deque其实是不常用的，因为它兼容了vector和list的部分优势，但是在随机访问的情况下不如vector，在插入删除数据的方面不如list，只是出于一个较为兼容的容器，在实际开发中应用场景并不多

那为什么会选择deque作为底层容器的实现？

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以; queue是先进先出的特殊线性数据结构，只要具有push_back()和pop_front()操作的线性结构，都可以作为queue的底层容器，比如list

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为:

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据); queue中的元素增长时，deque不仅效率高，而且内存使用率高，结合了deque的优点，而完美的避开了其缺陷

queue的模拟实现

#include 
#include 
#include 
#include 

namespace myqueue
{
	template <class T,class Container=std::deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		bool empty()
		{
			return _con.empty();
		}
		int size()
		{
			return _con.size();
		}
		const T& front()
		{
			return _con.front();
		}
		const T& back()
		{
			return _con.back();
		}
	private:
		Container _con;
	};
}
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

#include "queue.h"

int main()
{
	myqueue::queue<int> q;

	// 插入数据
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);

	// 打印数据
	while (!q.empty())
	{
		std::cout << q.front() << " ";
		q.pop();
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里直接使用了deque作为缺省参数，因此实例化只需要使用一个参数即可