Interview preparation
Implement Queue using Stacks
1Problem statement
Implement a FIFO queue using only two stacks. Support push(x), pop(), peek() and empty(). Each operation should be amortized O(1).
2Examples
3Constraints
- 1 ≤ x ≤ 9
- At most 100 calls
- pop and peek are only called on a non-empty queue.
4Approaches
Approach 1
Brute Force
On every push, move everything to the second stack, push, and move it all back.
Approach 2
Better
Transfer on every pop/peek (always move all back afterwards).
Approach 3
Optimal: Lazy transfer
Push onto `in`. For pop/peek, only when `out` is empty move all of `in` into `out` (reversing order). Each element moves at most once.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
class MyQueue {
constructor() {
this.inStack = [];
this.outStack = [];
}
push(x) {
this.inStack.push(x);
}
shift() {
if (this.outStack.length === 0) {
while (this.inStack.length > 0) this.outStack.push(this.inStack.pop());
}
}
pop() {
this.shift();
return this.outStack.pop();
}
peek() {
this.shift();
return this.outStack[this.outStack.length - 1];
}
empty() {
return this.inStack.length === 0 && this.outStack.length === 0;
}
}
const q = new MyQueue();
q.push(1);
q.push(2);
console.log(q.peek());
console.log(q.pop());
console.log(q.empty());
6Complexity
Time
O(1) amortized
Space
O(n)
7Visual walkthrough
- 1.push 1, push 2 → in = [1, 2], out = []
- 2.peek: out empty → move → out = [2, 1] (top is 1) → returns 1
- 3.pop → returns 1, out = [2]
- 4.empty → in and out not both empty → false
Related visualization (Queue Enqueue and Dequeue) — shows the core data-structure operations this solution relies on:
Size 0 / 4 · FIFO — values leave in the same order they arrived
A queue is First-In-First-Out (FIFO): enqueue adds at the rear, dequeue removes from the front. This circular-array queue wraps the rear pointer around to reuse freed slots.