Build a FIFO queue (push, pop, peek) using only two LIFO stacks.
Keep an in-stack for pushes and an out-stack for pops. On pop/peek, if the out-stack is empty, pour the entire in-stack into it (reversing order so the oldest element is on top). Each element is moved at most once, giving amortized O(1) per operation.
static class MyQueue {
Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
void push(int x) { in.push(x); }
int pop() { shift(); return out.pop(); }
int peek() { shift(); return out.peek(); }
private void shift() {
if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
}
}class MyQueue {
constructor() { this.inStack = []; this.outStack = []; }
push(x) { this.inStack.push(x); }
pop() { this._shift(); return this.outStack.pop(); }
peek() { this._shift(); return this.outStack[this.outStack.length - 1]; }
_shift() {
if (this.outStack.length === 0)
while (this.inStack.length) this.outStack.push(this.inStack.pop());
}
}class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x):
self.in_stack.append(x)
def pop(self):
self._shift()
return self.out_stack.pop()
def peek(self):
self._shift()
return self.out_stack[-1]
def _shift(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())This classic design question tests amortized analysis and shows how one data structure can be built from another — a common systems-design building block.
A candidate reverses both stacks on every pop, making each pop O(n). What is the amortized-O(1) refinement?