stack&queue&priority_queue

目录

一、容器适配器

二、deque

1、deque的相关函数

2、关于deque

3、deque的底层实现

4、deque的设计缺陷

5、结论

三、stack

1、stack的相关函数

2、stack相关函数使用

3、stack模拟实现

四、queue

1、queue的相关函数

2、queue相关函数使用

3、queue的模拟实现

五、priority_queue

1、priority_queue的相关函数

2、priority_queue的使用

---

一、容器适配器

首先适配器是一种设计模式，是将一个类的接口转化为客户希望的另一个接口

stack和queue没有被划分为容器，而被称为容器适配器，因为stack、queue和priority_queue只是对其他容器的接口进行了包装，stack、queue和priority_queue默认使用deque，如下图所示：

---

二、deque

这里有一个新容器需要介绍，因为接下来说到的stack、queue的第二个参数，即缺省参数都给的是deque

所以需要了解一下这个新容器

1、deque的相关函数

2、关于deque

首先使用deque需要包头文件deque    

大家观察deque的函数可知：

deque相比于vector支持头插头删，而相比于list又支持随机访问，相当于vector与list的合体

所以deque既支持任意位置的插入删除，又支持随机访问

但是deque实际并不是想象中的全能，大家可以想想如果真的这么好，那直接学deque就好了，为什么还要学vector和list呢，具体原因看下面的分析：

---

3、deque的底层实现

deque是双端队列

具体是这种样子：

deque有一个个小数组buffer，每一个小数组存储一部分数据，如果尾插空间满了就在后面再开一个小数组buffer，如果要头插就在前面再开一个小数组buffer

有一个中控的指针数组，每个位置存的都是指针，指向小数组buffer

并且有一个细节，在申请第一个buffer，即上图最中间的小数组时，不是从数组第一个位置申请的，它是从中控指针数组的中间开始申请的，如图所示扩容时，然后后面的buffer的指针的位置在数组中第一个buffer指针位置的后面，前面的buffer的指针的位置在数组中第一个buffer指针的前面

假设每个小数组的buffer是8个空间满，那么头插尾插扩容后应该如下所示的情况：

尤其需要注意的是，头插扩容时，buffer中是从右往左插入数据的

明白了deque是怎么支持任意位置的插入删除，再来看deque是如何支持随机访问的：

比如说，要访问第n个数据该怎么访问呢？

很简单，有两个公式：

(i - 第1个buffer中元素个数) / 8：这个公式算的是该元素在第几个buffer中

( i - 第1个buffer中元素个数) % 8：这个公式算的是该元素在那个buffer中的第几个位置

这便是deque如何支持[]，也就是如何支持随机访问的

4、deque的设计缺陷

①operator[]计算较为复杂，若大量使用，性能下降

②在中间的插入删除效率不高

5、结论

①相比于vector和list，deque非常适合头尾的插入删除，所以deque非常适合做stack、queue的默认适配容器

②中间的插入删除多用list

③随机访问多用vector

---

三、stack

栈满足后进先出的特点，即last-in first-out，LIFO

1、stack的相关函数

2、stack相关函数使用

按顺序插入1,2,3,4，使用push，empty，top，pop函数进行操作，观察图片及打印结果理解用法

stack和queue的使用基本就是这些，剩下结合前面的容器使用也完全能够学会，下面模拟实现具体说明相关知识

3、stack模拟实现

首先我们在自己的命名空间中模拟实现stack

可以观察到stack的模板参数有两个，一个是数据类型T，一个是Container，即是一个容器

也可以看到模拟实现的stack类中的成员是Container _con，即只要满足相关的push、pop、top、empty、size等功能的容器都可以在使用时当模板参数传入

如下即是模拟实现stack的代码：

下面看容器适配器的具体使用：

大家可以看到我们在使用stack时是用的fcy命名空间的，所以测试的内容都是我们自己模拟实现的

可以观察到，平时使用stack时是stack这样使用，而用了容器适配器后，可以选择自己想要的底层容器，这里我们传入了vector，因为vector可以满足stack的基本功能，所以传入vector就可以适配出这里的stack

当然不只有vector满足，list也是满足的，所以这里传入list也是输出结果相同的：

vector和list都能满足stack的基本功能，所以我们都可以传入，我们并不关心传入的是什么容器，只要能适配出stack就可以

而我们都知道，vector和list的底层是不同的，但是都能传入后都能够适配出我们想要的stack，这才叫我们所说的适配器

而我们上面讲的deque就是默认的容器，即我们需要给stack一个默认的容器，这样在我们不传指定的容器时，都默认使用deque适配，即在模板参数部分给一个缺省值

这样我们使用时，就不需要在手动传容器了，即：

---

四、queue

队列满足先进先出的特点，即first-in first-out，FIFO

1、queue的相关函数

2、queue相关函数使用

按顺序插入1,2,3,4，使用push，empty，front，pop函数进行操作，观察图片及打印结果理解用法

---

3、queue的模拟实现

我们在自己的命名空间中模拟实现stack

和stack一样，模板参数有两个，一个是数据类型T，一个是Container，即是一个容器，默认使用deque

只要满足相关的push、pop、back、front、empty、size等功能的容器都可以在使用时当模板参数传入

如下即是模拟实现queue的代码：

下面具体测试在fcy命名空间里模拟实现的queue的功能，默认可以不传容器：

当然我们也可以传入list容器适配queue，即：

这里不能用vector适配，是因为vector并不支持头部的删除，queue是尾部插入头部删除的

---

五、priority_queue

priority_queue叫做优先级队列，底层是一个堆

priority_queue也是一个容器适配器

priority_queue有三个模板参数：

第一个是数据类型

第二个是一个容器，默认用vector适配，因为随机访问比较多

第三个是仿函数，关于排序的函数，默认大堆，可以自己模拟实现一个传入

1、priority_queue的相关函数

2、priority_queue的使用

priority_queue构造函数可以传入迭代器初始化

如下所示，用数组初始化，默认大堆，打印出来是降序：

如果想变成小堆，升序输出，则需要改变仿函数，变为greater，greater包含在头文件functional中

并且如果要自己传入第三个参数仿函数，那第二个参数也是要手动传入的，即：

---

priority_queue的使用也非常简单，如下图就是最常用的四个函数的使用，push、pop、empty、top

通过输出结果可以明白，优先级队列是默认大堆，因为每次取堆顶的数据，然后pop，取出来是最大的

如果想变成小堆，升序输出，则需要改变仿函数，变为greater，greater包含在头文件functional中

并且如果要自己传入第三个参数仿函数，那第二个参数也是要手动传入的，即：