javascript - 面试编码时如何在短时间内用javascript实现一个队列？

Question

我想知道当我在 leetcode 上编码时，是否有任何内置模块或包可用于在 javascript 中实现 queue。如您所知，在面试期间不可能花很多时间手动实现队列。当我使用 python 时，我总是喜欢使用一个名为 collections 的模块，其中包含一个类 deque。但是在浏览了 stack overflow 之后，我发现大部分答案都在告诉人们如何从头开始在 javascript 中实现队列。我正在寻找这样一种方便的方法来实现它。有人可以帮忙吗？

Hmmmmmmmm，似乎没有比使用数组更好的实现队列的方法了。它似乎是基于 javascript 引擎本身。这是一个关于它的链接:time complexity of unshift() vs. push() in Javascript

Answer 1

queue 是一个 FIFO 结构，其中列表中第一个插入的元素是第一个被取出的元素。

在 JavaScript 中，您可以轻松地使用数组来实现此逻辑。

shift 方法返回并移除数组的第一个元素(与 dequeue 一样)，因此如果您使用 push 添加元素，并使用 shift 删除元素，您实际上是在使用队列。

下面是一个例子:

const a = [];
a.push(3);
a.push(5);
a.push(7);

console.log(a.shift());

以同样的方式，您甚至可以使用 unshift 在数组的开头添加，并使用 pop 从数组的结尾删除。

结果始终是一个 FIFO 结构，其中您添加的第一个元素是第一个被删除的元素:

const a = [];
a.unshift(3);
a.unshift(5);
a.unshift(7);

console.log(a.pop());

虽然在 JavaScript 中实现堆栈可以在 O(1) 中使用简单数组完成，但通过采用 O(1) 的 push 和 pop，队列实现为上面应该用 O(1) 来插入，在最坏的情况下用 O(n) 来移除。

您可以采用一种更好的时间复杂度方法，它应该让您在 O(1) 中为插入和移除实现一个队列，可以使用 Map 来完成，如下所示:

class MyQueue extends Map {
  constructor() {
    super();
    this.insertionIndex = 0;
    this.removalIndex = 0;
  }

  queue(element) {
    this.set(this.insertionIndex, element);
    this.insertionIndex++;
  }

  dequeue() {
    const el = this.get(this.removalIndex);
    if (typeof el !== 'undefined') {
      this.delete(this.removalIndex);
      this.removalIndex++;
    }
    return el;
  }
}

const q = new MyQueue();
q.queue(1);
q.queue(2);
console.log(q.dequeue());
console.log(q.dequeue());
q.queue(3);
console.log(q.dequeue());
console.log(q.dequeue()); // now is empty so dequeue will return undefined with no errors
q.queue(4);
console.log(q.dequeue());