GATE CS 2012 Q35 — Arrays, Stacks and Queues

To understand the conditions for a circular queue of capacity $n-1$ implemented using an array of size $n$, let us trace the operations with a small example.

1. Queue Empty Condition

Initially, the queue is empty, and we are given that:

$$\text{REAR} = \text{FRONT} = 0$$

Since this is the starting state where no elements are present, the condition to detect an empty queue is:

$$\text{REAR} == \text{FRONT}$$

2. Queue Full Condition

Let the array size be $n = 4$. The capacity of the queue is $n - 1 = 3$ elements.

• Initial State: $\text{FRONT} = 0, \text{REAR} = 0$ (Queue is empty).
• Insert 1^st element: Stored at index $0$. $\text{REAR}$ is updated to $(0 + 1) \bmod 4 = 1$.
• Insert 2^nd element: Stored at index $1$. $\text{REAR}$ is updated to $(1 + 1) \bmod 4 = 2$.
• Insert 3^rd element: Stored at index $2$. $\text{REAR}$ is updated to $(2 + 1) \bmod 4 = 3$.

At this point, the queue has reached its maximum capacity of $3$ elements. The array index $3$ is left unused to distinguish the "full" state from the "empty" state.

If we try to insert another element, the next position for $\text{REAR}$ would be:

$$(\text{REAR} + 1) \bmod n = (3 + 1) \bmod 4 = 0$$

Since this value matches $\text{FRONT}$ (which is $0$), the queue is full. Thus, the condition for a full queue is:

$$(\text{REAR} + 1) \bmod n == \text{FRONT}$$

Conclusion

• $\text{full}$: $(\text{REAR} + 1) \bmod n == \text{FRONT}$
• $\text{empty}$: $\text{REAR} == \text{FRONT}$

This corresponds to Option A.