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로 대기 건수를 바로 볼 수 있고, iterator는 조회용, drain()은 소비용으로 역할이 나뉜다.

주의할 점

이 구현은 FIFO만 남긴 최소 버전이다. 우선순위 큐나 임의 접근까지 다루지는 않는다. 단순한 대기열이면 이것으로 충분하지만, 취소, 우선순위, 중복 제거까지 필요하면 다른 자료구조가 더 잘 맞는다.