循环队列：图解及基本操作时间复杂度

1.基本概念

队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。它是一种基于先进先出（First In First Out，简称FIFO）策略的集合类型。允许插入的一端称为队尾，允许删除的一端称为队头。

同样的，队列具有两种存储方式：顺序存储和链式存储。

2.队列的顺序存储结构

其存储结构如图图9-15所示：

图9-15　队列的顺序存储

与栈不同的是，队列元素的出列是在队头，即下表为0的位置。为保证队头不为空，每次出队后队列中的所有元素都得向前移动，此时时间复杂度为O（n）。此时队列的实现和线性表的顺序存储结构完全相同。

若不限制队列的元素必须存储在数组的前n个单元，出队的性能就能大大提高。但这种结构可能产生「假溢出」现象，即数组末尾元素已被占用，如果继续向后就会产生下标越界，而前面为空。如图9-16所示：

图9-16　队列的假溢出

解决「假溢出」的办法就是若数组未满，但后面满了，就从头开始入队。我们把这种逻辑上首尾相连的顺序存储结构称为循环队列。(www.xing528.com)

数组实现队列的过程如图9-17所示：

图9-17　队列的数组实现过程

假设开始时数组长度为5，如图，当f入队时，此时数组末尾元素已被占用，如果继续向后就会产生下标越界，但此时数组未满，将从头开始入队。当数组满（h入队）时，将数组的长度加倍。

3.队列的链式存储结构

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

存储结构如图9-18所示：

图9-18　队列的链式存储

循环队列与链队列，它们的基本操作的时间复杂度都为O（1）。和线性表相同，在可以确定队列长度的情况下，建议使用循环队列；无法确定队列长度时使用链队列。