Tuesday, January 22, 2013

Circular Queue



Circular Queue

            The efficient representation of Queue is Circular Queues.  This method is used to arrange the element in circular fashion.  This type of queue is called Circular Queue.  Here the elements will be in the form of Q[0………n-1] where Q[0] is adjacent to Q[1], Q[1] is adjacent to Q[2] and so on and Q[n-2] is adjacent to Q[n-1] and Q[n-1] is adjacent to Q[0]. Here ‘n’ is the maximum No. of elements.  Circular Queue is represented as follows:


Role of Front and Rear

            We represent Front by ‘F’ and Rear by ‘R’.  Here ‘F’ always points to one position counter clockwise from the first element and ‘R’ will point to the last element that is inserted in the Circular Queue. Further when circular queue is empty F=R=0.

            To insert an element into the circular queue first we have to check the present value of ‘R’.  if R= n-1 then new value of ‘R’ is 0.  Otherwise new value of ‘R’ is R=R+1.  After incrementing ‘R’ value, if F=R then Circular Queue is full and hence new element cannot be inserted.  If F is not equal to R then insert a new element at Q[R].  The maximum No. of element that can be stored in circular queue of size n is n-1.  Thus one location is left empty always in circular queues.

            Similarly, to delete an element from circular queues first we have to check the present value of ‘F’.  if F=R then Circular Queue is empty and hence deletion cannot be performed.  Otherwise we delete the element either by incrementing F or resetting F.  if F= n-1 the new value of ‘F’ is 0 otherwise new value of ‘F’ is F=F+1.

Consider an Example of circular queue


Function to Store an element in Queue

CQInsert(int x)
{
     If (r==n-1)
     {
        r=0;
     }
     else
     {
        r=r+1;
     }

    if (r=f)
    {
        printf(“Circular Queue is Full”);
    }
    else
    {
       Q[r]=x;
    }
}



Int CQdelete()
{
    int n;
    if(f==r)
    {
       printf(“Circular Queue is Empty”);
    }
    elseif (f == n-1)
    {
       f=0;
       n=Q[f];
    }
    else
    {
      f=f+1;
      n=Q[f];
     }
    return n;
}



C Program  which depicts Circular Queue
   int r=0,f=0,max=4;
   int Q[4];
   void main()
   {
    int n;
    int choice;
    void dispCQueue();
    void CQinsert();
    int CQdelete();
    clrscr();
    while(1)
    {
       clrscr();
       printf("1 CQinsert\n");
       printf("2 CQdelete\n");
       printf("3 dispCQueue\n");
       printf("4 exit\n");
       printf("enter choice: ");
       scanf("%d",&choice);
       switch(choice)
       {
             case  1:CQinsert();
                         printf("press any key to continue");
                         getch();
                         break;
             case  2:n=CQdelete();
                         printf("Deleted Element =%d\n",n);
                         printf("press any key to continue");
                         getch();
                         break;
             case  3:dispCQueue();
                         printf("press any key to continue");
                         getch();
                         break;
             case  4:exit(0);
                         break;
             default:printf("invalid choice\n");
                         printf("press any key to continue");
                         getch();
       }
    }
  }


   void  dispCQueue()
    {
     int i;
     if(f==max-1)
     {
      for(i=0;i<=r;i++)
      {
       printf("%d  ", Q[i]);
      }
     }
     else if(f>r)
     {
      for(i=f+1;i<=max-1;i++)
      {
       printf("%d  ", Q[i]);
      }
      for(i=0;i<=r;i++)
      {
       printf("%d  ",Q[i]);
      }
     }
     else if(r>f)
     {
      for(i=f+1;i<=r;i++)
      {
       printf("%d  ", Q[i]);
      }
     }
    }


  void CQinsert()
  {
     int n;
     if(r==max-1)
     {
       r=0;
     }
     else
     {
            r=r+1;
     }

     if(r==f)
     {
      printf("CQueue is full\n");
      r=max-1;
     }
     else
     {
       printf("enter element into CQueue\n");
       scanf("%d",&n);
       Q[r]=n;
    }
  }



  int CQdelete()
  {
       int n;
       if(f==max-1)
       {
            f=0;
       }
       else if(f==r)
       {
            printf("CQueue is empty\n");
            return 0;
       }
       else
       {
            f=f+1;
       }
       n=Q[f];
       return n;
  }






No comments:

Post a Comment