Build a first in, first out queue MyQueue using only two stacks. Support push(x) (add to the back), pop() (remove and return the front), peek() (return the front) and empty(). You may only use standard stack operations: push to top, pop or peek from top, size and is empty. pop and peek are only called on a non-empty queue.
- 1 <= x <= 9
- At most 100 calls in total
- pop and peek are always valid
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force moves every element to the second stack and back on each pop, which is O(n) per operation. Notice that after pouring in into out once, the top of out is the oldest element, and the rest of out is already in queue order. So we only need to pour when out runs empty. Each element is moved from in to out at most once in its lifetime, which makes every operation O(1) amortised.
Algorithm
push(x): push onto theinstack.peek(): ifoutis empty, pop everything frominand push it ontoout; then return the top ofout.pop(): call the same transfer logic, then pop fromout.empty(): return true only when both stacks are empty.
O(1) amortised per operationSpace: O(n)out still has items, or you break the order. Be ready to explain the word amortised: a single pop can cost O(n), but n operations cost O(n) in total.class MyQueue: def __init__(self): self.inp = [] # receives pushes self.out = [] # top = front of the queue def push(self, x: int) -> None: self.inp.append(x) def _transfer(self): # Refill out only when it is empty, so each element moves once. if not self.out: while self.inp: self.out.append(self.inp.pop()) def pop(self) -> int: self._transfer() return self.out.pop() def peek(self) -> int: self._transfer() return self.out[-1] def empty(self) -> bool: return not self.inp and not self.out