Designing with stacks (min stack, queue via stacks)

A min stack supports push, pop, top and get_min, all in O(1). Scanning for the minimum would be O(n), so instead each entry remembers the minimum of everything at or below it. When you pop, the minimum of the rest is already stored in the new top.

A queue built from two stacks uses an inbox for pushes and an outbox for pops. When the outbox is empty, move everything from the inbox to the outbox, which reverses the order so the oldest item ends up on top. Each element is moved at most once, so pushes and pops are O(1) amortised.

1. 1Min stack: push (x, min(x, current min)). get_min reads the min stored at the top. pop removes the pair, so the previous minimum comes back automatically.
2. 2Space-saving variant: keep a second stack that only stores a value when it is less than or equal to the current minimum, and pop it when the popped value equals it. Using 'less than or equal' handles duplicates of the minimum.
3. 3Queue via two stacks: push always goes to inbox. pop and peek use outbox; if the outbox is empty, pop everything from inbox into outbox first.
4. 4Why amortised O(1): every element is pushed to the inbox once, moved to the outbox once, and popped once, about 3 operations in total, even though a single pop may move many elements.
5. 5Stack via queues (the reverse question): after enqueueing x, rotate the queue by dequeuing and re-enqueueing the other n - 1 elements, so x is at the front. Push is O(n), pop is O(1).

class MinStack:
    def __init__(self):
        self.items = []                  # pairs: (value, min so far)
    def push(self, x):
        low = min(x, self.items[-1][1]) if self.items else x
        self.items.append((x, low))
    def pop(self):
        return self.items.pop()[0]
    def top(self):
        return self.items[-1][0]
    def get_min(self):
        return self.items[-1][1]


class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
    def push(self, x):
        self.inbox.append(x)
    def peek(self):
        if not self.outbox:              # refill only when empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]
    def pop(self):
        self.peek()
        return self.outbox.pop()
    def empty(self):
        return not self.inbox and not self.outbox

MinStack: all operations O(1), space O(n) for the pairs. MyQueue: push O(1); pop and peek O(1) amortised, O(n) worst case for a single call that refills the outbox. Callers should check empty() before pop or peek.

Cost: Min stack: O(1) for every operation, O(n) space. Queue via two stacks: O(1) amortised per operation, O(n) worst case for one pop, O(n) space.