Design: a min stack and a queue using two stacks

Two small designs come up again and again in coding interviews, because a few lines of each test invariants and amortised reasoning. A min stack answers one extra question, which of its items is the smallest, in O(1), whatever has been pushed and popped. A queue using two stacks gives first-in, first-out order with nothing but two stacks: items go onto one and come off the other, and each item moves between them at most once, so every operation is O(1) amortised. This lesson states both problems in an original setting, shows the brute force for each and why it is too slow, and names what to notice before designing.

The problems: the cheapest fare and a queue of print jobs

Problem 1. A fare-comparison site keeps the result pages a traveller has opened on a stack: opening a page pushes its fare, and the Back button pops it. Beside the Back button the site shows the cheapest fare among the pages still on the stack. Support push(fare), pop(), top() and cheapest(), each in O(1), for up to 2 × 10⁵ operations with fares from 1 to 10⁶. pop, top and cheapest on an empty stack are errors.

For example, after pushing 5400, 4200 and 6100, cheapest() is 4200; after two pops it is 5400 again.

Problem 2. Build a first-in, first-out queue of print jobs with enqueue, dequeue and front, using only two stacks and their push, pop, peek and empty operations, for up to 2 × 10⁵ operations, each O(1) amortised.

For example, enqueue A, B and C, then dequeue: A comes out. Enqueue D, then dequeue three times: B, C and D.

The brute forces: scanning and pouring

The obvious answers work and are slow. cheapest() can scan the whole stack, O(n) per call. The queue can keep its items on one stack, oldest at the bottom, and for each dequeue pour everything onto the second stack, take the top, and pour everything back, O(n) per dequeue.

"""The two brute forces, with their work counted: scanning for the cheapest fare, and pouring stacks both ways."""


class ScanningMinStack:
    def __init__(self):
        self.items, self.steps = [], 0

    def push(self, fare):
        self.items.append(fare)

    def pop(self):
        return self.items.pop()

    def cheapest(self):
        self.steps += len(self.items)  # looks at every fare on the stack
        return min(self.items)


class PouringQueue:
    """Keeps the items in `stack`, oldest at the bottom; a dequeue pours everything onto `spare` and back."""

    def __init__(self):
        self.stack, self.spare, self.moves = [], [], 0

    def enqueue(self, item):
        self.stack.append(item)

    def dequeue(self):
        while self.stack:  # pour: the oldest item ends up on top of spare
            self.spare.append(self.stack.pop())
            self.moves += 1
        item = self.spare.pop()
        while self.spare:  # pour everything back
            self.stack.append(self.spare.pop())
            self.moves += 1
        return item


fares = ScanningMinStack()
for fare in [5400, 4200, 6100]:
    fares.push(fare)
print("cheapest of 5400, 4200, 6100:", fares.cheapest())
fares.pop()
fares.pop()
print("after two pops:", fares.cheapest())

q = PouringQueue()
for job in "ABC":
    q.enqueue(job)
print("dequeue order:", q.dequeue(), q.dequeue(), q.dequeue())
print()
print(f"{'n':>7} {'scans for n cheapest() after n pushes':>38} {'moves for n dequeues after n enqueues':>39}")
for n in [500, 1_000, 2_000]:
    s = ScanningMinStack()
    for i in range(n):
        s.push(i)
    for _ in range(n):
        s.cheapest()
    p = PouringQueue()
    for i in range(n):
        p.enqueue(i)
    for _ in range(n):
        p.dequeue()
    print(f"{n:>7,} {s.steps:>38,} {p.moves:>39,}")

cheapest of 5400, 4200, 6100: 4200
after two pops: 5400
dequeue order: A B C

      n  scans for n cheapest() after n pushes   moves for n dequeues after n enqueues
    500                                250,000                                 250,000
  1,000                              1,000,000                               1,000,000
  2,000                              4,000,000                               4,000,000

Both give the right answers, and both cost n² steps for n pushes followed by n queries or dequeues, as the counts show. At the stated 2 × 10⁵ operations that can mean about 10¹⁰ steps, far beyond what one second allows.

What to notice

For the fares: once a fare is on the stack, the cheapest fare at or below it never changes until it is popped, because nothing below it can change. For the print jobs: pouring one stack onto the other reverses it, which puts the oldest job on top, and once the jobs are in that order there is no reason to pour them back.

The min stack, in two designs Pro: opens with a Pro, Premium or Ultimate pass