part 6 队列
1 定义
1.1 现象
示例1：
窗口排队
示例2：
（多道程序运行时）
电脑处于疑似死机的状态，鼠标点什么似乎都没有用，双击任何快捷方式都不动弹。就当你失去耐心，打算重启时，突然它像酒醒了一样，把你刚才点击的所有操作 全部按照顺序执行了一遍。
这是因为操作系统中的多个程序需要通过一个通道输出，而按先后次序排队等待造成的。
示例3：
比如像移动、联通、电信等客服电话，客服人员相比用户总是少数。在所有的客服人员都占线的情况下，客户会被要求等待，直到某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理
1.2 原理
先进先出（FIFO）
1.2 定义
队列是只允许在一端进行插入操作，而在另一端进行删除的线性表
允许插入的一端称为队尾
允许删除的一端称为队头
2 队列的顺序表示——循环队列
2.1 类型定义
假设一个队列有n个元素，顺序存储的队列需要建立大小为N(N>=n)的数组，并把队列的所有元素储存在数组 的前n个单元，
数组下标为0的一端即是队头，数组下标为n的一端是队尾
2.2 空列
front == rear
2.3 入列
在队尾追加一个元素，不需要移动任何元素，时间复杂度为O(1)
rear++;(指向下一个待操作空间)
2.4 出列
2.4.1 问题1：
在队头，队列中所有的元素都得向前移动，保证队头（下标为0的位置）不为空，此时时间复杂度为O(n)
助解：一队人排队买票，前面的人买好离开，后面的人就要全部向前一步，补上空位
解决方案：
如果不限制队列的元素必须存储在数组的前n个，也就是队头不需要一定在下标为0的位置，出列后不移动元素，只修改指针那么出列性能就会增加
2.4.2 问题2：
假溢出：队列在下标为0,下标为1的位置空闲，数组末尾元素已经占用，再向后加，数组发生越界错粗的现象
示例：公交车后排全部坐满，只剩前排有空位
2.4.3 循环队列
解决假溢出的办法，头尾相接。
循环队列：我们将队列的这种头尾相接的顺序存储结构称为循环队列
2.4.4 问题3：
循环队列如何判空还是满？
满列： front=rear
空列： front=rear
满队：
空队：
解决办法
办法1：设置标签flag
空列：flag=0
满列：flag=1
办法2：预留n+1的空间，存n个元素
2.4.5 问题4 ：如何判满？
rear可能比front大，也可能比front小。可能只差1，也可能差整整一圈
情景一：顺时针方向，front=0 ,rear=n-1
（rear+1）%N=front
情景二：顺时针方向 rear=0 top=1
rear+1=front
情景三：rear+1=front
小结：
判满： (rear+1)%N=front
2.5 队列长度
2.5.1 情境一：rear>front :
队列长度:rear-front
2.5.2 情境2：rear< front
队列长度：左边数量+右边数量
(rear-0) +(N-front)
2.5.3 小结
rear>front :队列长度:rear-front
rear<front :队列长度rear-0 + queue_size-front
(rear-front +queue_size)
综上：
(rear-front +queue_size)%queue_size
参考代码：
2.6空队列的初始化
2.7 入列
2.7.1 算法步骤：
（1）判断队列是否满，若满则返回ERROR
（2）将新元素插入队尾
（3）队尾指针+1
2.7.2 参考代码
2.8 出列
2.8.1 算法步骤
（1）判断队列是否为空，若空则返回error
（2）保存队头元素
（3）队头指针+1
2.8.2 参考代码
3 队列的链式存储
尾进头出的线性链表
3.1 逻辑示意图
3.2 类型定义
结点定义
链队结构定义
3.3 链队的初始化
算法描述
（1）生成新的结点作为头结点，队头队尾指针指向此结点
（2）头结点的指针域置空
3.4 入队
3.4.1 算法描述：
（1）为入队元素分配结点空间，用指针p指向
（2）将新节点数据域置为e
（3）将新节点插入到队尾
（4）修改队尾指针为p
3.4.2 逻辑示意图
3.4.3 参考代码
3.5 出队
3.5.1 算法步骤
（1）判断队列是否为空，若空则返回ERROR
（2）临时保存队头元素的空间以备释放
（3）修改头结点的指针域，指向下一个结点
（4）判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点
（5）释放原队头元素的空间
3.5.2 逻辑示意图
3.5.3 参考代码
3.5.4 运行结果
入列：1 2 3 4 5 // 出栈：1 2 3 4 5 （先进先出）
3.6 小结
在可以确定队列长度最大值的情况下，建议使用循环队列
无法预估队列的长度时，则用链队列
4 总结回顾
栈和队列都是特殊的线性表。只不过对插入和删除操作做了限制。
栈是仅在表尾进行插入删除操作的线性表
队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表。
对于栈来说，如果是两个数据类型相同的栈，则可以用数组的两端做栈底的方法来让两个栈共享数据，最大化利用数组空间
对于队列来说，为了避免数组插入和删除时需要移动数据，于是引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得插入删除的时间复杂度从O(N)变成O(1)
他们都可以通过链式存储结构来实现，实现原则上与线性表基本相同
5 球钟问题
问题描述:球钟是利用球的移动来记录时间的装置（吐槽：这么麻烦，球会准时放进去？）。
它有三个可以容纳若干个球的容器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，5分钟指示器中有3个球，小时指示器中有4个球，则时间为4:17。
每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。在放进去第五个球的时候，分钟指示器内的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。（先进后出：栈）
而第五个球就会进入五分钟指示器（五进制）。
按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球（12进制）。因此，该球种表示的时间范围是从00:00到11:59
1、要想表示00:00到12：00最少需要多少个球? 2、假设，指示器都为空，球队列需要多长时间能回到原来的状态? 即从初始球队列中球的顺序，经过球的循环后球队列中的球再次与初始顺序相同。
算法：
（1）指示器：栈（先进后出）
分钟：5
5分钟：12
小时：12
（2）数据：球的编号（链队）
5.1 球的编号
（1）空链队
（2）入队
（3）出队
5.2 栈（动态分配）
（1）空栈（顺序）
（2）入栈
（3）出栈
5.3 评判规则
5.4 主函数调用