# 6.队列：先进先出线性表实现增删查
# 6-1 主要内容
- 队列是什么
- 队列对于数据的增删查处理
- 队列的一些案例
遵循先进先出的性质的线性表，就是队列
# 6-2 队列是什么
队列是一种特殊的线性表，不同点体现在增和删的操作
队列的特点是先进先出；
- 先进，表示队列的数据新增操作只能在末端进行，不允许在队列的中间某个结点后新增数据
- 先出，队列的数据删除操作只能在始端进行，不允许在中间某个结点删除数据。也就是说，队列的新增和删除操作只能分别在队列的队尾和队头进行
与线性表，栈一样，队列也存在两种存储方式，即顺序队列和链式队列：
- 顺序队列，依赖数组来实现，其中的数据内存中也是顺序存储
- 链式队列，依赖链表实现，其中的数据依赖每个结点的指针互联，在内存中并不是顺序存储。链式队列，实际上就是只能尾进头出的线性表单链表
# 6-3 队列对于数据的增删改查处理
对于一个顺序结构的队列，会设置一个front的指针指向队头，并设置另一个rear指针指向队尾，当我们不停进行插入删除操作时，头尾指针都会不断向后移动
为了实现有k个元素的顺序存储的队列，我们需要建一个长度比k大的数组，以便把所有的队列元素存储在数组中。
队列新增时，利用rear指针在队尾新增一个数据元素，这个过程不会影响其他数据，时间复杂度为O(1)
队列删除数据时，队列出口在队列头部，队列中剩余的元素都需要向前移动一个位置，此时时间复杂度为O(n)
利用顺序队列，持续新增和删除数据，会出现数组越界问题，但下标为0的地方为空闲，这就出现了‘假溢出’现象，解决办法：
- 不惜消耗O(n)的时间复杂度去移动数据
- 或者开辟足够大的内存空间确保数据不会越界
# 6-4 循环队列的数据操作
以上两个方法都不太友好，其实数组越界的问题可以通过队列的一种特殊变种来解决，叫做循环队列
# 6-4-1 循环队列新增
- 循环队列进行新增数据元素时，首先判断队列是否为满
- 如果不满，则可以将新元素赋值给队尾，然后让rear移动一个位置
- 如果已经排队到队列最后位置，则rear指针重新指向头部
# 6-4-2 循环队列删除
- 首先判断队列是否为空，不为空时，然后将队头元素赋值给返回值，front指针向后移动一个位置
- 如果已经排到队列最后位置了，就把front指针重新指向头部(钟表过了12点重新指回1)
- 这样就可以不开辟大量储存空间的前提下，不采用O(n)的操作，也能通过移动数据完成频繁删除新增
此时会出现另一个问题，但队列为空时，front和rear指针相等，但队列是满的时候，front和rear的指针也相等，
那怎么区分，是空队列还是满队列呢？常用的方法就是，设置一个flag来区别队列是满还是空
# 6-5 链式队列的数据操作
链式队列就是一个单链表，同时增加了front指针和rear指针，链式队列和单链表一样，通常会增加一个头结点，并另front指向头结点，头结点不用来存储数据，
主要用来辅助标示
- 链式队列新增时，将拥有数值X的新结点s赋值给原队尾结点的后继，即rear.next,然后把当前的s设置为队尾结点，指针rear指向s
- 链式队列进行删除时，实际删除的是头结点的后继结点，接着让头结点指向要删除结点的后继结点
如果链表除去头结点外剩下一个元素，那么删除仅剩下的一个元素后，reae指针就变成野指针了，此时要将rea指向头结点
这样做主要就是为了防止删除删除最后一个有效数据结点后，front指针和rear指针变成野指针，导致队列没有意义。有了
头结点，哪怕队列空了，头结点依然存在，能让front和rear指针依然有意义
- 队列的查找操作，不管是顺序还是链式，队列都么有额外改变，它需要遍历整个队列完成数值查找，时间复杂度为O(n)
# 6-6 队列的案例
下面是一个约瑟夫环的问题，问题具体描述如下：
已知n个人（1，2，3...n）围坐在一个圆桌，从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始数，数到m的人又出列，以此循环，直到所有人出列 ,这个问题输入变量就是n和m，输出的就是n个人出现的顺序
- 1.先把所有人都放到循环队列中，注意循环队列的长度要大于或等于n
- 2.从第一个人开始依次出队列，出队列一次计数变量i 自增
- 3.直到i等于m的人出队列时，就不再让这个进队列了，而是放入一个用来记录出队列的顺序
- 4.直到n个人为止，但队列为空时，则标示队列中的n个人都出列了，这时结束队列循环，输出数组记录的元素
# 6-7 总结
- 队列与栈的特性很相似，继承了线性表的优点和不足，是加了限制条件的线性表，增在队尾，删在队头
- 时间复杂度，新增删除都是O(1),查找是O(n);
- 空间性能上，循环队列必须有一个固定长度，因此会有存储数量和空间的浪费；链式队列不存在这个问题，所以更灵活
- 在实际问题中，如果是已知长度，建议用循环队列；无法确定长度时，建议使用链式队列
- 队列具有先进先出的特点，很像买彩票排队场景，在面对数据处理顺序非常敏感问题时，队列是一个不错的技术选型