没有数组(年代)

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

}

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

数组。

栈:

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();

很抱歉碰到这个话题，但我滚动了许多答案，没有看到任何基于对象的队列的实现，它可以用O(1)执行排队和出队列，并且没有浪费内存。

Dmitri Pavlutin在他的博客https://dmitripavlutin.com/javascript-queue/上有一个很好的入门代码

它只遗漏了一个长度为0的检查，这是很容易添加的。

这个解决方案的最大和唯一的问题是不断增长的索引可能会在某一点上达到一些数量限制，如果队列运行很长时间和/或高速(我的意图是处理音频=高速)。

这个问题没有完美的解决方案……最简单的方法是在队列为空时将索引重置为0。

最后，我添加了一个重构方法，它将所有索引移回开始，以在队列永远不为空的情况下使用。

性能无疑是更好的(以毫秒为单位的时间，排队10000个号码然后退出它们):

class QueueObject {
  constructor () {
    this.data = {}
    this.head = 0
    this.tail = 0
    this.length = 0
  }
  enqueue (value) {
    this.data[this.tail++] = value
    this.length++
  }
  dequeue () {
    let value
    if (this.length > 0) {
      this.length--
      value = this.data[this.head]
      delete this.data[this.head++]
    } else {
      this.head = 0
      this.tail = 0
      value = null
    }
    return value
  }
  refactor () {
    if (this.head > 0) {
      for (let i = this.head; i < this.tail; i++) {
        this.data[i - this.head] = this.data[i]
        delete this.data[i]
      }
      this.tail = this.length
      this.head = 0
    }
  }
}

我在实现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();

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