JavaScript Queue

学习目标

理解队列的基本概念及其遵循的 FIFO（先进先出）原则
掌握使用数组、链表和循环数组三种方式实现队列的方法
能够根据应用场景选择合适的队列实现方式
了解各种实现的时间与空间复杂度差异

队列的基本概念

队列是一种线性数据结构，其操作遵循 FIFO（First In, First Out，先进先出） 原则：

元素从队尾（rear） 插入（enqueue）
元素从队首（front） 移除（dequeue）

核心操作

方法	说明
`enqueue(item)`	将元素添加到队尾
`dequeue()`	移除并返回队首元素
`peek()`	返回队首元素但不移除
`isEmpty()`	判断队列是否为空
`size()` / `getSize()`	返回队列中元素数量
`clear()`	清空队列（部分实现中提供）
`print()`	打印队列内容（用于调试）

基于数组的队列

这是最直观的实现方式，利用 JavaScript 数组的 push() 和 shift() 方法。

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

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

  dequeue() {
    return this.isEmpty() ? "队列为空" : this.items.shift();
  }

  peek() {
    return this.isEmpty() ? "队列为空" : this.items[0];
  }

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

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

  print() {
    console.log(this.items.join(" -> "));
  }
}

// 示例使用
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.print();          // 输出: 1 -> 2 -> 3
console.log(queue.dequeue()); // 输出: 1
console.log(queue.peek());    // 输出: 2
console.log(queue.size());    // 输出: 2

复杂度分析

enqueue()：O(1) —— 在末尾添加
dequeue()：O(n) —— shift() 需要移动所有后续元素
其他操作（peek, isEmpty, size）：O(1)
print()：O(n)

缺点：频繁 dequeue 会导致性能下降，不适合高频出队场景。

基于链表的队列

通过维护 front（头节点）和 rear（尾节点）指针，实现高效的入队和出队。

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(data) {
    const newNode = new Node(data);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) return null;

    const removedData = this.front.data;
    this.front = this.front.next;
    if (!this.front) this.rear = null; // 队列变空
    this.size--;
    return removedData;
  }

  peek() {
    return this.isEmpty() ? null : this.front.data;
  }

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

  getSize() {
    return this.size;
  }

  print() {
    let current = this.front;
    const elements = [];
    while (current) {
      elements.push(current.data);
      current = current.next;
    }
    console.log(elements.join(' -> '));
  }
}

// 示例使用
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.print();           // 输出: 10 -> 20 -> 30
console.log(queue.dequeue()); // 输出: 10
queue.print();           // 输出: 20 -> 30

复杂度分析

所有核心操作（enqueue, dequeue, peek, isEmpty, getSize）：O(1)
print()：O(n)
内存按需分配，无浪费

优点：高效、动态内存管理，适合生产环境。

基于循环数组的队列

适用于固定容量的高性能场景（如缓冲区、任务调度）。

版本 A

维护 front 和 rear 指针

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

  enqueue(element) {
    if ((this.rear + 1) % this.size === this.front) {
      console.log("队列已满！");
      return;
    }
    if (this.front === -1) this.front = 0;
    this.rear = (this.rear + 1) % this.size;
    this.queue[this.rear] = element;
    console.log(`${element} 已入队`);
  }

  dequeue() {
    if (this.front === -1) {
      console.log("队列为空！");
      return;
    }
    const data = this.queue[this.front];
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.size;
    }
    console.log(`${data} 已出队`);
    return data;
  }

  peek() {
    return this.front === -1 ? null : this.queue[this.front];
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return (this.rear + 1) % this.size === this.front;
  }

  printQueue() {
    if (this.isEmpty()) {
      console.log("队列为空！");
      return;
    }
    const elements = [];
    let i = this.front;
    while (i !== this.rear) {
      elements.push(this.queue[i]);
      i = (i + 1) % this.size;
    }
    elements.push(this.queue[this.rear]);
    console.log("队列:", elements.join(' -> '));
  }
}

版本 B

仅维护 front 和 count（更简洁）

class CircularQueue {
  constructor(size) {
    this.size = size;
    this.queue = new Array(size);
    this.front = -1;
    this.count = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      console.log("队列已满！");
      return;
    }
    if (this.front === -1) this.front = 0;
    const rear = (this.front + this.count) % this.size;
    this.queue[rear] = element;
    this.count++;
    console.log(`${element} 已入队`);
  }

  dequeue() {
    if (this.isEmpty()) {
      console.log("队列为空！");
      return;
    }
    const data = this.queue[this.front];
    if (this.count === 1) {
      this.front = -1;
    } else {
      this.front = (this.front + 1) % this.size;
    }
    this.count--;
    console.log(`${data} 已出队`);
    return data;
  }

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

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

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

  printQueue() {
    if (this.isEmpty()) {
      console.log("队列为空！");
      return;
    }
    const elements = [];
    for (let i = 0; i < this.count; i++) {
      elements.push(this.queue[(this.front + i) % this.size]);
    }
    console.log("队列:", elements.join(" -> "));
  }
}

循环队列优势

所有操作均为 O(1)
内存固定，避免动态分配开销
有效利用数组空间，避免“假溢出”

适用场景：嵌入式系统、实时系统、固定缓冲区（如音频 / 视频流处理）

实现方式对比

实现方式	`enqueue`	`dequeue`	内存效率	动态扩容	适用场景
数组	O(1)	O(n)	低（`shift` 开销大）	自动	小规模、低频操作
链表	O(1)	O(1)	高（按需分配）	是	通用、高性能需求
循环数组	O(1)	O(1)	极高（固定内存）	否	固定容量、实时系统

重点总结

队列是 FIFO 结构，广泛用于任务调度、广度优先搜索（BFS）、消息队列等场景。
数组实现简单但 dequeue 性能差，不适合高频出队。
链表实现性能最优且灵活，是通用推荐方案。
循环数组实现内存高效，适合资源受限或固定容量场景。
在实际开发中，应根据性能要求、内存限制和数据规模选择合适的实现。

思考题

为什么在浏览器环境中，基于链表的队列通常比基于数组的队列更适合处理大量动态数据？
假设你要实现一个“最近浏览记录”功能，最多保存 100 条记录，新记录加入时自动移除最旧的记录。你会选择哪种队列实现？为什么？
循环队列中为什么要牺牲一个数组位置（即容量为 n 的数组只能存 n-1 个元素）？有没有办法避免这一点？