TypeScript-Implementierung von yocto-queue

TypeScript-Neuimplementierung der schlanken Queue yocto-queue.

Wenn eine Queue als simples Array beginnt, landet man schnell bei wiederholten shift()-Aufrufen. Für kleine Skripte reicht das, aber in Concurrency-Limitern und Task-Schedulern will ich diese Verantwortung sauber isolieren. yocto-queue ist genau diese Minimalform und lässt sich leicht übernehmen, wenn ich das Verhalten ohne zusätzliche Abhängigkeit haben will.

Originalimplementierung

/**
 * @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
  }
}

Wofür es gut passt

Die Struktur passt gut zu Promise-Konkurrenzkontrolle, Breadth-First Search und Warteschlangen vor Worker-Jobs. Man kann das auch mit Arrays schreiben, aber als eigene Queue bleibt der aufrufende Code deutlich lesbarer.

Warum diese Form sinnvoll ist

Weil head und tail getrennt gehalten werden, hängen enqueue() und dequeue() nicht vom Umsortieren eines Arrays ab. Der size-Getter macht die Anzahl wartender Einträge sichtbar, und iterator sowie drain() trennen Lesen und destruktiven Verbrauch sauber.

Hinweise

Das hier ist absichtlich nur eine minimale FIFO-Queue. Prioritäten oder Random Access sind nicht Teil des Entwurfs. Wenn ich nur eine kleine Warteschlange brauche, reicht das völlig. Wenn zusätzlich Prioritäten, Abbruch oder Deduplizierung nötig sind, ist eine andere Struktur die bessere Wahl.