没有数组(年代)

//Javascript stack linked list data structure (no array)

function node(value, noderef) {
    this.value = value;
    this.next = noderef;
}
function stack() {
    this.push = function (value) {
        this.next = this.first;
        this.first = new node(value, this.next);
    }
    this.pop = function () {
        var popvalue = this.first.value;
        this.first = this.first.next;
        return popvalue;
    }
    this.hasnext = function () {
        return this.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

//Javascript stack linked list data structure (no array)
function node(value, noderef) {
    this.value = value;
    this.next = undefined;
}
function queue() {
    this.enqueue = function (value) {
        this.oldlast = this.last;
        this.last = new node(value);
        if (this.isempty())
            this.first = this.last;
        else 
           this.oldlast.next = this.last;
    }
    this.dequeue = function () {
        var queuvalue = this.first.value;
        this.first = this.first.next;
        return queuvalue;
    }
    this.hasnext = function () {
        return this.first.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

有点晚了，但我认为答案应该在这里。下面是一个使用稀疏数组幂的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;
  }
};

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

正如其他答案中解释的那样，堆栈实现是微不足道的。

然而，我在这个线程中没有找到任何满意的答案，所以我自己做了一个队列。

在这个线程中有三种类型的解决方案:

数组——在大型数组上使用array.shift()是最糟糕的解决方案，效率非常低。 链表——它是O(1)，但是为每个元素使用一个对象有点过分，特别是如果它们很多而且它们很小，比如存储数字。 延迟移位数组——它包括将索引与数组关联。当一个元素退出队列时，索引向前移动。当索引到达数组的中间时，数组被切成两半以删除前一半。

在我看来，延迟移位数组是最令人满意的解决方案，但它们仍然将所有内容存储在一个大的连续数组中，这可能会有问题，并且当数组被切片时，应用程序将错开。

我使用小数组的链表(每个最多1000个元素)实现。这些数组的行为类似于延迟移位数组，只是它们从未被切片:当数组中的每个元素都被移除时，该数组将被简单地丢弃。

这个包在npm上，具有基本的FIFO功能，我最近刚刚推送了它。代码分为两部分。

这是第一部分

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

这里是Queue的主类:

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

类型注释(:X)可以很容易地删除，以获得ES6 javascript代码。

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技巧”

我在实现BFS时遇到了这个线程。在疑惑为何表现如此糟糕之后，我做了一些调查。array.shift()通常在O(n)中运行，这将我的BFS运行时从O(V+E)增加到O(V^2+E)。

我没有从头开始实现一个队列，而是使用了npm包双端队列，它与之前使用的数组方法兼容，工作起来很有魅力。 deque可以用作堆栈或队列。

    //import package
    import Deque from 'double-ended-queue';

    //create queue
    let queue = new Deque();
    //append
    queue.push(item);
    //dequeue (get first item inserted)
    let firstItem = queue.shift();

    //pop (get last item inserted)
    let lastItem = queue.pop();

数组。

栈:

var stack = [];

//put value on top of stack
stack.push(1);

//remove value from top of stack
var value = stack.pop();

队列:

var queue = [];

//put value on end of queue
queue.push(1);

//Take first value from queue
var value = queue.shift();