双端队列的实现

功能说明

Deque 支持在头部与尾部插入、删除和查看元素，push 与 pop 都是摊还 O(1)，适合任务调度、回退历史、滑动窗口和广度优先搜索。内部使用环形缓冲区，避免数组 unshift 带来的整体搬移。toArray 按从前到后的顺序返回快照，size 暴露当前元素数量，空队列的 pop 返回 undefined。

关键代码

缓冲区初始容量为八，head 指向队首，size 记录有效元素数，尾部位置由 head 加 size 对容量取模得到。pushFront 先把 head 向前回绕一格再写入；popBack 先减少 size 再计算原尾部下标。扩容时按双倍容量创建新数组，从旧 head 开始逐项复制，并把 head 归零。删除位置会写入 undefined，帮助旧引用被回收。

使用注意

容量只增不减，长时间运行且元素数量波动大时可能占用较多内存，需要收缩策略时应自行实现重建。pop 返回 undefined 无法区分空队列与真实 undefined 元素，类型敏感场景可先检查 size。环形缓冲区的索引运算对容量有依赖，不要在外层直接修改内部数组。该实现不是线程安全的，Worker 之间需要消息传递。

验证方式

测试两端交替 push 与 pop，断言顺序符合后进先出或先进先出。构造跨越缓冲区边界的操作序列，验证回绕索引正确。持续 push 触发多次扩容，确认 toArray 顺序不变。测试空队列的 peek 与 pop、size 变化、单元素以及大量元素。最后检查 push 返回实例本身，且 toArray 的修改不会影响内部状态。

代码示例

// Double-ended queue backed by a growable ring buffer.
export class Deque {
  #buffer = new Array(8);
  #head = 0;
  #size = 0;

  pushBack(value) {
    this.#ensure(this.#size + 1);
    this.#buffer[(this.#head + this.#size) % this.#buffer.length] = value;
    this.#size += 1;
    return this;
  }

  pushFront(value) {
    this.#ensure(this.#size + 1);
    this.#head = (this.#head - 1 + this.#buffer.length) % this.#buffer.length;
    this.#buffer[this.#head] = value;
    this.#size += 1;
    return this;
  }

  popFront() {
    if (this.#size === 0) return undefined;
    const value = this.#buffer[this.#head];
    this.#buffer[this.#head] = undefined;
    this.#head = (this.#head + 1) % this.#buffer.length;
    this.#size -= 1;
    return value;
  }

  popBack() {
    if (this.#size === 0) return undefined;
    this.#size -= 1;
    const index = (this.#head + this.#size) % this.#buffer.length;
    const value = this.#buffer[index];
    this.#buffer[index] = undefined;
    return value;
  }

  peekFront() {
    return this.#size > 0 ? this.#buffer[this.#head] : undefined;
  }

  peekBack() {
    return this.#size > 0
      ? this.#buffer[(this.#head + this.#size - 1) % this.#buffer.length]
      : undefined;
  }

  get size() {
    return this.#size;
  }

  toArray() {
    const result = [];
    for (let index = 0; index < this.#size; index += 1) {
      result.push(this.#buffer[(this.#head + index) % this.#buffer.length]);
    }
    return result;
  }

  #ensure(capacity) {
    if (capacity <= this.#buffer.length) return;
    const next = new Array(this.#buffer.length * 2);
    for (let index = 0; index < this.#size; index += 1) {
      next[index] = this.#buffer[(this.#head + index) % this.#buffer.length];
    }
    this.#buffer = next;
    this.#head = 0;
  }
}