在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
数组是Javascript中的堆栈。只需使用arr.push(x)和y = arr.pop()。
下面是用Javascript实现队列的最简单方法,对于enqueue(x)和y = dequeue(),它的平摊时间都是O(1)。它使用从插入索引到元素的映射。
function newQueue() {
return {
headIdx: 0,
tailIdx: 0,
elts: {},
enqueue: (elt) => queue.elts[queue.tailIdx++] = elt,
dequeue: () => {
if (queue.headIdx == queue.tailIdx) {
throw new Error("Queue is empty");
}
return queue.elts[queue.headIdx++];
},
size: () => queue.tailIdx - queue.headIdx,
isEmpty: () => queue.tailIdx == queue.headIdx
};
}
使用链表实现的队列比这种基于映射的方法更有效,使用循环缓冲区实现的队列比这种基于映射的方法更有效,但这两种数据结构的实现更复杂(特别是循环缓冲区数据结构)。
其他回答
Javascript数组shift()很慢,特别是当包含很多元素时。我知道两种方法来实现平摊O(1)复杂度的队列。
首先是使用循环缓冲区和表加倍。我以前实现过这个。你可以在这里看到我的源代码 https://github.com/kevyuu/rapid-queue
第二种方法是使用两个堆栈。这是带有两个堆栈的队列的代码
function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];
function moveElementToPopContainer() {
while (pushContainer.length !==0 ) {
var element = pushContainer.pop();
popContainer.push(element);
}
}
that.push = function(element) {
pushContainer.push(element);
};
that.shift = function() {
if (popContainer.length === 0) {
moveElementToPopContainer();
}
if (popContainer.length === 0) {
return null;
} else {
return popContainer.pop();
}
};
that.front = function() {
if (popContainer.length === 0) {
moveElementToPopContainer();
}
if (popContainer.length === 0) {
return null;
}
return popContainer[popContainer.length - 1];
};
that.length = function() {
return pushContainer.length + popContainer.length;
};
that.isEmpty = function() {
return (pushContainer.length + popContainer.length) === 0;
};
return that;}
这是使用jsPerf进行的性能比较
CircularQueue.shift() vs Array.shift()
http://jsperf.com/rapidqueue-shift-vs-array-shift
正如你所看到的,大数据集的速度要快得多
如果有人需要它,你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript,它有一个队列和堆栈,它支持javascript和typescript,它是通用的,所以你可以用你自己的值类型;)
有点晚了,但我认为答案应该在这里。下面是一个使用稀疏数组幂的O(1)入队列和O(1)出队列的Queue实现。
JS中的稀疏数组通常被忽视,但实际上它们是一块宝石,我们应该在一些关键任务中使用它们的力量。
这是一个骨架队列实现它扩展了数组类型并在O(1)中做了所有的事情。
class Queue extends Array { constructor(){ super() Object.defineProperty(this,"head",{ value : 0 , writable: true }); } enqueue(x) { this.push(x); return this; } dequeue() { var first; return this.head < this.length ? ( first = this[this.head] , delete this[this.head++] , first ) : void 0; // perfect undefined } peek() { return this[this.head]; } } var q = new Queue(); console.log(q.dequeue()); // doesn't break console.log(q.enqueue(10)); // add 10 console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc) console.log(q); // display q console.log(q.dequeue()); // lets get the first one in the line console.log(q.dequeue()); // lets get DIO out from the line .as-console-wrapper { max-height: 100% !important; }
那么这里是否存在潜在的内存泄漏?不,我不这么认为。JS的稀疏数组是不连续的。因此,删除的项不应该成为数组内存占用的一部分。让GC帮你完成任务。这是免费的。
一个潜在的问题是,长度属性在不断将项目放入队列时无限增长。然而,仍然可以实现一个自动刷新(冷凝)机制,一旦长度达到某个值。
编辑:
上面的代码很好,但是删除操作符仍然是O(1),是一个很慢的操作符。此外,现代JS引擎是如此优化,对于< ~25000项。shift()工作O(1)无论如何。所以我们需要更好的东西。
在这种特殊情况下,随着引擎的发展,我们必须利用它们的新力量。下面的代码使用链表,我相信它是截至2021年最快、最安全的现代JS队列结构。
class Queue {
#head;
#last;
constructor(){
this.#head;
this.#last;
};
enqueue(value){
var link = {value, next: void 0};
this.#last = this.#head ? this.#last.next = link
: this.#head = link;
}
dequeue(){
var first;
return this.#head && ( first = this.#head.value
, this.#head = this.#head.next
, first
);
}
peek(){
return this.#head && this.#head.value;
}
};
这是一个非常快速的队列结构,并使用私有类字段隐藏关键变量以防止窥视。
var stack = [];
stack.push(2); // stack is now [2]
stack.push(5); // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i); // displays 5
var queue = [];
queue.push(2); // queue is now [2]
queue.push(5); // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i); // displays 2
摘自“9个你可能不知道的JavaScript技巧”
如果你理解栈的push()和pop()函数,那么queue只是在相反的意义上进行这些操作之一。push()的对边是unshift(), pop()的对边是shift()。 然后:
//classic stack
var stack = [];
stack.push("first"); // push inserts at the end
stack.push("second");
stack.push("last");
stack.pop(); //pop takes the "last" element
//One way to implement queue is to insert elements in the oposite sense than a stack
var queue = [];
queue.unshift("first"); //unshift inserts at the beginning
queue.unshift("second");
queue.unshift("last");
queue.pop(); //"first"
//other way to do queues is to take the elements in the oposite sense than stack
var queue = [];
queue.push("first"); //push, as in the stack inserts at the end
queue.push("second");
queue.push("last");
queue.shift(); //but shift takes the "first" element