c++:stack与deque

1.stack使用

1.1empty

作用：判断栈中是否为空

我们看到这里s1初始化的时候是空初始化，所以用empty来判断出的就是空的栈

1.2size

size的作用就是判断栈中的数据个数

1.3push

与vector,string,list不同的是,stack中没有头插尾插的概念

因为栈有一个原则：后进先出。也就是他像杯子装水一样限制了我们只能从唯一接口进行数据插入与删除。所以也就自然没有push_back了，只有push

通过push，我们成功给栈插入了一个1

1.4pop

在pop前，栈中有一个1

pop之后栈中的1被删掉了

1.5top

我们按照顺序将1,2,3,4依次插入栈中，也就是说4应该是最后进栈的，他就是栈顶数据

2.容器适配器

 适配器：是一种设计模式，他的目的是将一个接口转换成客户希望的另一个接口

容器适配器：就是将一个容器转换成另外一种容器

eg：vector/list -> stack

（1）只支持一种容器的写法

这里是使用数组实现栈，由于底层锁死了vector，所以要改成链表实现栈就很麻烦了，底层的都要改动

（2）支持多种容器的写法

这里面我们就可以将其他各种容器给到模板参数container，达到可以切换多种容器的目的

eg： m_stack<int,list<int>>

3.利用容器适配器实现stack

这里我们直接复用大部分容器中都有的方法来实现栈

 注意：函数参数和模板参数是类似的，只不过函数参数传的是值，而模板参数传的是类型

所以我们的其中一种使用就是:my_stack<int, vector<int>> m；

不过我们其实需要给container一个默认容器类型，就像给函数参数一个缺省值一样。

4.deque 

标准库中的栈默认的容器既不是数组，也不是链表，而是用deque。

vector：

优势：可以实现数据的随机高效访问

劣势：插入删除效率较低，扩容会有一定空间浪费

list：

优势：可以实现高效的随机存储，没有空间浪费

劣势：不支持下标随机访问

deque结合了数组随机读取的优势和链表插入删除方便的优势，但是也带来了一些新的问题

当只需要查找和头尾数据操作的时候，deque是可以完美替代vector与list的，除了这种情况，deque就会比较麻烦了

示意图：

vector是一段连续的长空间，存储所有数据

list是一个个断开的空间，存储一个个数据

deque是由中控数组与存储数组组成的，中控数组存储着存储数组的指针，负责从一个存储数组跳到另一个存储数组访问，存储数组是一大段连续空间存储数据，且存储数组的长度是一样的

接下来看看他的迭代器

迭代器由四个指针组成，其中三个是一级指针，一个是二级指针。

cur指向当前访问到的数据，first指向存储数组的首元素位置，last指向存储数组的尾元素位置

node指向中控数组中指向当前存储数组的指针

下面是更完整的结构

由于deque的应用场景是头尾的插入删除，所以这里主要有两个迭代器，分别是start与finish，他们分别是指向中控数组的第一个元素的指针，与最后一个元素的指针

（1）遍历

从first的cur开始遍历，不涉及存储数组转换就是cur++，涉及存储数组变化就改变node指针的指向，然后根据node指针取得first指针的地址并更新cur，再根据存储数组固定的元素个数推断出last的指针地址，这样就完成了迭代器的更新。

（2）尾部插入数据

数据没满：直接插入数据并cur++

数据满了：开一个新的存储数组，将数据存在新数组开头，更新finish迭代器

（3）头部插入数据

存储数组满了：开一个新的数组，把数据存在新数组的结尾，更新start迭代器

存储数组没满：直接插入，然后cur--

（4）下标随机访问

i/size求出在第几个存储数组，i%size求出在存储数组的第几个位置

---

插入与删除：

他们需要把pos后面的数据跨存储数组移动，效率很低

下标随机访问：

略低于vector

头尾插入删除：
优于vector和list

排序：

用vector

5.priority_queue

priority_queue是优先级队列，他的底层是利用堆来实现的，默认大数据优先级更高。

5.1框架搭建

我们还是使用容器适配器来构建该容器

5.2插入

由于底层是堆，所以我们的插入是先直接插入到堆尾，然后向上调整，最后完成一个堆结构插入

5.3删除 

堆的删除：先把首尾元素值交换，然后删除尾元素，接着向下调整

向下调整用到了假设法：我们先假设左孩子是较大的，然后进行判断，若实际上右孩子更大，则让child++。不过要注意，进行右孩子的访问前，需要确定有右孩子

5.4仿函数使用

 我们前面实现的插入删除都是针对大堆的（大数据优先级高的），那如果我们要针对小堆，怎么实现？

方法一：在类中直接修改代码比较逻辑

方法二：使用仿函数

方法一的修改需要改动底层，且不适合做成模板，方法二可以写成模板，改动比较逻辑可以从接口处改动，不用动底层

接下来我们实现lessfuc仿函数

其实仿函数就是一个类中重载()运算符，然后在这个重载函数中实现函数的功能

由于lessfuc是大的数据优先级高，所以我们需要注意向上和向下调整中parent和child数据的位置

这里把parent的数据放在child之前，若parent<child，则交换数据，满足大数据优先

---

这里再讲解一个仿函数的应用

假设我们有一个date类，我们的比较逻辑是指针直接比较，但是我们希望的是指针指向的内容大小比较，我们就可以写一个仿函数，重载（）运算符，实现指向内容的比较，然后传仿函数给date类

综上：仿函数可以增加一些代码的可变性，通过传不同的仿函数实现一个类兼容多种情况