【队列概念】

只允许在表的一端进行插入，而在表的另一端进行删除。四个字：“先进先出”

向队列中插入元素称为入队，从队列中删除元素称为出队。

提示：简单队列可能存在假溢出或假满的问题。

 【栈队列对比】

1、栈（堆栈）：后进先出表

栈是一种特殊的表，这种表只能在 表首（栈顶）进行删除操作和插入操作

2、队列：先进先出表

队列是一种特殊的表，这种表只能在 表尾 进行插入，表首 进行删除

【循环队列】

为了解决假溢出或假满这一问题，一般将顺序队列组成循环队列

 空队状态：front=rear；

入队：①queue[rear]=A；②rear=(rear+1)%Maxsize；

满队状态：(rear+1)%Maxsize=front；

出队：①e=queue[front]；②front=(front+1)%Maxsize；

【循环队列—课堂习题】

例1、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（  A  ）

A.（rear-front+m）%m      B.rear-front+1     C.（front-rear+m）%m       D.（rear-front）%m

例2、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（  B  ）

A.1和5                               B.2和4                 C.4和2                                D.5和1

解析：头front：3，尾rear：0，队列在表首进行删除元素即front：（front+1）%6=4，队列在表尾进行插入元素即rear：（rear+2）%6=2，则rear和front分别为2和4。

【双端队列】

双端队列：指允许两端都可以进行入队和出队操作的队列（不受限）

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

输入受限的双端队列：允许在一段进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。

【经典例题】若以1234作为双端队列的输入序列，既不能由输出受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（ B ）

A.4213                      B.4231                      C.4132                      D.1234

【链队】

实际上是一个同时带有队头指针和队尾指针的单链表

空队：front=NULL；rear=NULL;

满队：不存在滴

入队：①rear->next=p；②rear=rear->next；

出队：①e=front->data；②front=front->next；

【链队—课堂习题】

例1、若用单链表来表示队列，则应该选用（ B ）

A.带尾指针的非循环链表                                   B.带尾指针的循环链表

C.带头指针的非循环链表                                   D.带头指针的循环链表

例2、判定“带头结点的链队列为空”的条件是（ C ）

A.Q.front==NULL                                               B.Q.rear==NULL

C.Q.front==Q.rear                                              D.Q.front!=Q.rear

解析：当带头结点的链队为空时,只有一个头结点,头尾指针均指向头结点，因此有Q.front==Q.rear

【循环队列和链式队列的比较】

（1）时间性能比较：

循环队列与链式队列基本操作的算法都需要常数时间O（1）

循环队列是事先申请好空间，使用期间不释放

链式队列是每次申请和释放结点，也会存在一些时间开销

如果入队出队频繁，则两者还是有细微差异。

（2）空间性能比较

循环队列必须由一个固定的长度，所以就有了存储元素个数和空间的浪费