在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
As many have said: native array using push and pop is fine for a stack, but using shift for taking elements from a queue means that the remaining elements need to move, which is potentially slow. The idea of using two stacks to make a queue in kevinyu's answer is a nice idea to fix it, and of course that can be done with native-array-stacks as well. (Edit: there was actually already an answer by Yuki-Dreamer that does this, albeit less compactly. I didn't notice it until now because it was unfairly downvoted.)
下面是一个使用ES5/ES6特性的紧凑实现，它使队列对象的行为尽可能接近本机的push/shift变体，除了每次操作花费O(1)平摊时间:
const queue = () => {
const a = [], b = [];
return {
push: (...elts) => a.push(...elts),
shift: () => {
if (b.length === 0) {
while (a.length > 0) { b.push(a.pop()) }
}
return b.pop();
},
get length() { return a.length + b.length }
}
}
现在你可以做:
const q = queue();
q.push(8);
q.push(9);
q.push(10);
console.log(q.length); // outputs 3
console.log(q.shift()); // outputs 8
q.push(11);
console.log(q.shift()); // outputs 9
console.log(q.shift()); // outputs 10
console.log(q.shift()); // outputs 11
console.log(q.shift()); // outputs undefined
队列实现对长度使用getter语法，使其看起来像一个属性，并对push使用rest参数语法，以允许一次推送多个内容。如果你不想这样做，你可以用push: elt => a.push(elt)，替换第4行。(但是请注意，你不能用push: a.push替换它，就像我自己第一次尝试的那样，结果非常奇怪:这是因为它导致本机push方法被调用，并设置为队列对象。)
其他回答
有很多方法可以在Javascript中实现堆栈和队列。上面的大多数答案都是非常肤浅的实现，我将尝试实现一些更可读(使用es6的新语法特性)和更健壮的东西。
下面是堆栈实现:
class Stack {
constructor(...items){
this._items = []
if(items.length>0)
items.forEach(item => this._items.push(item) )
}
push(...items){
//push item to the stack
items.forEach(item => this._items.push(item) )
return this._items;
}
pop(count=0){
//pull out the topmost item (last item) from stack
if(count===0)
return this._items.pop()
else
return this._items.splice( -count, count )
}
peek(){
// see what's the last item in stack
return this._items[this._items.length-1]
}
size(){
//no. of items in stack
return this._items.length
}
isEmpty(){
// return whether the stack is empty or not
return this._items.length==0
}
toArray(){
return this._items;
}
}
下面是如何使用堆栈:
let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3
如果您想查看关于此实现的详细描述以及如何进一步改进，请阅读这里:http://jschap.com/data-structures-in-javascript-stack/
下面是es6中队列实现的代码:
class Queue{
constructor(...items){
//initialize the items in queue
this._items = []
// enqueuing the items passed to the constructor
this.enqueue(...items)
}
enqueue(...items){
//push items into the queue
items.forEach( item => this._items.push(item) )
return this._items;
}
dequeue(count=1){
//pull out the first item from the queue
this._items.splice(0,count);
return this._items;
}
peek(){
//peek at the first item from the queue
return this._items[0]
}
size(){
//get the length of queue
return this._items.length
}
isEmpty(){
//find whether the queue is empty or no
return this._items.length===0
}
}
下面是如何使用这个实现:
let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3
要完整地了解如何实现这些数据结构以及如何进一步改进这些数据结构，您可能需要阅读jschap.com上的“在javascript中处理数据结构”系列。这是队列的链接——http://jschap.com/playing-data-structures-javascript-queues/
这是我的实现堆栈。
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());
As many have said: native array using push and pop is fine for a stack, but using shift for taking elements from a queue means that the remaining elements need to move, which is potentially slow. The idea of using two stacks to make a queue in kevinyu's answer is a nice idea to fix it, and of course that can be done with native-array-stacks as well. (Edit: there was actually already an answer by Yuki-Dreamer that does this, albeit less compactly. I didn't notice it until now because it was unfairly downvoted.)
下面是一个使用ES5/ES6特性的紧凑实现，它使队列对象的行为尽可能接近本机的push/shift变体，除了每次操作花费O(1)平摊时间:
const queue = () => {
const a = [], b = [];
return {
push: (...elts) => a.push(...elts),
shift: () => {
if (b.length === 0) {
while (a.length > 0) { b.push(a.pop()) }
}
return b.pop();
},
get length() { return a.length + b.length }
}
}
现在你可以做:
const q = queue();
q.push(8);
q.push(9);
q.push(10);
console.log(q.length); // outputs 3
console.log(q.shift()); // outputs 8
q.push(11);
console.log(q.shift()); // outputs 9
console.log(q.shift()); // outputs 10
console.log(q.shift()); // outputs 11
console.log(q.shift()); // outputs undefined
队列实现对长度使用getter语法，使其看起来像一个属性，并对push使用rest参数语法，以允许一次推送多个内容。如果你不想这样做，你可以用push: elt => a.push(elt)，替换第4行。(但是请注意，你不能用push: a.push替换它，就像我自己第一次尝试的那样，结果非常奇怪:这是因为它导致本机push方法被调用，并设置为队列对象。)
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
正如你所看到的，大数据集的速度要快得多
有点晚了，但我认为答案应该在这里。下面是一个使用稀疏数组幂的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;
}
};
这是一个非常快速的队列结构，并使用私有类字段隐藏关键变量以防止窥视。
