We have implemented a circular queue(capacity: (n – 1)) using an array of size n

Question

We have implemented a circular queue(capacity: (n – 1)) using an array of size n.

Assume that the insertion and deletion operation using REAR and FRONT as array index, respectively.

Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are (choose one):

Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

Explanation / Answer

Answer : Option B.

Explanation:

Keeping this is mind, let's start to search the solution. Initially, both front and rear = 0. We insert 1 element, so rear = 1, front is still 0. Front never change until we perform dequeue() operation.

Now, we keep adding the elements, so rear gets incremented. The array size is n. So, at first, rear = 0, then when we add elements till the end, rear becomes n-1...

Now, REAR is pointing to the last element which is having value n-1. The next of the last is first node and if there is not any value removed from the queue, front is still 0. So, if FRONT = 0 and REAR = n-1, the queue is full. There is not exactly this thing written in the options, but you can think of this another way. REAR = n-1 then REAR + 1 = n and so (REAR + 1) mod n = 0 which is the value of FRONT.

So, the condition required for full circular queue is : (REAR + 1) mod n == FRONT.

The circular queue is empty initially, so at that time, FRONT == REAR.

Actually, the only time when circular queue is empty is FRONT == REAR. Because, say for example, you added 3 elements in the queue. Initially, FRONT = REAR = 0. Now, after insertion of 3 elements, FRONT = 0 and REAR becomes 2. This queue will become empty when 3 elements are removed, i.e. when FRONT will reach to 2 because deleting 1 element means incrementing of FRONT by 1.

So, whenever FRONT == REAR, the queue is empty.

So, the condition required for empty circular queue is : REAR == FRONT.

This means option B is the correct option.

Do comment if there is any query. Thank you. :)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.