Implémentation TypeScript de yocto-queue

Réimplémentation TypeScript de la file légère yocto-queue.

Quand une file commence comme un simple tableau, on finit vite par empiler les appels à shift(). Pour un petit script ce n’est pas grave, mais dans un limiteur de concurrence ou un scheduler il vaut mieux isoler clairement la responsabilité de file. yocto-queue correspond à ce minimum et se copie facilement dans un projet quand on veut ce comportement sans ajouter de dépendance.

Implémentation originale

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

Quand l’utiliser

Cette implémentation convient bien à un limiteur de concurrence, un parcours en largeur, ou une file d’attente avant l’envoi vers des workers. On peut écrire la même chose avec un tableau, mais une vraie structure de file rend le code appelant plus lisible.

Pourquoi cette forme fonctionne

Comme l’implémentation garde des pointeurs head et tail séparés, enqueue() et dequeue() ne dépendent pas d’un réindexage de tableau. Le getter size expose aussi facilement le volume en attente, tandis que iterator et drain() séparent la lecture de la consommation destructive.

Notes

Cette version reste volontairement minimale. Elle ne gère ni priorité ni accès aléatoire. Si une FIFO simple suffit, cela fait le travail. Si vous avez aussi besoin d’annulation, de priorité ou de déduplication, mieux vaut partir sur une autre structure.