stack __ queue(栈和队列)
1. stack的介绍和使用
栈和队列里面都叫容器适配器
存储数据就要交给别的容器
通过封装别的容器，可以进行相应的操作，来达到目的
适配的本质就是复用
这就没有迭代器了，不支持随便遍历
2. queue的介绍和使用
下面用一些题来深入理解
栈的压入、弹出序列_牛客题霸_牛客网
这一题就不能找规律，这样就会陷入死胡同，正确的解法就是我们判断的一样
我们判断就是通过想着一个模拟实现的栈，只要这个栈的top与出栈开头不同就入栈，相同pop
最后看这个栈是否全出了
这里里面用out来判断是否出完（若没出完就入，当入完的时候就是false）
150. 逆波兰表达式求值 - 力扣（LeetCode）
这里涉及到了表达式求解
如正常的一个表达式 2+1*3
这个表达式是前缀表达式，计算机是无法进行运算的，但是后缀表达式就可以
后缀表达式（操作数顺序不变，按优先级进行重排）： 2 1 3 * +
这里就用到了栈
1 取出的元素为为操作数就入栈
2是操作符就取栈顶的两个元素进行计算，计算结果重新入栈
具体的代码实现
这里还要讲一下中缀如何转换成后缀
232. 用栈实现队列 - 力扣（LeetCode）
像这一题，之前c语言做过，但是很麻烦c++就不一样了 不用自己造轮子
思路：就是用两个栈，一个入一个出，当出的为空（但这时候要出数据），就把入的那个栈里面的元素全部都取出来放进去 就行了
代码实现：
102. 二叉树的层序遍历 - 力扣（LeetCode）
这里有两种方法
1：双队列
queue<TreeNode*> nodeQ ---->表示每一层的元素
queue<int> nodelevel ---->表示层数
2 用levelsize 控制一层一层出
思想：因为这里是要一层一层取元素，给的是一个二叉树，能个访问到其根节点
用队列的原因就是先进先出，这样就能有序的访问到（也就是从左到右依次访问）元素，再用levelsize来控制每层是否结束（这样就能把一层元素放到同一个vector里面）
3. priority_queue的介绍和使用
他的底层就是二叉树的堆，优先级的选择就是大堆和小堆
函数模板要传类对象（如sort函数传仿函数的时候），类模板要传参数类型（传仿函数的类型）
215. 数组中的第K个最大元素 - 力扣（LeetCode）
时间复杂度为k*logN
时间复杂度为（N-k）*logK
建堆的时间复杂度为logN （N为数据个数）
如何使用priority_queue
这里传greater<int >这个类类型就会建小堆，其他的就和我们堆的使用一模一样，只是通过仿函数来确立建大堆还是小堆
解下来就是模拟实现priority_queue
仿函数就是一个类
什么是仿函数：仿函数就是类对象可以像函数一样去使用
这就很nb了这个就可以控制向下和向上调整建堆里面建小堆还是大堆（应为用< 和>的时候比较就写死了不能改变 ）现在就是通过对象去控制
注意:对于自定义类型也可以经行比较，因为自定义类型对调用他的比较符号的运算符重载（自定义类型必须要提供）
他是用来替代函数指针
这里就不会像之前我们要建大堆和建小堆还要去重新写向上向下调整！！！
能够控制怎样去比较
完整实现
有些地方也要自己写仿函数
1优先级队列存的是指针
这就会按照指针比较（如果不自己写）这时候重载运算符就不能解决（内置类型不能重载）
比较日期类对象举例
用指针的时候就失效了，因为指针式内置类型比较就会按照地址大小去比较，这时候要自己去写一个（稍微改动一下就可以）
其实我们发现，仿函数真nb
4. 容器适配器
1什么是适配器？
模板变量也可以给缺省值
这里是模拟实现stack
这里是模拟实现queue
queue不能强制适配vector,因为头删效率低
2 deque的简单介绍(了解)
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配 器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，
deque 是一个融合了vector和list 的容器，是一个六边形战士
但是，这个容器在实际用的不多
deque拷贝的代价比较小，说明插入的效率高（deque,是随机迭代器）
但是deque的排序的效率低，虽然支持随机访问，但是还是与vector有差别
vector: 1下标随机访问 2扩容问题 3中间和头部删除效率
list: 1任意位置插入和删除都可以 2按需申请释放 3不支持下表随机访问
那么deque就是两者的融合 一些连续的空间组合到一起
下面就是空间图
相比于vector
极大地缓解了头插头删问题，但是[ ]不够极致，他要计算在哪个buff的第几个
那么operator[]的实现方法为
1，先看在不在第一个buff数组，在就在位置访问
2，不在第一个buff，i-=第一个buff数组的size，第几个buff = i/buffsize,
在这个buff的第几个 = i%buffsize
当有大量的访问的时候，计算量非常大
相比于list
可以自持下标随机访问，cpu高速缓存 ，头尾插入删除都不错，但是中间插入删除就很不好（一个是挪动数据，一个是扩容数组（一般不这样，因为buffsize都是相同的，若改变了，[]的效率会下降））
这就像世界上没有完美的人，可能有一个人各方面都差不都，但是各方面都不突出，不要看到了一个人的优点，但忽视致命的缺点
deque用于：适配stack 和队列的默认容器就很适合
反向迭代器
反向迭代器有两种思路
1让我们来想，list就是
2就是考虑复用，你给一个正向迭代器就适配出一个反向迭代器
但是库里面rbegin 和rend指向的位置与我们想的不同
镜像对称---反向迭代器与正向迭代器的关系