Implement Queue Using Stacks — Amortized O(1) Two-Stack

Problem 253 · Implement Queue Using Stacks

Difficulty: Easy · Pattern: Two-Stack (inbox/outbox)

Intuition

inbox stack: accepts pushes. outbox stack: serves pops. When outbox is empty, transfer all from inbox. Each element moves at most once → amortized O(1).

Solutions

# Python
class MyQueue:
    def __init__(self): self.inbox = []; self.outbox = []
    def push(self, x): self.inbox.append(x)
    def _transfer(self):
        if not self.outbox:
            while self.inbox: self.outbox.append(self.inbox.pop())
    def pop(self): self._transfer(); return self.outbox.pop()
    def peek(self): self._transfer(); return self.outbox[-1]
    def empty(self): return not self.inbox and not self.outbox

// Java
class MyQueue {
    Deque<Integer> inbox = new ArrayDeque<>(), outbox = new ArrayDeque<>();
    public void push(int x) { inbox.push(x); }
    private void transfer() { if (outbox.isEmpty()) while (!inbox.isEmpty()) outbox.push(inbox.pop()); }
    public int pop() { transfer(); return outbox.pop(); }
    public int peek() { transfer(); return outbox.peek(); }
    public boolean empty() { return inbox.isEmpty() && outbox.isEmpty(); }
}

Complexity

push: O(1)
pop/peek: O(1) amortized