GATE CS 2004 Q3 — Arrays, Stacks and Queues

To utilize the array space efficiently, we should allow both stacks to grow dynamically into the shared space. This means one stack can occupy more than half of the array if the other stack is relatively small.

Let the array be $A[1 \ldots \text{MAXSIZE}]$.

• Stack 1 starts from the left end ($1$) and grows towards the right ($1, 2, 3, \ldots$). Its topmost element is pointed to by $top1$.
• Stack 2 starts from the right end ($\text{MAXSIZE}$) and grows towards the left ($\text{MAXSIZE}, \text{MAXSIZE}-1, \ldots$). Its topmost element is pointed to by $top2$.

Since the stacks grow towards each other, the array becomes completely full when there are no empty slots left between $top1$ and $top2$. Since $top1 < top2$, this boundary condition occurs when the two pointers are adjacent:

Analysis of Options:

• Option A & C: These force a static division of space (e.g., limiting each stack to half the array size), which defeats the purpose of efficient space utilization.
• Option B: $top1 + top2 = \text{MAXSIZE}$ is incorrect. For example, if $\text{MAXSIZE} = 10$, $top1 = 3$, and $top2 = 7$, then $top1 + top2 = 10$, but slots $4, 5,$ and $6$ are still empty.
• Option D: $top1 = top2 - 1$ correctly identifies that the two stacks have met and no free space remains.