Consider a normal array implementation of a queue. We’ll have $2$ pointers $\text{Front}$ and $\text{Rear}$ where $\text{Front}$ points to the first element of the queue and $\text{Rear}$ points to the next free space. When queue is full $\text{Rear}$ points to $\text{NULL}.$
The below figure depicts the Queue full condition and then a $\text{DEQUEUE}$ is performed which removes element $4.$ In the second part of the figure, all elements are shifted by one position or else we won’t be able to make use of the free space for the next element to be inserted. So, this means $\Theta(n)$ operations for $\text{DEQUEUE}$ where as $\text{ENQUEUE}$ can be done in $O(1).$
But we can in fact do both $\text{ENQUEUE}$ and $\text{DEQUEUE}$ operations in $O(1)$ and fully utlizie the array space by smartly using the $\text{Front}$ and $\text{Rear}$ pointers as shown in $\text{DEQUEUE}_{\text{opt}}.$ If $\text{MAX}$ denote the total size of the array, here,
- for $\text{ENQUEUE}$
- $\text{Rear} = (\text{Rear} + 1) \mod \text{MAX}$
- for $\text{DEQUEUE}$
- $\text{Front} = (\text{Front} + 1) \mod \text{MAX}$
- Condition for $\text{QUEUE}$ Empty
- $\text{Front} == \text{NULL}$ (Whenever after a $\text{DEQUEUE}$ operation $\text{Front}$ becomes equal to $\text{Rear}$ it means Queue is now empty and we make $\text{Front} = \text{NULL}$ to mark this condition as $\text{Rear} = \text{Front}$ is the condition we use for checking if $\text{QUEUE}$ is full
- Condition for $\text{QUEUE}$ Full
- $\text{Rear} == \text{NULL}$
So, correct answer: A.