如何在面试时快速用JavaScript实现队列？

Question

如何在面试时快速用JavaScript实现队列？

5

我想知道在我编写leetcode时，是否有任何内置的模块或包可用于实现javascript中的队列。正如您所知，在面试期间手动实现队列需要花费很多时间。当我使用python时，我总是喜欢使用一个叫做“collections”的模块，其中包括一个类“deque”。但是在浏览stackoverflow之后，我发现大多数答案都是告诉人们如何从头开始在javascript中实现队列。我正在寻找这样一种方便的方法来实现它。有人能帮忙吗？

嗯，似乎没有比使用数组更好的实现队列的方法。它似乎基于javascript引擎本身。这是一个关于它的链接：javascript中unshift()与push()的时间复杂度。

- Aurora

2个回答

1

对于广度优先搜索，旋转两个数组可能会有帮助。平均FIFO时间复杂度为O(1)。

- Charlie 木匠

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- quirimmo · Accepted Answer

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

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

shift方法返回并删除数组的第一个元素（就像dequeue一样），因此如果您使用push添加元素，并使用shift删除元素，则实际上正在使用队列。

以下是一个示例：

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

console.log(a.shift());

同样地，你可以使用 unshift 在数组的开头添加元素，并使用 pop 从数组的末尾移除元素，这样就可以得到一个 FIFO 结构。

结果总是一个 FIFO 结构，其中第一个添加的元素是被取出的第一个元素：

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

console.log(a.pop());

虽然在JavaScript中使用简单的数组通过push和pop可以以O(1)的时间复杂度实现堆栈，但是上述实现队列的方法在插入时应该可以以O(1)的时间复杂度完成，但在移除时最坏情况下需要O(n)的时间复杂度。

一种更好的时间复杂度方法是使用Map，如下所示，它可以让你以O(1)的时间复杂度实现队列的插入和移除操作。

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());