How do you implement a queue using two stacks?
Push new items onto an input stack. When you need to dequeue and the output stack is empty, pour everything from the input stack into the output stack, which reverses the order, then pop from the output stack.
Explain it simply
A stack reverses order: what goes in last comes out first. Reverse something twice and you get the original order back. That is the whole idea.
Keep two stacks. New items are pushed onto inbox. To remove the oldest item, look at outbox. If it is empty, move every item from inbox into outbox; the oldest item is now on top. Only refill outbox when it is empty, otherwise you would break the order.
Example
class MyQueue {
constructor() {
this.inbox = [];
this.outbox = [];
}
enqueue(x) {
this.inbox.push(x);
}
dequeue() {
if (this.outbox.length === 0) {
while (this.inbox.length) this.outbox.push(this.inbox.pop());
}
return this.outbox.pop();
}
}
const q = new MyQueue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
console.log(q.dequeue()); // Output: 1
q.enqueue(4);
console.log(q.dequeue()); // Output: 2
console.log(q.dequeue()); // Output: 3Complexity
enqueue O(1), dequeue amortized O(1), space O(n).
What to say in the interview
"I use an inbox stack for pushes and an outbox stack for pops. When the outbox is empty I transfer everything from the inbox, which reverses it into queue order. Each element moves at most twice, so enqueue is O(1) and dequeue is O(1) amortized."
Common mistakes
- Transferring on every dequeue, even when the outbox still has items, which scrambles the order.
- Saying dequeue is always O(1): a single call can be O(n), but the average over many calls is O(1).