Implement Queue using Stacks
Problem Statement
Implement a queue using two stacks. The queue should support push, pop, peek, and empty operations.
Example: push(1), push(2), pop() → returns 1
Approach 1: Brute Force
Explanation: On push, move all elements to auxiliary stack, insert, and restore order.
Time Complexity: push O(n), pop O(1)
Space Complexity: O(n)
stack1 = empty
stack2 = empty
push(x):
while stack1 not empty:
stack2.push(stack1.pop())
stack1.push(x)
while stack2 not empty:
stack1.push(stack2.pop())
pop(): return stack1.pop()
peek(): return stack1.top()
empty(): return stack1 is empty
💡 Think: Rebuild order on every push so pops are O(1).
Approach 2: Lazy Transfer (Better)
Explanation: Push into stack1; pop/peek from stack2; transfer only when stack2 empty.
Time Complexity: Amortized O(1) per operation
Space Complexity: O(n)
stack1 = empty
stack2 = empty
push(x): stack1.push(x)
pop():
if stack2 empty:
while stack1 not empty:
stack2.push(stack1.pop())
return stack2.pop()
peek(): similar to pop but return stack2.top()
empty(): return stack1 empty and stack2 empty
💡 Think: Push to in-stack; only pour to out-stack when needed.
Approach 3: Recursive Pop (Alternative)
Explanation: Use recursion to reverse stack1 temporarily during pop.
Time Complexity: O(n) per pop
Space Complexity: O(n) recursion stack
push(x): stack1.push(x)
pop():
if stack1 size == 1:
return stack1.pop()
temp = stack1.pop()
res = pop()
stack1.push(temp)
return res
peek(): similar, but return last element instead of popping
empty(): stack1 empty
💡 Think: Use recursion to reverse temporarily for front retrieval.