Javascript数组shift()很慢，特别是当包含很多元素时。我知道两种方法来实现平摊O(1)复杂度的队列。

首先是使用循环缓冲区和表加倍。我以前实现过这个。你可以在这里看到我的源代码 https://github.com/kevyuu/rapid-queue

第二种方法是使用两个堆栈。这是带有两个堆栈的队列的代码

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

这是使用jsPerf进行的性能比较

CircularQueue.shift() vs Array.shift()

http://jsperf.com/rapidqueue-shift-vs-array-shift

正如你所看到的，大数据集的速度要快得多

我在实现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中，栈和队列的实现如下:

堆栈:堆栈是一个容器，其中的对象是根据后进先出(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);

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

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

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

你可以使用WeakMaps来实现ES6类中的私有属性，以及JavaScript语言中String属性和方法的好处，如下所示:

const _items = new WeakMap();

class Stack {
  constructor() {
    _items.set(this, []);
  }

push(obj) {
  _items.get(this).push(obj);
}

pop() {
  const L = _items.get(this).length;
  if(L===0)
    throw new Error('Stack is empty');
  return _items.get(this).pop();
}

peek() {
  const items = _items.get(this);
  if(items.length === 0)
    throw new Error ('Stack is empty');
  return items[items.length-1];
}

get count() {
  return _items.get(this).length;
}
}

const stack = new Stack();

//now in console:
//stack.push('a')
//stack.push(1)
//stack.count   => 2
//stack.peek()  => 1
//stack.pop()   => 1
//stack.pop()   => "a"
//stack.count   => 0
//stack.pop()   => Error Stack is empty