数据结构学习笔记——队列

定义

队列（Queue）：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。

如下图所示：

循环队列

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。

队列顺序存储的不足

假设有一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此世家复杂度为O(1)。

与栈不同的是，队列元素的出队是在队头，即下标为0的位置，也就意味着，队列中的所有元素都得向前移动，也就是下标为0的位置不为空，时间复杂度为O(n).

它们的具体实现和线性表的顺序存储结构是一样的，不再累赘。

但是

如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加，如图

为了避免只有一个元素时，队头和队尾重合使得处理变得麻烦，就引入两个指针，front指向队头元素，rear指向队尾元素的下一个位置，这样当front等于rear时，表示空队列。

这样又出现一个问题，如果队尾已有元素，再插入新元素时rear指向哪里？而且，当队列中只有队尾有元素时，向后再加，就会产生数组越界错误，可实际上之前的位置可能有空，我们把这种现象叫做假溢出。

循环队列定义

解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

下标2、3、4位置已有元素，在插入新元素，则存放下标为0的位置。如图：

但之前约定当front==rear时，表示队列为空，上述方法中front==rear时还表示队列已满，怎么处理呢？

我们要求，队列满时，数组中还有一个空闲单元，如图：

得出以下公式：

• 队列满 的条件（rear+1）%QueueSize==front
• 队列长度公式：（rear-front+QueueSize）%QueueSize

队列的链式存储

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们简称为链队列。

空队列时，front和rear都指向头节点：

入队操作

1. 将最后一个元素后继指向新元素；
2. 将尾指针指向新元素。

出队操作

1. 将头结点的后继改为后面一位结点；
2. 若除头节点外只剩一个元素时，将rear指向头节点。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。