JavaScript是否内置高效FIFO队列及链表实现？

JavaScript没有内置的链表实现，也没有原生提供支持O(1)时间复杂度头部删除、尾部追加的队列结构。

针对你的需求，有两种常见的高效实现方案：

1. 基于双向链表手动实现队列 #

用对象模拟链表节点，维护头尾指针，可实现严格O(1)的入队（尾部追加）和出队（头部删除）操作：

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 尾部追加，O(1)
  enqueue(value) {
    const newNode = new Node(value);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.size++;
  }

  // 头部删除，O(1)
  dequeue() {
    if (!this.head) return null;
    const removedNode = this.head;
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }
    this.size--;
    return removedNode.value;
  }
}

2. 双数组模拟队列（均摊O(1)） #

利用两个数组分别承担入队栈和出队栈的角色，通过元素转移实现近似O(1)的操作，代码更简洁：

class Queue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  enqueue(value) {
    this.inStack.push(value);
  }

  dequeue() {
    if (!this.outStack.length) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
}

这种实现的入队操作是严格O(1)，出队操作是均摊O(1)——只有当出队栈为空时才需要转移元素，整体来看每个元素只会被转移一次，均摊下来时间复杂度为O(1)。

内容的提问来源于stack exchange，提问作者Mark