Design a queue that reports its minimum

Question

A processing pipeline holds quotes in arrival order: new quotes join the back, the oldest are served from the front, and at any moment you need the smallest quote still in flight. That is a min-queue: enqueue, dequeue (FIFO), and get_min, all in amortized $O(1)$ .

q = MinQueue()
q.enqueue(5); q.enqueue(3); q.enqueue(7)
q.get_min() -> 3
q.dequeue() -> 5        # FIFO: oldest leaves first
q.get_min() -> 3        # 3 and 7 remain

A min-stack is not enough on its own, a queue removes from the opposite end. The classic build is two min-stacks.

Accepted Answer

Simulate a queue with an in stack (takes new items) and an out stack (serves them). Each stack also carries a running minimum at every level, just like a min-stack. When out is empty, pour in into out, which reverses order so the oldest sits on top and FIFO holds. The overall minimum is the smaller of the two stack minima. Tracing: after enqueue(5, 3, 7), in = [(5,5),(3,3),(7,3)], so getmin is 3. dequeue finds out empty, pours everything over to out = [(7,7),(3,3),(5,3)], and pops the top (5,3), returning 5, the oldest. Now getmin reads out[-1][1] = 3, correct for the remaining 3 and 7. Every…

Design a queue that reports its minimum

Your answer

More Coding questions