stack和queue的使用和模拟实现

---

前言

上次写博客距今天已有20天了，暑假的休息到今天也就结束了，相信很多朋友和我一样虽然开学了，但还在家里上网课中，然后今天我来给大家聊聊关于C++中的stack和queue的知识，还有关于deque的了解知识。
还有给大家一个建议，C++中的容器建议根据文档来去学习，很多东西脑子是记不住的，附上C++的文档如下
C++文档

打开后建议进入旧的版本，比较容易找到我们需要的东西

在方框中搜索即可

---

正文开始

一、stack的介绍和使用

1.1 stack的介绍

stack文档介绍

1.stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定
的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
2.stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类

1.2 stack的使用

1.3 stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

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

因为容器适配器中选用的是内置类型vector，所以不用对stack进行初始化和构造函数的实现，由编译器帮你实现.

二、queue的介绍和使用

2.1 queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于先进先出中操作，其中从容器一端插入元素，另一端获取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的
   成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操
   作:
   empty：检测队列是否为空
   size：返回队列中有效元素的个数
   front：返回队头元素的引用
   back：返回队尾元素的引用
   push_back：在队列尾部入队列
   pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标
   准容器deque。
   

2.2 queue的使用

2.3 queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue，
具体如下：

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

三、容器适配器

4.1 什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总
结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
我们先来看看库里对stack和queue容器适配器的实现是用什么来完成的

可以看出库里对栈和队列的实现利用到了deque，deque是一个双端队列

4.3 deque的简单介绍(了解)

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和
删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比
较高。

但是他不是一个真正意义上连续的空间，而是由一小段一小段空间利用指针连接而成的一段空间，
实际上deque就类似于一个动态开辟的二维空间

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落
在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

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

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可
以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有
push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和
queue默认选择deque作为其底层容器，主要是因为：
1.stack和queue不需要遍历，所以本身也就没有迭代器，只需要在容器的一端或者两端操作数即可
2.stack和deque的元素增长中可能需要扩容，但是deque不需要，容量满了，继续开辟一小段空间就好
结合了deque的优点，而完美的避开了其缺陷。

---

（本章完）