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

我认为实现堆栈和队列的最干净的方法应该是使用一个允许从两端添加和删除的容器，然后限制其在一端的功能，这可以通过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();

Javascript有push和pop方法，它们操作在普通的Javascript数组对象上。

关于排队，请看这里:

http://safalra.com/web-design/javascript/queues/

Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because of the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called. Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time. As a result, for larger queues, it can be significantly faster than using arrays.

或者可以使用两个数组来实现队列数据结构。

var temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

如果我现在弹出元素，那么输出将是3 2 1。 但我们想先进先出结构，所以你可以做以下。

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3

下面是我使用链表实现的堆栈和队列:

// Linked List function Node(data) { this.data = data; this.next = null; } // Stack implemented using LinkedList function Stack() { this.top = null; } Stack.prototype.push = function(data) { var newNode = new Node(data); newNode.next = this.top; //Special attention this.top = newNode; } Stack.prototype.pop = function() { if (this.top !== null) { var topItem = this.top.data; this.top = this.top.next; return topItem; } return null; } Stack.prototype.print = function() { var curr = this.top; while (curr) { console.log(curr.data); curr = curr.next; } } // var stack = new Stack(); // stack.push(3); // stack.push(5); // stack.push(7); // stack.print(); // Queue implemented using LinkedList function Queue() { this.head = null; this.tail = null; } Queue.prototype.enqueue = function(data) { var newNode = new Node(data); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } } Queue.prototype.dequeue = function() { var newNode; if (this.head !== null) { newNode = this.head.data; this.head = this.head.next; } return newNode; } Queue.prototype.print = function() { var curr = this.head; while (curr) { console.log(curr.data); curr = curr.next; } } var queue = new Queue(); queue.enqueue(3); queue.enqueue(5); queue.enqueue(7); queue.print(); queue.dequeue(); queue.dequeue(); queue.print();

这是我的实现堆栈。

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