js 队列实现

队列的基本概念

队列是一种遵循先进先出（FIFO）原则的线性数据结构。在JavaScript中，队列可以通过数组或链表实现，核心操作包括入队（enqueue）、出队（dequeue）、查看队首（peek）和判断是否为空（isEmpty）。

基于数组的实现

使用数组实现队列简单直观，但需注意数组的shift()方法在删除首元素时会导致后续元素移动，性能较差（时间复杂度O(n)）。

class ArrayQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();
  }

  peek() {
    if (this.isEmpty()) return null;
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

基于链表的实现

链表实现避免了数组的性能问题，入队和出队操作均为O(1)时间复杂度。

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

class LinkedListQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  dequeue() {
    if (!this.head) return null;
    const removedNode = this.head;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.length--;
    return removedNode.value;
  }

  peek() {
    return this.head?.value ?? null;
  }

  isEmpty() {
    return this.length === 0;
  }
}

循环队列优化

针对数组实现的性能问题，可通过循环队列（Circular Queue）优化。使用固定大小的数组和指针追踪队首和队尾。

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.rear = -1;
    this.size = 0;
  }

  enqueue(element) {
    if (this.isFull()) return false;
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = element;
    this.size++;
    return true;
  }

  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.items[this.front];
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }

  peek() {
    return this.isEmpty() ? null : this.items[this.front];
  }

  isEmpty() {
    return this.size === 0;
  }

  isFull() {
    return this.size === this.capacity;
  }
}

使用场景示例

• 任务调度：按顺序处理异步任务。
• 广度优先搜索（BFS）：树的层级遍历或图的路径查找。
• 消息队列：模拟生产者-消费者模型。

// BFS示例（二叉树层级遍历）
function levelOrder(root) {
  const queue = new LinkedListQueue();
  const result = [];
  if (root) queue.enqueue(root);

  while (!queue.isEmpty()) {
    const levelSize = queue.size();
    const currentLevel = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.dequeue();
      currentLevel.push(node.val);
      if (node.left) queue.enqueue(node.left);
      if (node.right) queue.enqueue(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}