[数据结构与算法]数据结构解析-队列

队列是一种特殊的线性表，那么他的特殊之地就在于他只允许在表的前端(front)进行删除操作，在表的后端(rear)进行插入操作，和栈一样，队列是一种受操作限制的线性表。进行插入操作的端称为队尾，进行删除操作的称为队头

队列-简介

? ? ? ?队列是一种特殊的线性表，进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
? ? ? ?队列数据元素又称之为队列元素。在队列中插入一个队列元素称之为入队，从队列中删除一个元素称之为出队，因为队列只能允许从一端删除，从另外一端插入，所以，只有在最进入队列的元素才可以在先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

顺序队列

? ? ? ?建立顺序队列结构的前提就是为其静态或者动态的申请一片连续的存储空间，并放置俩个指针进行管理。一个是队头指针front，另外一个队尾指针rear，他指向下一个元素入队的储存位置。如下图所示：

? ? ? ?每次在队尾插入一个元素rear增加1；每次在队头增加一个元素的时候，front增加1，随着插入和删除操作的，队列元素个数不断的变化，队列所占的储存空间也在队列结构所分配的连续空间中移动。当front=rear，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列在无法插入新元素，但在这个时候往往还有大量的可用空间未被占用，这些空间是已经出队的队列元素曾今占用的存储单元。

溢出现象

下溢现象

下溢现象：指的是一个超长的数据进入到缓冲区时，超出部分被写入下级缓冲区，下级缓冲区存放的是下一条指令的指针，或者是其他程序的输出内容。下溢会导致下一个命令执行不正常。

? ? ? ?当队列为空的时候，做队运算产生的溢出现象。下溢是正常现象，常用来做程序控制转移的条件。

真上溢现象

上溢现象：当一个超长的数据进入到缓冲区时，超出部分被写入上级缓冲区，上级缓冲区存放的可能是数据、上一条指令的指针，或者是其他程序的输出内容，这些内容都被覆盖或者破坏掉。可见一小部分数据或者一套指令的溢出就可能导致一个程序或者操作系统崩溃。

? ? ? ?真上溢现象：当队列满时，做队列进栈运算产生的空间溢出的现象，这种状态是一种出错状态，应该避免。

假上溢现象

? ? ? ?由于入队和出队操作，头指针指增加不减少，致使被删除元素的空间永远无法被利用，当队列中实际元素个数远远小于向量空间的规模时，也有可能超越向量空间的上界而不能做入队操作，那么这种现象就称之为“假上溢”现象

循环队列

? ? ? ?在实际使用队列时，为了使得队列空间能够重复使用，往往对队列的使用方式进行微调。无论插入或者删除，一旦rear指针增加·1·或者front 指针增加·1·的时候超出了分管的队列空间，那么他所在的这一块内存会将指针重制，那么实现这一个重置的方法可以用rear%MaxSize这种取余的方法来实现。那么说白了，这种方式其实就是把队列空间想象成一个环形空间结构，那么中间环形所包含的内存空间就可以重复使用。正常来说，真正实用的队列其实就是循环队列。

$注意事项$

? ? ? ?在循环队列中，当队列为空的时候，那么就会出现front=rear,当然根据上述描述，当所有的队列全占满的，也会出现front=rear。
? ? ? ?为了区别这俩种情况，试想一下如果说我们每次留一个空位出来，告诉队列说：“这是警戒线，请勿靠近！！！”，然后在这里拉起警报线，那么在面对元素全满的情况时将会很好的和队列为空的情况区别出来。

队列的数组实现

? ? ? ?在队列的运算中需设两个指针：head，队头指针:指向实际队头元素；tail，队尾指针，指向实际队尾元素的下一个位置。在一般情况下，两个指针的初值设为0，这时队列为空。
? ? ? ?定义一个数组A[1…5]。Q(i) i=3,4。头指针head=2，尾指针tail=4。队列中拥有的元素个数为:L=tail-head。现要让排头的元素出队，则需将头指针加1。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q(5)入队。当队尾已经处理在最上面时，即tail=5，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。

? ? ? ?解决假溢出的方法有俩种：一种是将所有元素下标变更，显然这种方式比较麻烦，另外一种就是我上面讲解的循环队列