Deviopath › TypeScript

Stable Priority Queue

Medium · Data Structures

Implement PriorityQueue<T>. The constructor receives a compare(a, b) function: a negative result means a comes out first. Any correct approach is fine (a binary min-heap is the classic one).

The queue must be **stable**: when compare returns 0, the item that was pushed earlier comes out first. (Hint: store an increasing sequence number next to every item.)

- push(item) adds an item.

- pop() removes and returns the first item, or undefined when empty.

- peek() returns the first item without removing it, or undefined.

- size() returns the number of items.

The driver runQueue(ops) is already written. It uses jobs ordered by priority (smaller first) and returns null for push, the job name (or null) for pop/peek, and the number for size.

Next: Generic LRU Cache