正如其他答案中解释的那样，堆栈实现是微不足道的。

然而，我在这个线程中没有找到任何满意的答案，所以我自己做了一个队列。

在这个线程中有三种类型的解决方案:

数组——在大型数组上使用array.shift()是最糟糕的解决方案，效率非常低。 链表——它是O(1)，但是为每个元素使用一个对象有点过分，特别是如果它们很多而且它们很小，比如存储数字。 延迟移位数组——它包括将索引与数组关联。当一个元素退出队列时，索引向前移动。当索引到达数组的中间时，数组被切成两半以删除前一半。

在我看来，延迟移位数组是最令人满意的解决方案，但它们仍然将所有内容存储在一个大的连续数组中，这可能会有问题，并且当数组被切片时，应用程序将错开。

我使用小数组的链表(每个最多1000个元素)实现。这些数组的行为类似于延迟移位数组，只是它们从未被切片:当数组中的每个元素都被移除时，该数组将被简单地丢弃。

这个包在npm上，具有基本的FIFO功能，我最近刚刚推送了它。代码分为两部分。

这是第一部分

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

这里是Queue的主类:

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

类型注释(:X)可以很容易地删除，以获得ES6 javascript代码。

单端队列

这是一个使用映射的队列。由于插入顺序得到了保证，所以可以像迭代数组一样迭代它。除此之外，它的思想与Queue.js非常相似。

我做了一些简单的测试，但还没有进行广泛的测试。我还添加了一些我认为很好的功能(通过数组构造)或易于实现(例如last()和first())。

它背后的简单版本/直觉如下:

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
    }

    dequeue() {
        if (this.length() > 0) {
            this.data.delete(this.offset)
            this.offset += 1
        }
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }
}

简单版本的问题是，当内存索引超过9千万亿(Number.MAX_SAFE_INTEGER的值)时，需要重新映射内存。此外，我认为它可能很好有数组构造，它很高兴看到值正在进入队列和退出队列返回。可以通过编写以下代码来解释这一点:

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
        if (arguments.length === 1) this._initializeFromArray(arguments[0])
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
        let result = this.data.get(current)
        this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)
        return result
    }

    dequeue() {
        let result = undefined
        if (this.length() > 0) {
            result = this.data.get(this.offset)
            this.data.delete(this.offset)
            this.offset += 1
        }
        if (this.length() === 0) this.offset = 0
        return result
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }

    _remapDataIfMaxMemoryViolation(current, threshhold) {
        if (current+1 === threshhold) {
            const length = this.length()
            this.offset = 0
            for (const [key, value] of this.data) {
                this.data.set(this.offset, value)
                this.data.delete(key, value)
                this.offset += 1
                if (this.offset === length) break
            }       
        }
    }

    _initializeFromArray(array) {
        for (const value of array) {
            this.data.set(this.offset, value)
            this.offset += 1
        }
    }
}

我在Chrome开发控制台进行了一些测试，对完整版本进行了以下调用。

l = console.log // I'm lazy with typing
q = new Queue()
l('enqueue', q.enqueue(1))
l('enqueue', q.enqueue(2))
l('enqueue', q.enqueue(3))
l('enqueue', q.enqueue("hello"))
l('enqueue', q.enqueue("monkey"))
l('show 5 elements: ', q.data)
l('length', q.length())
l('first', q.first())
l('last', q.last())
l('dequeue', q.dequeue())
l('dequeue', q.dequeue())
l('show 3 elements', q.data)
q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)
l('show 3 remapped elements', q.data)

l(queue = new Queue([3,4,5,6,7,8,9]))
l(queue.data)

如果你想创建自己的数据结构，你可以创建自己的:

var Stack = function(){
  this.top = null;
  this.size = 0;
};

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

Stack.prototype.push = function(data) {
  var node = new Node(data);

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

Stack.prototype.pop = function() {
  temp = this.top;
  this.top = this.top.previous;
  this.size -= 1;
  return temp;
};

对于队列:

var Queue = function() {
  this.first = 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){
    this.first = node;
  } else {
    n = this.first;
    while (n.next) {
      n = n.next;
    }
    n.next = node;
  }

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

Queue.prototype.dequeue = function() {
  temp = this.first;
  this.first = this.first.next;
  this.size -= 1;
  return temp;
};

  var x = 10; 
  var y = 11; 
  var Queue = new Array();
  Queue.unshift(x);
  Queue.unshift(y);

  console.log(Queue)
  // Output [11, 10]

  Queue.pop()
  console.log(Queue)
  // Output [11]

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

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

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

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