TypeScriptでyocto-queue実装

軽量なキュー実装yocto-queueをTypeScriptで再実装した。

配列でキューを雑に書くと、すぐに shift() を呼び始める。小さなスクリプトならそれでも済むが、並行数制御やタスク待ち行列の内部実装では、キューの責務を分けておいた方が読みやすい。yocto-queue はそのための最小構成で、依存を増やしたくない時にそのまま持ち込みやすい。

元実装

/**
 * @see {@link https://github.com/sindresorhus/yocto-queue/blob/main/index.js}
 */

interface QNode<T> {
  value: T;
  next: QNode<T> | undefined;
}

interface Queue<T> {
  enqueue(value: T): void;
  dequeue(): T | undefined;
  peek(): T | undefined;
  clear(): void;
  readonly size: number;
  [Symbol.iterator](): Generator<T, void, unknown>;
  drain(): Generator<T | undefined, void, unknown>;
}

function createNode<T>(value: T): QNode<T> {
  return { value, next: undefined };
}

function createQueue<T>(): Queue<T> {
  let head: QNode<T> | undefined;
  let tail: QNode<T> | undefined;
  let size: number;

  const clear = (): void => {
    head = tail = undefined;
    size = 0;
  }

  clear();

  const enqueue = (value: T): void => {
    const node = createNode(value);
    if (head) {
      tail && (tail.next = node);
      tail = node;
    } else {
      head = node;
      tail = node;
    }

    size++;
  }

  const dequeue = (): T | undefined => {
    const current = head;
    if (!current) return;
    head = head?.next;
    size--;
    return current.value;
  }

  const peek = (): T | undefined => {
    return head?.value;
  }

  function* iterator(): Generator<T, void, unknown> {
    let current = head;
    while (current) {
      yield current.value;
      current = current.next;
    }
  }

  function* drain(): Generator<T | undefined, void, unknown> {
    while (head) {
      yield dequeue();
    }
  }

  return {
    enqueue,
    dequeue,
    peek,
    clear,
    get size() {
      return size;
    },
    [Symbol.iterator]: iterator,
    drain
  }
}

使いどころ

Promise の並行数制御、BFS、ワーカー投入前の待ち行列のように、末尾追加と先頭取り出しを繰り返す場面に向く。配列でも実装できるが、キューとして切り出しておくと呼び出し側の意図が見えやすい。

実装のポイント

head と tail を分けて持つので、enqueue() と dequeue() が配列の詰め直しに依存しない。size getter があるので pending 件数を外から見やすく、iterator は観察用、drain() は破壊的な消費用と役割も分かれている。

注意点

これは FIFO だけに絞った最小実装。優先度付きキューやランダムアクセスまでは扱わない。必要なのが単純な待ち行列だけならこれで十分だが、優先度、キャンセル、重複排除まで欲しいなら別の構造に寄せた方が楽。

実務メモ

このスニペットは、typescript、data-structure、queue の周辺で同じ操作や判定を毎回書きたくない時に向く。小さな補助として切り出しておくと、呼び出し側では意図だけを追いやすい。

逆に、分岐や前提条件が増えて責務が膨らむなら、1本のスニペットに詰め込まない方がよい。手順と helper を分けるか、役割ごとに切り出す方が保守しやすい。