使用两个堆栈构造一个队列。

O(1)用于入队和出队操作。

class Queue {
  constructor() {
    this.s1 = []; // in
    this.s2 = []; // out
  }

  enqueue(val) {
    this.s1.push(val);
  }

  dequeue() {
    if (this.s2.length === 0) {
      this._move();
    }

    return this.s2.pop(); // return undefined if empty
  }

  _move() {
    while (this.s1.length) {
      this.s2.push(this.s1.pop());
    }
  }
}

这是我的实现堆栈。

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

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

我在实现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#.

数组。

栈:

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