4. 队列（Queue）

问题：需要「先进先出」的顺序，如任务调度、消息队列、BFS 广度优先搜索。

核心：从队尾入队（enqueue）、从队首出队（dequeue），先进先出（FIFO）。

特点

两端操作：队尾入队，队首出队
Enqueue / Dequeue 均 O(1)
不支持随机访问

优点

公平的排队顺序，FIFO 保证
O(1) 入队出队
适合缓冲、调度场景

缺点

只能访问队首和队尾
用数组实现时，shift() 是 O(n)（JS）；需用循环队列优化
不适合需要优先级或随机访问的场景

// 用对象实现 O(1) 队列（避免 Array.shift 的 O(n)）
class Queue {
  #items = {};
  #head = 0;
  #tail = 0;

  enqueue(val) {
    this.#items[this.#tail++] = val;
  }

  dequeue() {
    if (this.#head === this.#tail) return undefined;
    const val = this.#items[this.#head];
    delete this.#items[this.#head++];
    return val;
  }

  peek()    { return this.#items[this.#head]; }
  get size() { return this.#tail - this.#head; }
}

// BFS 广度优先搜索
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = new Queue();
  queue.enqueue(start);
  const order = [];

  while (queue.size) {
    const node = queue.dequeue();
    order.push(node);
    for (const neighbor of graph[node] ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }
  return order;
}

package queue

// 基于切片的队列（简单实现，生产环境建议 ring buffer）
type Queue[T any] struct {
    data []T
    head int
}

func (q *Queue[T]) Enqueue(val T) {
    q.data = append(q.data, val)
}

func (q *Queue[T]) Dequeue() T {
    val := q.data[q.head]
    q.head++
    // 缩容：已用空间不足总空间 1/4 时回收
    if q.head > len(q.data)/4 {
        q.data = q.data[q.head:]
        q.head = 0
    }
    return val
}

func (q *Queue[T]) Peek() T {
    return q.data[q.head]
}

func (q *Queue[T]) Size() int {
    return len(q.data) - q.head
}

消息队列（RabbitMQ、Kafka）、操作系统任务调度、打印机排队、BFS 都依赖队列的 FIFO 特性。