What is the minimum number of stacks of size n required to implement a queue…
2001
What is the minimum number of stacks of size n required to implement a queue of size n?
- A.
One
- B.
Two
- C.
Three
- D.
Four
Attempted by 110 students.
Show answer & explanation
Correct answer: B
The correct answer is Option B (Two). A single stack is LIFO, so it cannot by itself preserve FIFO order for a queue. With two stacks, enqueue operations push into the first stack. For dequeue, when the second stack is empty, all elements are moved from the first stack to the second stack; this reverses their order and exposes the oldest element on top. Thus two stacks of size n are sufficient, and one stack is not sufficient for a queue of size n.