在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;
  }
};

这是一个非常快速的队列结构,并使用私有类字段隐藏关键变量以防止窥视。

其他回答

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#.

如果你理解栈的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

下面是一个相当简单的队列实现,有两个目标:

与array.shift()不同,您知道这个出队列方法需要常数时间(O(1))。 为了提高速度,这种方法使用的分配比链表方法少得多。

堆栈实现只共享第二个目标。

// Queue
function Queue() {
        this.q = new Array(5);
        this.first = 0;
        this.size = 0;
}
Queue.prototype.enqueue = function(a) {
        var other;
        if (this.size == this.q.length) {
                other = new Array(this.size*2);
                for (var i = 0; i < this.size; i++) {
                        other[i] = this.q[(this.first+i)%this.size];
                }
                this.first = 0;
                this.q = other;
        }
        this.q[(this.first+this.size)%this.q.length] = a;
        this.size++;
};
Queue.prototype.dequeue = function() {
        if (this.size == 0) return undefined;
        this.size--;
        var ret = this.q[this.first];
        this.first = (this.first+1)%this.q.length;
        return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };

// Stack
function Stack() {
        this.s = new Array(5);
        this.size = 0;
}
Stack.prototype.push = function(a) {
        var other;
    if (this.size == this.s.length) {
            other = new Array(this.s.length*2);
            for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
            this.s = other;
    }
    this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
        if (this.size == 0) return undefined;
        return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };

或者可以使用两个数组来实现队列数据结构。

var temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

如果我现在弹出元素,那么输出将是3 2 1。 但我们想先进先出结构,所以你可以做以下。

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3

如果有人需要它,你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript,它有一个队列和堆栈,它支持javascript和typescript,它是通用的,所以你可以用你自己的值类型;)