Implement Queue using Stacks

Implement a FIFO queue using only stack operations (push, pop, peek, empty). A single stack reverses the order of everything; two stacks can reverse it back.

The key insight: stack LIFO plus LIFO is FIFO. Keep an in stack for pushes and an out stack for pops. Pushing appends to in. Popping drains in — which reverses the elements — onto out, then pops the top of out, which is now the oldest element. The drain happens lazily: only when out is empty, so elements move between stacks exactly once each, making the whole sequence amortized O(1) per operation.

Approach in steps:

1. push(x): append to in.
2. pop()/peek(): if out is empty, move every element of in onto out; then pop/peek out.
3. empty(): both stacks must be empty.

class MyQueue:
    def __init__(self):
        self.in_st = []
        self.out_st = []
 
    def push(self, x):
        self.in_st.append(x)
 
    def _shift(self):
        if not self.out_st:
            while self.in_st:
                self.out_st.append(self.in_st.pop())
 
    def pop(self):
        self._shift()
        return self.out_st.pop()
 
    def peek(self):
        self._shift()
        return self.out_st[-1]
 
    def empty(self):
        return not self.in_st and not self.out_st

Time is O(1) amortized per op — each element is moved twice total; space O(n).

Trickiest edge case: interleaved pushes and pops. After push(1), push(2), pop(), push(3), in holds [3] and out holds [2]; the next pop() must take 2 without touching in. That is exactly why _shift only runs when out is empty.