Queue With Minimum

Design a class MinQueue: a first-in-first-out queue of integers that can report its minimum element in constant time. Implement it using two stacks (Python lists used only with append and pop), not a deque and not a list scan.

• MinQueue(): create an empty queue.
• push(x): add x at the back.
• pop(): remove and return the front element.
• front(): return the front element without removing it.
• min_val(): return the smallest element in the queue.

pop, front and min_val are only called on a non-empty queue.

Examples

Input:  ops  = ["MinQueue", "push", "push", "push", "min_val", "pop", "min_val", "pop", "min_val", "front"]
        args = [[], [3], [1], [2], [], [], [], [], [], []]
Output: [None, None, None, None, 1, 3, 1, 1, 2, 2]

Constraints

• At most 2 * 10**4 operations
• Target: amortised O(1) per operation

Goals

• Build a queue from two stacks
• Augment each stack with running minimums so min is O(1)
• Understand why the transfer step is amortised O(1)