Circular Queue

Given an array A of a default size (≥ 1) with two references back and front, originally set to -1 and 0 respectively. Each time we insert (enqueue) a new item, we increase the back index; when we remove (dequeue) an item – we increase the front index. Here is a picture that illustrates the model after a few steps:

As you see from the picture, the queue logically moves in the array from left to right. After several moves back reaches the end, leaving no space for adding new elements

However, there is a free space before the front index. We shall use that space for enqueueing new items, i.e. the next entry will be stored at index 0, then 1, until front. Such a model is called a wrap around queue or a circular queue

Finally, when back reaches front, the queue is full. There are two choices to handle a full queue:a) throw an exception; b) double the array size.

The circular queue implementation is done by using the modulo operator (denoted %), which is computed by taking the remainder of division (for example, 8%5 is 3). By using the modulo operator, we can view the queue as a circular array, where the “wrapped around” can be simulated as “back % array_size”. In addition to the back and front indexes, we maintain another index: cur – for counting the number of elements in a queue. Having this index simplifies a logic of implementation.

Implementation using Arrays

class Circular_Queue
{
    private:
        int *cqueue_arr;
        int front, rear;
    public:
        Circular_Queue()
        {
            cqueue_arr = new int [MAX];
            rear = front = -1;
        }
        /*
         * Insert into Circular Queue
         */
        void insert(int item)
        {
            if ((front == 0 && rear == MAX-1) || (front == rear+1))
            {
                cout<<"Queue Overflow \n";
                return;
            }
            if (front == -1)
            {
                front = 0;
                rear = 0;
            }
            else
            {
                if (rear == MAX - 1)
                    rear = 0;
                else
                    rear = rear + 1;
            }
            cqueue_arr[rear] = item ;
        }
        /*
         * Delete from Circular Queue
         */
        void del()
        {
            if (front == -1)
            {
                cout<<"Queue Underflow\n";
                return ;
            }
            cout<<"Element deleted from queue is : "<<cqueue_arr[front]<<endl;
            if (front == rear)
            {
                front = -1;
                rear = -1;
            }
            else
            {
                if (front == MAX - 1)
                    front = 0;
                else
                    front = front + 1;
            }
        }
        /*
         * Display Circular Queue
         */
        void display()
        {
            int front_pos = front, rear_pos = rear;
            if (front == -1)
            {
                cout<<"Queue is empty\n";
                return;
            }
            cout<<"Queue elements :\n";
            if (front_pos <= rear_pos)
            {
                while (front_pos <= rear_pos)
                {
                    cout<<cqueue_arr[front_pos]<<"  ";
                    front_pos++;
                }
            }
            else
            {
                while (front_pos <= MAX - 1)
                {
                    cout<<cqueue_arr[front_pos]<<"  ";
                    front_pos++;
                }
                front_pos = 0;
                while (front_pos <= rear_pos)
                {
                    cout<<cqueue_arr[front_pos]<<"  ";
                    front_pos++;
                }
            }
            cout<<endl;
        }
};

Implementation using Linked List

struct cq
{
  int data;
  struct cq *next;
}*f=NULL,*r=NULL,*n,*temp,*temp1;

void cq_ins()
{
  n=new cq[sizeof(cq)];
  cout<<"\nEnter the Element: ";   
  cin>>n->data;
  if(f==NULL)
  {
      f=n;
  }
  else
  {
      r->next=n;
  }
  r=n;
  r->next=f;
}

void cq_del()
{
  int x;
  temp=f;
  if(f==NULL)
  {
      cout<<"\nCircular Queue Empty!!!";   
  }   
  else   
  {      
     if(f==r)      
     {        
       x=f->data;
       delete(temp);
       f=NULL;
       r=NULL;
     }
     else
     {
        x=temp->data;
        f=f->next;
        r->next=f;
        delete(temp);
     }
     cout<<"\nElement "<<x<<" is Deleted";
     cq_dis();
  }
}

void cq_dis()
{
  temp=f;
  temp1=NULL;
  if(f==NULL)
  {
    cout<<"\n\nCircular Queue Empty!!!";
  }
  else
  {
    cout<<"\n\nCircular Queue Elements are:\n\n";
    while(temp!=temp1)
    {
       cout<data<<"  ";        
       temp=temp->next;
       temp1=f;
    }
  }
}