我想知道当我在 leetcode 上编码时,是否有任何内置模块或包可用于在 javascript 中实现 queue
。如您所知,在面试期间不可能花很多时间手动实现队列。当我使用 python 时,我总是喜欢使用一个名为 collections
的模块,其中包含一个类 deque
。但是在浏览了 stack overflow 之后,我发现大部分答案都在告诉人们如何从头开始在 javascript 中实现队列。我正在寻找这样一种方便的方法来实现它。有人可以帮忙吗?
Hmmmmmmmm,似乎没有比使用数组更好的实现队列的方法了。它似乎是基于 javascript 引擎本身。这是一个关于它的链接:time complexity of unshift() vs. push() in Javascript
最佳答案
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());
关于javascript - 面试编码时如何在短时间内用javascript实现一个队列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53966240/