Condition required to detect queue full and queue empty-quiz question asked in interviews
For the operations given below in a circular queue of (n-1) capacity is implemented with an array of n elements. Condition required to detect queue full and queue empty are:
//initializing indexint FRONT=0int REAR=0Insertion and deletion is carried out using FRONT and REAR as array indices
A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Correct answer: Option A
Suppose we start filling the queue.
Let the maxQueueSize ( Capacity of the Queue) is 4.
So the size of the array which is used to implement
this circular queue is 5, which is n.
In the beginning when the queue is empty, FRONT and REAR
point to 0 index in the array.
REAR represents insertion at the REAR index.
FRONT represents deletion from the FRONT index.
enqueue("a"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 1)
enqueue("b"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 2)
enqueue("c"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 3)
enqueue("d"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 4)
Now the queue size is 4 which is equal to the maxQueueSize.
Hence overflow condition is reached.
Now, we can check for the conditions.
When Queue Full :
( REAR+1)%n = (4+1)%5 = 0
FRONT is also 0.
Hence ( REAR + 1 ) %n is equal to FRONT.
When Queue Empty :
REAR was equal to FRONT when empty ( because in the starting
before filling the queue FRONT = REAR = 0 )
Hence Option A is correct.
Thanks for Reading
Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.