Beginner LevelData Structures & Algorithms
How do you implement a Queue using two Stacks?
ā Interview Prompt: Implement a FIFO Queue using only two LIFO Stacks with amortised O(1) enqueue and dequeue operations.
Idea: Use two stacks ā inbox and outbox.
ā¢
Enqueue: Always push onto
inbox. $O(1)$.ā¢
Dequeue: If
outbox is empty, pop ALL from inbox into outbox (reverses order). Pop from outbox. Amortised $O(1)$ ā each element moves at most once.This is a classic problem demonstrating amortised analysis. Each element is pushed and popped exactly twice across both stacks.
Code Implementation Example
typescript
class MyQueue<T> {
private inbox: T[] = [];
private outbox: T[] = [];
enqueue(val: T): void {
this.inbox.push(val); // O(1)
}
dequeue(): T | undefined {
if (this.outbox.length === 0) {
while (this.inbox.length > 0) {
this.outbox.push(this.inbox.pop()!); // transfer
}
}
return this.outbox.pop(); // O(1) amortised
}
peek(): T | undefined {
if (this.outbox.length === 0) this.dequeue();
return this.outbox[this.outbox.length - 1];
}
}š”Queue implemented with two stacks ā amortised O(1) dequeue.
šÆ Interview Key Takeaway
Two-stack queue is a classic amortised O(1) design. Interviewers use it to test understanding of amortised analysis and data structure composition.
#DSA#Queue#Stack#Amortised#Beginner
Back to all Data Structures & Algorithms Questionsā