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

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

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