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.

如果你正在寻找带有一些基本操作(基于链表)的堆栈和队列数据结构的ES6 OOP实现，那么它可能是这样的:

Queue.js

import LinkedList from '../linked-list/LinkedList';

export default class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  isEmpty() {
    return !this.linkedList.tail;
  }

  peek() {
    if (!this.linkedList.head) {
      return null;
    }

    return this.linkedList.head.value;
  }

  enqueue(value) {
    this.linkedList.append(value);
  }

  dequeue() {
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }

  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Stack.js

import LinkedList from '../linked-list/LinkedList';

export default class Stack {
  constructor() {
    this.linkedList = new LinkedList();
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.linkedList.tail;
  }

  /**
   * @return {*}
   */
  peek() {
    if (!this.linkedList.tail) {
      return null;
    }

    return this.linkedList.tail.value;
  }

  /**
   * @param {*} value
   */
  push(value) {
    this.linkedList.append(value);
  }

  /**
   * @return {*}
   */
  pop() {
    const removedTail = this.linkedList.deleteTail();
    return removedTail ? removedTail.value : null;
  }

  /**
   * @return {*[]}
   */
  toArray() {
    return this.linkedList
      .toArray()
      .map(linkedListNode => linkedListNode.value)
      .reverse();
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

上面例子中用于堆栈和队列的LinkedList实现可以在GitHub上找到。

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

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

单端队列

这是一个使用映射的队列。由于插入顺序得到了保证，所以可以像迭代数组一样迭代它。除此之外，它的思想与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)

很抱歉碰到这个话题，但我滚动了许多答案，没有看到任何基于对象的队列的实现，它可以用O(1)执行排队和出队列，并且没有浪费内存。

Dmitri Pavlutin在他的博客https://dmitripavlutin.com/javascript-queue/上有一个很好的入门代码

它只遗漏了一个长度为0的检查，这是很容易添加的。

这个解决方案的最大和唯一的问题是不断增长的索引可能会在某一点上达到一些数量限制，如果队列运行很长时间和/或高速(我的意图是处理音频=高速)。

这个问题没有完美的解决方案……最简单的方法是在队列为空时将索引重置为0。

最后，我添加了一个重构方法，它将所有索引移回开始，以在队列永远不为空的情况下使用。

性能无疑是更好的(以毫秒为单位的时间，排队10000个号码然后退出它们):

class QueueObject {
  constructor () {
    this.data = {}
    this.head = 0
    this.tail = 0
    this.length = 0
  }
  enqueue (value) {
    this.data[this.tail++] = value
    this.length++
  }
  dequeue () {
    let value
    if (this.length > 0) {
      this.length--
      value = this.data[this.head]
      delete this.data[this.head++]
    } else {
      this.head = 0
      this.tail = 0
      value = null
    }
    return value
  }
  refactor () {
    if (this.head > 0) {
      for (let i = this.head; i < this.tail; i++) {
        this.data[i - this.head] = this.data[i]
        delete this.data[i]
      }
      this.tail = this.length
      this.head = 0
    }
  }
}

你可以使用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