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

下面是一个队列的链表版本，它也包括最后一个节点，这是@perkins建议的，也是最合适的。

// QUEUE Object Definition

var Queue = function() {
  this.first = null;
  this.last = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){ // for empty list first and last are the same
    this.first = node;
    this.last = node;
  } else { // otherwise we stick it on the end
    this.last.next=node;
    this.last=node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  if (!this.first) //check for empty list
    return null;

  temp = this.first; // grab top of list
  if (this.first==this.last) {
    this.last=null;  // when we need to pop the last one
  }
  this.first = this.first.next; // move top of list down
  this.size -= 1;
  return temp;
};

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

你可以基于这个概念使用你自己的自定义类，这里是你可以用来做这些事情的代码片段

/*
*   Stack implementation in JavaScript
*/



function Stack() {
  this.top = null;
  this.count = 0;

  this.getCount = function() {
    return this.count;
  }

  this.getTop = function() {
    return this.top;
  }

  this.push = function(data) {
    var node = {
      data: data,
      next: null
    }

    node.next = this.top;
    this.top = node;

    this.count++;
  }

  this.peek = function() {
    if (this.top === null) {
      return null;
    } else {
      return this.top.data;
    }
  }

  this.pop = function() {
    if (this.top === null) {
      return null;
    } else {
      var out = this.top;
      this.top = this.top.next;
      if (this.count > 0) {
        this.count--;
      }

      return out.data;
    }
  }

  this.displayAll = function() {
    if (this.top === null) {
      return null;
    } else {
      var arr = new Array();

      var current = this.top;
      //console.log(current);
      for (var i = 0; i < this.count; i++) {
        arr[i] = current.data;
        current = current.next;
      }

      return arr;
    }
  }
}

要检查这一点，请使用控制台，并逐一尝试这些行。

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();

问候,

在Javascript中，栈和队列的实现如下:

堆栈:堆栈是一个容器，其中的对象是根据后进先出(LIFO)原则插入和删除的。

方法将一个或多个元素添加到数组的末尾，并返回数组的新长度。 方法从数组中删除最后一个元素并返回该元素。

队列:队列是根据先进先出(FIFO)原则插入和删除对象的容器(线性集合)。

方法将一个或多个元素添加到数组的开头。 Shift:该方法从数组中移除第一个元素。

let stack = []; stack.push(1);//[1] stack.push(2);//[1,2] stack.push(3);//[1,2,3] console.log('It was inserted 1,2,3 in stack:', ...stack); stack.pop(); //[1,2] console.log('Item 3 was removed:', ...stack); stack.pop(); //[1] console.log('Item 2 was removed:', ...stack); let queue = []; queue.push(1);//[1] queue.push(2);//[1,2] queue.push(3);//[1,2,3] console.log('It was inserted 1,2,3 in queue:', ...queue); queue.shift();// [2,3] console.log('Item 1 was removed:', ...queue); queue.shift();// [3] console.log('Item 2 was removed:', ...queue);

很抱歉碰到这个话题，但我滚动了许多答案，没有看到任何基于对象的队列的实现，它可以用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
    }
  }
}