在JavaScript中实现队列

时间 2021-04-08 标签 javascript 前端 java 程序员面试编程 segmentfault 服务器微信数据结构

做为一个优秀的程序猿须要具备知识的广度。首先是要了解你选择的编程语言。若是你正在阅读这篇文章，最有可能使用 JavaScript。javascript

然而在熟悉了编程语言以后，你还必须了解如何根据任务轻松且有效地操纵数据。这就是数据结构的用武之地。前端

在本文中，我将描述队列数据这个结构：它都有哪些操做以及在 JavaScript 中怎样实现。java

1. 队列数据结构

若是你喜欢四处旅行，确定在火车站经历过检票这道手续。若是有不少人要坐火车，那么很天然地会造成一个队列。刚进入车站的人加入队列。另外一边刚刚经过检票的人从队列中走出。这就是队列的一个例子，与队列数据结构的操做方式相同。程序员

队列是一种遵循先入先出（FIFO）规则的数据结构。第一个进入队列中的项目（输入）是第一个出队（输出）的。面试

队列有2个指针：队首和队尾。最早进入队列进行排队的项目位于队首，而最后进入队列的项目位于队尾。编程

回顾车站的例子，第一个检票的是在队列的队首。刚进入队列的人在队尾。segmentfault

从更高的层面来看，队列是一种容许你按照前后顺序处理项目的数据结构。服务器

2. 队列的操做

队列支持 2 个主要操做：入队（enqueue）和出队（dequeue），另外还有 peek 和 length 操做。微信

2.1 入队操做

入队操做在队列的尾部插入项目，使其成为队列的队尾。数据结构

上图中的入队操做在队尾插入了 8，以后 8 成为队列的队尾。

queue.enqueue(8);

2.2 出队操做

出队操做取出队列中第一个项目，此时队列中的下一个项目成为队首。

在上图中，出队操做返回项目7并从队列中删除。出队以后以后，项目 2 成为新的队首。

queue.dequeue(); // => 7

2.3 Peek 操做

Peek 操做读取队首的项目，可是不改变队列。

上图中 7 是队首。 peek 操做只需返回队首 7 可是不修改队列。

queue.peek(); // => 7

2.4 length

length 操做返回队列中包含项目的数量。

上图中的队列有 4 项：4、6、2 和。7。结果队列长度为 4。

queue.length; // => 4

2.5 队列操做的时间复杂度

关于队列全部操做的重点：enqueue，dequeue，peek 和 length 必须以常数时间复杂度 O(1) 执行。

常数时间复杂度 O(1) 意味着不管队列大小如何（无论是有 10 个仍是 100 万个项目），这些操做都必须在相对一致的时间内执行。

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 类中，普通对象 this.Items 将队列的项目经过数值索引保持。队首项的索引由 Where.HeadInex 跟踪，队尾项由 this.tailIndex 跟踪。

队列方法的复杂度

在 Queue 的 queue()、 dequeue()、 peek() 和 length() 方法中存在：

属性访问器（如:this.items[this.headIndex]），
执行算数操做（如:this.headidex++）

这些方法的时间复杂度是恒定的时间 O(1)。

4. 总结

队列是一种遵循先入先出（FIFO）规则的的数据结构。

队列有 2 个主要操做：入队和出队。另外，队列能够有辅助操做，例如 peek 和 length。

全部队列操做都必须以常数时间 O(1) 执行。

挑战一下：改进 dequeue() 和 peek() 方法，当在空队列上执行时会抛出错误。

本文首发微信公众号：前端先锋

欢迎扫描二维码关注公众号，天天都给你推送新鲜的前端技术文章

欢迎继续阅读本专栏其它高赞文章：

更多文章...