GATE CS 2001 Q2.16 — Arrays, Stacks and Queues

To implement a queue (which follows First-In-First-Out or FIFO order) using stacks (which follow Last-In-First-Out or LIFO order), we need to reverse the order of the elements.

• With one stack: We cannot reverse the order of elements dynamically to support both enqueue and dequeue operations in a FIFO manner. Thus, one stack is insufficient.
• With two stacks ($S_1$ and $S_2$): We can successfully simulate a queue of size $n$:
  • Enqueue: Push the incoming element onto $S_1$.
  • Dequeue: If $S_2$ is empty, pop all elements from $S_1$ and push them one by one into $S_2$ (this reverses their order, making the oldest element sit at the top of $S_2$). Then, pop the top element from $S_2$. If $S_2$ is not empty, simply pop the top element from $S_2$.

Since the maximum number of elements in the queue at any time is $n$, two stacks of size $n$ are sufficient to handle all operations without overflow.

Therefore, the minimum number of stacks required is two.