Implement Queue using Stacks

👶 The 5-Year-Old Summary

You only have stacks (like a stack of plates - only top one accessible), but you need to build a queue (like a line - first in, first out). How would you do it?

🎮 Interactive Visualizer

Watch how we simulate a queue using two stacks!

Input Stack (new items)

Output Stack (ready to dequeue)

🧠 The Brain Hack

Use two stacks! When enqueueing, push to input stack. When dequeueing, if output stack is empty, transfer all from input (reversing order!). The bottom of input becomes the front of queue!

💻 The Clean Solution

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []
    
    def push(self, x):
        # Push to input stack
        self.input.append(x)
    
    def pop(self):
        # If output empty, transfer from input
        self._transfer()
        return self.output.pop()
    
    def peek(self):
        self._transfer()
        return self.output[-1]
    
    def empty(self):
        return not self.input and not self.output
    
    def _transfer(self):
        # Move all from input to output (reverses order!)
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

# Try it!
q = MyQueue()
q.push(1)
q.push(2)
print(q.peek())    # 1
print(q.pop())     # 1
print(q.pop())     # 2

Amortized Time: O(1) for all operations!

Space: O(n) - two stacks