定义
队列（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都指向头节点：
这里写图片描述
入队操作
这里写图片描述
- 将最后一个元素后继指向新元素；
- 将尾指针指向新元素。
出队操作
这里写图片描述
- 将头结点的后继改为后面一位结点；
- 若除头节点外只剩一个元素时，将rear指向头节点。
总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。
更多精彩内容，欢迎关注我的微信公众号——Android机动车
这里写图片描述
网友评论