队列的顺序存储

非循环队列

这种队列有一个问题：如下图 (c) 和 (d) 所示，数组并没有满，但是队列已满，无法再执行「入队」操作。这叫做「伪溢出」。
image.png

循环队列

循环队列是基于顺序存储来实现的，可以通过「取余运算」实现指针从尾部到首部。
循环队列有一个问题：需要用额外的信息来说明当前是满队列还是空队列。

区别空队列和满队列的一种方法：front 指向队列的头部元素；rear 指向队尾元素的下一个位置

  • 判断队列为空：rear == front
  • 判断队列为满：(rear + 1) % MaxSize == front
  • 计算队列的长度：(MaxSize + rear - front) % MaxSize

image.png

注：进行入队操作时，front 不动，rear 增加，所以可以有 rear 的数组下标大于 front 的映像。
image.png

队列的链式存储

通过单链表实现时，使用「头指针」表示「队首」，使用尾指针表示「队尾」
在链表的尾部进行入队操作，在链表的头部进行出队操作。
为了操作方便，通常会设置一个空的「头节点」
image.png

双端队列

两边都可以输入和输出
image.png

还有输入首先或者输出受限的情形
image.png
image.png

如果规定从哪端输入的元素只能由哪端输出，那么就退化为两个栈底相接的栈。