在 JS 中实现队列操作可以很简单

成为一名优秀的开发人员需要具备多种学科的知识。

第一个要求是了解所选择的编程语言。如果你正在阅读这篇文章，很可能你使用的是JavaScript。

然而，在了解编程语言的基础上，您还必须了解如何组织数据，以便根据任务轻松有效地操作数据。这就是数据结构发挥作用的地方。

在这篇文章中，我将描述队列数据结构，它有哪些操作，并提供一个JavaScript的队列实现。

1. 队列数据结构

想象一下，如果你喜欢旅行(像我一样)，你很可能已经在机场办理了登机手续。如果有很多旅客愿意办理登机手续，那么在办理登机手续的柜台前自然就会排起长队。

一名旅客刚进入机场，想要办理登机手续，他将会排队等候。另一个刚刚通过值机手续的旅客将从队列中退出。

这是队列的真实示例—队列数据结构以同样的方式工作。

• 队列是一种先输入先输出(FIFO)数据结构。第一个进入队列的项(输入)是第一个退出队列的项(输出)。
• 一个队列有两个指针:头和尾。最早进入队列的项在队列的头部，而最新进入队列的项在队列的尾部。

回想一下机场的例子，在办理登机手续的旅客是队列的最前面。刚进入队伍的旅客排在最后面。

从更高的角度来看，队列是一种数据结构，它允许您按照条目进入的相同顺序一次处理一个条目。

2. 队列的操作

该队列支持2个主要操作:入队列和出队列。此外，您可能会发现使用peek和length操作很有用。

2.1 入队操作

入队操作在队列的尾部插入一项。进入队列的项成为队列的尾部。

上图中的排队操作将项目8插入到尾部。8成为队列的尾部。

queue.enqueue(8);

2.2 出队操作

出队列操作提取队列头部的项。队列中的下一项成为头部。

在上图中，dequeue操作返回并从队列中删除item 7。出队列后，项目2成为新的头部。

queue.dequeue(); // => 7

2.3 Peek 操作

peek操作读取队列头部，而不改变队列。

在上图中，dequeue操作返回并从队列中删除item 7。出队列后，项目2成为新的头部。

queue.dequeue(); // => 7

2.3 Peek 操作

peek操作读取队列头部，而不改变队列。

项7是上图中队列的头。peek操作只是返回头部—项目7—而没有修改队列。

queue.peek(); // => 7

2.4 队列长度

长度操作计算队列包含多少项。

图片中的队列有4个项目:4、6、2和7。因此，队列长度为4。

queue.length; // => 4

2.5 队列操作的时间复杂度

关于所有队列操作——入队、出队、查看(peek)和长度——所有这些操作必须在常量时间O(1)内执行。

常数时间O(1)意味着无论队列的大小(它可以有1000万项或100万项):入队、出队、查看(peek)和长度操作必须相对同时执行。

3. 用JavaScript实现队列

让我们看看队列数据结构的一种可能实现，同时保持所有操作必须在常量时间O(1)内执行的要求。

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  get length() {
    return this.tailIndex - this.headIndex;
  }
}

const queue = new Queue();

queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);

queue.dequeue(); // => 7

queue.peek();    // => 2

queue.length;    // => 3

const queue = new queue()是创建队列实例的方法。

调用queue.enqueue(7)方法将项目7放入队列。

queue.dequeue()将一个头部项从队列中取出，而queue.peek()只查看头部项。

最后, queue.length 长度显示队列中还有多少项。

关于实现: 在Queue类中，plain对象this.Items通过数字索引保存队列中的项。item 的索引由this跟踪。尾项由this.tailIndex跟踪。

4. 总结

队列数据结构是一种先输入先输出(FIFO)的类型:最先进入队列的项目最先退出队列。

队列有2个主要操作:入队列和出队列。此外，队列可以有像peek和length这样的辅助操作。

所有队列操作必须在固定时间O(1)内执行。