Find number of elements in a Circular Queue

Question

How do I find the number of items in a circular queue? |front - rear| doesn't always work.

Is there one formula to know how many elements are there in a circular queue using front, rear and size of the array?

Solution 1

actually the size would be,

size = front > rear ? (MAX - front + rear + 1) : (rear - front + 1);

or one can go for a generic formula:

size = abs(abs(MAX - front) - abs(MAX -rear));//this works in every situation

Solution 2

Assuming you implement it using an array with size N so there are pointers pointing to the front and rear. Use the following formula:

size = front > rear ? (front - rear) : (front+N -  rear);

Solution 3

 Pointer1 = head; // (your node)
 count = 0;


 if( Pointer1 != NULL )
 {
   count = 1;
   Pointer2 = Pointer1->Next;
   while ( Pointer2 != NULL && Pointer2 != Pointer1 )
   {
     count++;
     Pointer2 = Pointer2->Next;
   }
 }

 return count;

Solution 4

Assuming you are using array of size N for queue implementation, then size of queue would be size = (N-front + rear) mod N.

Solution 5

None of the formulas take into account the empty (zero) case. This will give you the number of free bytes available in the queue:

FreeSpace = (printRdQue == printWrQue) ? PRINT_QUEUE_SIZE :
           (PRINT_QUEUE_SIZE - printWrQue + printRdQue) % PRINT_QUEUE_SIZE;

View more solutions

Comments

[Robert Reinhard]

Sorry the formatting is off - I'm new to this. The 'count = 0;' should be on a separate line, as should the nested if statement lines...

[leppie]

Or otherwise known as Floyd's cycle detection routine.

[Pranjal Bikash Das]

please put a little description.

[CodeWithVikas]

can you explain it ?

[Shivansh Rajolia - HeLleR]

This is wrong. Does not work for ciircular queue. Take any example where f>r. This formula gives wrong results.