js队列实现

队列的基本概念

队列是一种先进先出（FIFO）的数据结构，支持从队尾插入元素（入队），从队头移除元素（出队）。JavaScript中可通过数组或链表实现队列。

基于数组的实现

利用数组的 push 和 shift 方法模拟队列操作：

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

  // 入队
  enqueue(element) {
    this.items.push(element);
  }

  // 出队
  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    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;
  }

  // 清空队列
  clear() {
    this.items = [];
  }
}

注意：shift() 操作的时间复杂度为 O(n)，频繁出队时性能较差。

基于链表的实现

通过链表节点维护队列结构，避免数组移动的开销：

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 removedValue = this.head.value;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) this.tail = null;
    return removedValue;
  }

  // 查看队头
  peek() {
    return this.head?.value ?? null;
  }

  // 检查是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 返回队列大小
  size() {
    return this.length;
  }
}

优势：链表实现的入队和出队操作均为 O(1) 时间复杂度。

循环队列（优化版）

解决数组实现中空间浪费的问题：

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

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

  // 出队
  dequeue() {
    if (this.isEmpty()) return null;
    const element = this.items[this.head];
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    return element;
  }

  // 检查是否为空
  isEmpty() {
    return this.size === 0;
  }

  // 检查是否已满
  isFull() {
    return this.size === this.capacity;
  }
}

适用场景：需要固定大小队列时（如消息缓冲池）。

实际应用示例

任务调度：使用队列管理异步任务顺序执行：

const taskQueue = new ArrayQueue();
taskQueue.enqueue(() => console.log("Task 1"));
taskQueue.enqueue(() => console.log("Task 2"));

while (!taskQueue.isEmpty()) {
  const task = taskQueue.dequeue();
  task(); // 依次输出 "Task 1", "Task 2"
}