一.相关接口

stack:

queue:

二.适配器模式

这两个类模板利用container类型的成员变量_con,就能将相关容器的接口转换为stack或queue的接口。也就是并不需要从0实现栈和队列，将list,vector...容器拿过来，通过这两个类模板转换，即可实现。

注：container是一个模板参数，可支持不同种类容器。

三.默认容器(container的缺省值)

为啥构造一个栈或队列的对象时，可以只传一个T类型，而不用传container的类型？

原因在于在实现类模板时，已经给了container的缺省值。

从两个图片可以看出，stack的默认适配容器是vector,因为vector的相关接口便于stack接口的转换。

deque对于queue同样如此。决定默认适配容器的，往往是要实现的适配器的底层。

但对于deque这个容器，我们是比较陌生的，让我们来探讨一下它。

四.deque

是一个究极缝合怪(vector和list的缝合)，既有迭代器支持随机访问，还支持头尾删除，也支持“[]"

接口同时囊括vector和list：

此处先让作者提一嘴vector和list的区别(面试重点)

这俩就是一对互补的苦命鸳鸯：

回归deque

底层其实是利用二维数组，先用一个中控指针数组存储每个节点的地址，这里的每一个节点是一个小的数组(buff)。

注意：在每个buff里下标是从0开始的。

五.priority_queue(优先级队列)

相关接口：

底层其实是堆。堆的底层是个数组，因此priority_queue的默认适配容器是vector:

特点：pop和top取优先级高的数据，默认大的数据优先级高。

注：为什么不是deque而是vector?

原因在于两个适配器“[]"的效率问题，deque先天上就是不如queue。而上面pop和top取优先级必然涉及到堆排序，而堆排序必然用到”[]",就要从两个适配器中选择效率高的。

六.仿函数

仿函数就是一个无成员变量的类，它具有一个重载的“()”运算符函数。该函数用于比较形参x和y大小。

可用于控制升降序，使得排序更加灵活。

注意：less是小于，在实现向上调整时，如果parent < child，二者交换，把小的元素向下调，这样调整出的堆就是大堆。根据这样的堆排出的序就是升序。

需自己实现仿函数的情况

问题

1.文件包含顺序

Stack.h被包含以后，编译时该文件的内容就在此处展开，同时会向上寻找相关文件或命名空间，以服务于.h文件内的接口。此时就要格外注意Stack.h和其他文件的上下包含顺序。

eg:

防止向上寻找std找不到。

所以自己写的文件建议包含在命名空间或文件下面，毕竟只会向上寻找。

2.实例化的原则(按需实例化)

类实例化后，用到哪个函数，才会实例化哪个函数。所以有时在写成员函数的时候，即便写错了，但实例化的时候并没有调用这个函数，程序一样能走。所以模板里函数没有完全使用之前，并不能保证语法没有问题。

3.queue的container不能用啥容器？

不能用vector，因为它没有front接口，在实现queue的取top操作时，需要front接口。

4.为何在test文件里明明写using namespace std了，在.h文件里使用swap等标准库里的函数，还要加上std::?