在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
使用两个堆栈构造一个队列。
O(1)用于入队和出队操作。
class Queue {
constructor() {
this.s1 = []; // in
this.s2 = []; // out
}
enqueue(val) {
this.s1.push(val);
}
dequeue() {
if (this.s2.length === 0) {
this._move();
}
return this.s2.pop(); // return undefined if empty
}
_move() {
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
}
}
其他回答
Create a pair of classes that provide the various methods that each of these data structures has (push, pop, peek, etc). Now implement the methods. If you're familiar with the concepts behind stack/queue, this should be pretty straightforward. You can implement the stack with an array, and a queue with a linked list, although there are certainly other ways to go about it. Javascript will make this easy, because it is weakly typed, so you don't even have to worry about generic types, which you'd have to do if you were implementing it in Java or C#.
Javascript有push和pop方法,它们操作在普通的Javascript数组对象上。
关于排队,请看这里:
http://safalra.com/web-design/javascript/queues/
Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because of the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called. Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time. As a result, for larger queues, it can be significantly faster than using arrays.
Javascript中的常规数组结构是一个堆栈(先入后出),也可以用作队列(先入先出),这取决于你所做的调用。
检查这个链接,看看如何让一个数组像一个队列:
队列
有点晚了,但我认为答案应该在这里。下面是一个使用稀疏数组幂的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 x = 10;
var y = 11;
var Queue = new Array();
Queue.unshift(x);
Queue.unshift(y);
console.log(Queue)
// Output [11, 10]
Queue.pop()
console.log(Queue)
// Output [11]