如何在访问期间编码时在短时间内在javascript中实现队列？

Question

我想知道queue当我在leetcode上编码时,我可以使用任何内置模块或包来实现javascript.如您所知,在面试过程中用手实施队列是不可能的.当我使用python时,我总是喜欢使用一个collections包含类的模块deque.但在浏览堆栈溢出后,我发现大多数答案都告诉人们如何从头开始在javascript中实现队列.我正在寻找这种方便的方法来实现它.有人可以帮忙吗？

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

Answer 1

A queue是FIFO结构,其中列表中的第一个插入元素是第一个要取消的元素.

在JavaScript中,您可以轻松使用Arrays来实现此逻辑.

该shift方法返回并删除数组的第一个元素(同样dequeue如此),因此如果使用添加元素push,并删除元素shift,则实际上使用的是队列.

这是一个例子:

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

console.log(a.shift());

同样,您可以使用FIFO甚至unshift用于在数组的开头添加以及从数组pop的末尾删除.

结果总是一个FIFO结构,其中您添加的第一个元素是第一个被取消的元素:

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

console.log(a.pop());

虽然在Java中实现堆栈可以在O(1)中使用简单数组完成,push并且通过popO(1),如上所述实现的队列应该采用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());