Applied GATE test series

Question

Que Consider a circular queue which is of capacity 100 elements and is implemented on an array a[0...99], at a particular instant the front pointer is pointing to index 20 and the rear is pointing at index 10  the number of elements present in the queue is.

   

• A. 10
• B. 90
• C. 91
• D. None 

 

Comments

Answer should be 90

As rear point to the index which is available for enqueue And front point to the index which should be popped for dequeue

SO no of elements  →  20 to 99 + 0 to 9  → 80 + 10  → 90

---

total element = 20-99+0to 10 -→ 91 elements in circular queue.

---

Exactly !!! I also solved it in the same way but the answer given is 91.

This is what they have mentioned in the explanation :

”In the question, it is mentioned that we have and arrange ranging from index 0 to 99 and the size of the queue is 100, for a circular queue there are two possible implementations, one is with array size n and queue size n and another with array size n and queue size n-1, in the first case the tail/rear points to the element last inserted and not the location to insert the next element. Hope it is clear, with this in mind the number of elements which are in the circular queue is 91.”

As far as I understood from this explanation they are also solving it in the same way but i don’t know how their answer is coming out to be 91. May be they are also including the element pointed by FRONT, but what i have studied is that first we increment the FRONT pointer and then delete the element pointed by it. So the element pointed by FRONT should not be considered. 

Please do mention if you can understand something different from their explanation.

---

we can say it really depends on the implementation.

Some info regarding elements in circular queue

https://gateoverflow.in/133910/%23number-elements-circular-queues-and-simple-queues-%23doubt

---

https://gateoverflow.in/1756/gate2012-35

see here the gate question mentions that the size of array is n and that of queue is n-1.So here rear should point to the empty location.(next of the last inserted element).

 

But the question here tell that the size of array is 100 and size of queue is also 100. so here the rear should point to the last inserted element.and the front will point  to the element to be deleted.

so total element is N-front+rear+1 if (front > rear). which is 91 here.

---

@Sahil91 Thanks for the reply.

My doubt was actually related to Front pointer. I understand what is happening with the rear pointer. But as u mentioned that front will point to the element which is to be deleted. I didn’t count this element pointed by front bcoz i am assuming incrementing front and deleting the element as a single operation which usually happens. But i think according to the answer given element pointed by the front pointer is also counted that makes the total element as 91.

But isn’t this approach little ambiguous ? i mean it should be mentioned in the question clearly that the element pointed by front should also be counted otherwise there can be different interpretations of the question.

Btw how did u infer from the language of the question that element pointed by front is also counted. Please do mention.

---

@GATE2021_ayush Are u counting the element pointed by front pointer as well ?

---

@tourist

AFAIK in all scenarios front pointer will point to the element to be deleted so we have to count it.

In Exam I also did this wrong.

---

@Sahil91 Ok got it.Thanks man !!!

Answer 1

circular queue capacity 100 elements and is implemented on an array a[0...99],  see we have 100 elements in queue and we are using 100 array index in this situation rear must be pointing to the last element of array.

If circular queue capacity 100 elements and is implemented on an array a[0...100] here we have 100 element and we are using 101 index then here rear may point to the location where new element can be inserted.

Front 20 and Rear 10 and capacity is same as array size so rear is pointing to last element of array . so from 11 to 19(9 location is empty) so total element present is 100-9=91.