队列

队列 (Queue) 也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。

1. 顺序队列：顺序存储结构。当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头前一个位置，而尾指针始终指向队尾元素的实际位置
2. 循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加 1，朝前移动。只不过当头尾指针指向向量上界（MaxSize-1）时，其加 1 操作的结果是指向向量的下界 0。除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相等。因此，我们无法通过 front=rear 来判断队列 “空” 还是“满”
3. 链队列：链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。

4. 设尾指针的循环链表表示队列, 则入队和出队算法的时间复杂度均为 O(1)。用循环链表表示队列，必定有链表的头结点，入队操作在链表尾插入，直接插入在尾指针指向的节点后面，时间复杂度是常数级的；出队操作在链表表头进行，也就是删除表头指向的节点，时间复杂度也是常数级的。

5. 队空条件：rear==front，但是一般需要引入新的标记来说明栈满还是栈空，比如每个位置布尔值

6. 队满条件：(rear+1) % QueueSize==front，其中 QueueSize 为循环队列的最大长度
7. 计算队列长度：（rear-front+QueueSize）% QueueSize
8. 入队：（rear+1）% QueueSize
9. 出队：（front+1）% QueueSize
10. 假设以数组 A[N] 为容量存放循环队列的元素, 其头指针是 front, 当前队列有 X 个元素, 则队列的尾指针值为 (front+X mod N)