CODEWITHSUNDEEP
queuecircular-list
john
john

Reputation: 79

Find number of elements in a Circular Queue

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?

Upvotes: 7

Views: 48021

Answers (15)

Samarendra Jee
Samarendra Jee

Reputation: 1

return (!isEmpty()   ? (m_front>m_rear) ? (m_capacity + m_rear - m_front) + 1 : m_rear - m_front + 1 : (m_rear - m_front));
enter code here

Upvotes: 0

Shruti Sharma
Shruti Sharma

Reputation: 45

Assuming you have are implementing a queue using a circular array A[0, n-1], where the (n-1)th index used to store the full/empty condition, the formula would be:

Number of elements = { rear-front + 1 , if rear==front

                 { rear-front + n , otherwise

We'll be moving the queue clockwise at each enqueue or dequeue.

Upvotes: 0

Abhishek Dutt
Abhishek Dutt

Reputation: 1437

The easiest way to count the number of elements in the circular queue is:

if front > rear(i.e. front is ahead than rear) Just count the number of empty spaces in between

front - (rear+1)

else if front < rear:

rear - front + 1

A C program if you need to:

    int find_ele(int total,int front,int rear){
         if(rear < front ) {  \\1st case
int res =    front - rear + 1;
return (total-res);}

else{
      return (rear - front + 1);
}
}

Upvotes: 0

Dae Hyun
Dae Hyun

Reputation: 35

no. of elements = (rear + MAX_SIZE - front) % MAX_SIZE + 1

Upvotes: 0

user913359
user913359

Reputation: 660

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

Upvotes: 2

user10802680
user10802680

Reputation: 1

What do you need to implement a circular queue ?

Answer: you will need front and rear nodes + list of items + count_items.

Of course it is only implemented like this when the queue is finite, when talking about

dynamic allocation it will be different.

Take a look at an example in C Language, 

typedef struct
{

TYPE items[MAXSIZE];

TYPE front;

TYPE rear;

int count_items;

} QUEUE;

This will assure you the exact amount of items are currently exist in the queue.

When you want to insert an item to the queue, you will simply increment rear and count_items, and when you want to remove an item from the queue, you will simply decrement rear and count_items.

Upvotes: 0

Ayad Albadri
Ayad Albadri

Reputation: 1

if (Cqueue_front>Cqueue_rear) cout<<" The number of queue items are : "<

Upvotes: 0

Aziz Chafik
Aziz Chafik

Reputation: 36

int lenghtQueue(queue* q){

     int len =0 ;
     if (isEmpty(q))
            return 0 ;

      queue* qe = q->next ;
      len ++ ;

       while(qe!=q){
             len ++ ;
             qe=qe->next ;           
       }
           return len ;
  }

Upvotes: 0

Tom Walsh
Tom Walsh

Reputation: 11

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;

Upvotes: 1

rizon
rizon

Reputation: 8187

No of items in Circular queue is, 

size = (N-f+r) mod N

where

  • N is the size of array used in circular fashion
  • f index of the front element
  • r index immediately past the rear element

This formula work for both liner and circular queues.

Upvotes: 0

Nikhil Doomra
Nikhil Doomra

Reputation: 398

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

Upvotes: 8

Shashi
Shashi

Reputation: 2898

The standard answer is to take two iterators at the beginning, increment the first one once, and the second one twice. Check to see if they point to the same object. Then repeat until the one that is incrementing twice either hits the first one or reaches the end. inside this loop use the counter to get the length of the CQuueeue

Upvotes: 1

Robert Reinhard
Robert Reinhard

Reputation: 31

 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;

Upvotes: 3

unsym
unsym

Reputation: 2200

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);

Upvotes: 3

Sam Holder
Sam Holder

Reputation: 32936

can your queue contain the same element in more than one location? if it can then I don't think you can do this as there is no way to know the difference between:

a->b->c

and

a->b->c->a->b->c

if it can't contain the same element more than once, just look through the queue until you find an element you have already seen

Upvotes: 0

Related Questions