如何理解“队列”？

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。所以，队列跟栈一样，也是一种操作受限的线性表数据结构。

顺序队列和链式队列

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

  1. class {
  2.      constructor(n) {
  3.       this.items = new Array(n);
  4.     this.head = 0;
  5.     this.tail = 0;
  6.     this.n = n;
  7.   }
  8.   enqueue(item) {
  9.     this.items[this.tail] = item;
  10.     ++this.tail;  
  11.     return true;
  12.   }
  14.   dequeue() {
  15.       if (this.head == this.tail) return null;
  16.     let ret = this.items[this.head];
  17.     ++this.head;
  18.     return ret
  19.   }
  20. }

对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

你可以结合下面这张图来理解。当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。

5c0ec42eb797e8a7d48c9dbe89dc93cb.webp

当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。

dea27f2c505dd8d0b6b86e262d03430d.webp

你肯定已经发现了，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。这个问题该如何解决呢？

每次进行出队操作都相当于删除数组下标为 0 的数据，要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。能不能优化一下呢？

实际上，我们在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue() 保持不变，我们稍加改造一下入队函数 enqueue() 的实现，就可以轻松解决刚才的问题了。下面是具体的代码：

  1. class {
  2.     enqueue(item) {
  3.             if (this.tail === this.n) {
  4.           if (this.head === 0) return false;
  5.         for (let i = this.head; i < this.tail; ++i) {
  6.           this.items[i-this.head] = this.items[i];
  7.         }
  8.         this.tail -= this.head;
  9.         head = 0;
  10.       }
  11.     this.items[this.tail] = this.item;
  12.     ++this.tail;
  13.     return true;
  14.     }
  15. }

从代码中我们看到，当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。

094ba7722eeec46ead58b40c097353c7.webp

接下来，我们再来看下基于链表的队列实现方法。

基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。

c916fe2212f8f543ddf539296444d393.webp

循环队列

我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？我们来看看循环队列的解决思路。

循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

58ba37bb4102b87d66dffe7148b0f990.webp

我们可以发现，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

71a41effb54ccea9dd463bde1b6abe80.webp

在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？

3d81a44f8c42b3ceee55605f9aeedcec.webp

就像图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。

图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

  1. class CircularQueue {
  2.     constructor(n) {
  3.     this.items = new Array(n);
  4.     this.n = n;
  5.     this.head = 0;
  6.     this.tail= 0;
  7.   }
  8.   enqueue(item) {
  9.     // 队列满了
  10.       if ((this.tail + 1) % this.n == this.head) return false;
  11.     this.items[this.tail] = item;
  12.     this.tail = (this.tail + 1) % n;
  13.     return true;
  14.   }
  15.   dequeue() {
  16.     // 如果head == tail 表示队列为空
  17.     if (this.head == this.tail) return null;
  18.     let ret = this.items[this.head];
  19.     this.head = (this.head + 1) % this.n;
  20.     return ret;
  21.   }
  22. }