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

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

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

问候,

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

我认为实现堆栈和队列的最干净的方法应该是使用一个允许从两端添加和删除的容器，然后限制其在一端的功能，这可以通过Javascript中的一个简单数组来完成。

//堆栈容器在封装时使用的语句

// Allow push and pop from the same end
array.push(element);
array.pop();

//封装时在队列容器中使用的语句

// Allow push and pop from different ends
array.push(element);
array.shift();

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

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

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