队列相关知识点较为简单易懂，不再叙述。（注意【FIFO】特点，框架遗漏）
本文主要针对考点中的2、3点进行知识总结，以及知识框图中遗漏的一个小考点【求队列的长度】，参考资料《王道数据结构》及《数据结构》严蔚敏版。
分析：根据队列“队头删除、队尾插入”易知，必需要有队头和队尾的指针（头指针和尾指针）。链队列的操作可以看作是单链表的插入和删除的特殊情况：只需要更改头指针或尾指针。由此，我们所用的链表必须是可以直接拿到队首和队尾的结点的指针。
应用：
Q1:最适合用作链队的链表是（）
A、带队首指针和队尾指针的循环单链表
B、带队首指针和队尾指针的非循环单链表
C、只带队首指针的非循环单链表
D、只带队首指针的循环单链表
A1: 选择：B
队列需要在两端进行，需要能直接拿到队首和队尾指针，所以可以首先排除C和D。
选项A，循环单链表双向，在进队出队需要修改指针，使其回到原本的循环，可以实现队列的操作，但是很麻烦，“画蛇添足”。
选项B，可以在头删除、尾插入，符合
Ｑ2：最不适合用作链式队列的链表是（）
A、只带队首指针的非循环单链表
B、只带队首指针的循环双链表
C、只带队尾指针的循环单链表
D、只带队尾指针的循环单链表
A2: 选择：A
A项中，只带队首指针，如果要在队尾进行操作的话需要遍历单链表。显然不适合两端操作的队列。
分析：类比栈的操作，可以知道，如果指针指向当前，那么就应该先移指针再入值（如图1）；如果当前所指是上一个（后一个），那么可以先入值再移指针（如图2）。
由此我们类比到队列中，若初始时font=0，rear=n-1，则入队时应该先队尾指针后入值。基于如上，便于我们判断队列的空/满。
如图，为顺序存储时队空和队满的情况
由图易知，当rear= =front= =0时队空，但是队满情况需要注意，当rear达到maxsize时，不一定队满（如图中第三个），这就导致一种“假溢出”，为此，我们想到采用循环的方式进行判满。
图中所示是采用牺牲一个单元来区分队空和队满的方法：
队空：rear= =front
队满：队头指针在队尾指针的下一位置（rear+1）%maxsize= =front。
倘若不空出一个，队空和队满的都是rear= =front，为区分是队空导致的rear= =front，还是队满，有以下两种办法：
1、借助一个变量length，来记录此时队列的长度，length= =0，显然是队空
2、增设一个tag数据成员，若执行入队，tag=1；若执行出队，tag=0
注意，若初始front=0，rear=maxsize-1， 那么判空条件应该是**（rear+1）%maxsize= = front**
链式队列分有带头和不带头两种，不带头结点判空显然是front= =null。带头结点如图，其判空条件应为front==rearl
链式队列适合数据元素变动比较大的情形，而且不存在队列满且溢出的问题。
*Ｑ1:*假设一个循环队列Q[MaxSize]的队头指针为front，队尾指针为rear，队列的最大容量为Maxsize，此外，该队列没有其他数据成员，则判断该队列的队满条件是________
*A1:*没有其他数据成员说明采用“牺牲一个单元”方法，队满条件，队头在队尾指针的下一个位置，故答案为：
Q.front= =(Q.rear+1)%MaxSize
Q2:循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。
则其队空条件为：________________
队满条件为________________
*Ａ2:*队空显然是end1= =end2
因为最多容纳M-1个元素，故队满时，队头下标为0，队尾下标为M-2，end1指向队头，end2指向队尾的后一个位置。推出队满条件为：end1= =（end2+1）mod M
Q3： 循环队列的队头和队尾指针分别是front、rear，约定队头指针指示队列中队头元素的当前位置，队尾指针指示队列中队尾元素的当前位置的下一位置，容量为MAXSIZE的队列满的条件是（rear +1）%MAXSIZE = = front，则判断队列为空的条件是__________
A3: rear = = front
Ｑ1:【武汉大学·2011·计算机基础】设环形队列中数组的下标是0～N-1，其头尾指针分别是f和r（其中f指向队头元素的前一个位置，r指向队尾元素的位置），则其元素的个数为__________
插入一个元素，rear就会顺时针移动一位
删除一个元素，front就会顺时针移动一位
由此可推断元素个数为：（r-f+N）%N
Q2:【湖南大学·2006·数据结构】单循环链表表示的队列长度为n，若只设头指针，则进队的时间复杂度为__________
队列的特点：先进先出
单链表的特点：迭代的时候向前，不能回头
在只知道头指针的情况下，入队，要先遍历单链表，找到尾指针，然后进行插入，遍历过程时间复杂度为O（n）。故答案为O（n）
Q3:【武汉大学·2015·计算机基础】设有顺序数组（最大容量为maxsize）存储某循环队列Q，用front（队首元素的下标）与count（队列中元素个数）来标记该队列，假设当前count<maxsize，则以下语句可以完成新元素e入队的操作为__________
答案：
Q->data[Q->front+Q->count)%maxsize]=e;
Q->count++;
由于是循环队列，所以在插入数据的时候需要%maxsize，count需要加1
Q4:若用一个不带头结点的循环单链表表示队列，则最好用_____标识链队
A、首结点指针
B、尾结点指针
C、首结点和尾结点两个指针
D、任何结点指针
答案：B
非循环单链表和带头指针的循环单链表查找尾结点的时间效率是O（n）【这点在链表题目中也总是变相考察】，而带尾指针的循环链表查找首尾结点的时间效率是O（1），查找和更改时只需要修改指针，无需遍历，队列的操作实际上就是对链表首尾结点的操作。
【下次再更～】
