队列

队列 (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)