数据结构与开发应用之队列

队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出线性表。

理解队列

队列和栈非常类似，但是使用了不同的原则，而非后进先出。在现实中，最常见的队列的例子就是排队：

在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档。

队列通常可分为：

• 顺序队列
• 循环队列

顺序队列

使用顺序存储结构的队列称为顺序队列。如下图：

顺序队列中的溢出现象：

• “下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
• “真上溢”现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
• “假上溢”现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

循环队列

循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。即将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。结构如下图所示：

队列的基本实现

创建一个队列，首先需要一个用于存储队列中元素的数据结构。我们可以使用数组实现一个 Queue 类：

class Queue {
  constructor () {
    this.items = []
  }

  push (...elems) {
    this.items = [...this.items, ...elems]
  }

  shift () {
    return this.items.shift()
  }

  get (index = 0) {
    return this.items[index]
  }

  isEmpty () {
    return this.items.length === 0
  }

  size () {
    return this.items.length
  }

  clear () {
    this.items = []
  }
}

其中：

• push：向队列尾部添加一个（或多个）新的项。
• shift：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
• get：访问队列元素。
• isEmpty：如果队列中不包含任何元素，返回 true ，否则返回 false 。
• size：返回队列包含的元素个数，与数组的 length 属性类似。
• clear：清空队列。