September 22, 2012 / IST / Language, Software Development.

A circular queue is a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don’t have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.


How does it work?

A circular queue consists of an array that contains the items in the queue, two array indexes and an optional length. The indexes are called the head and tail pointers and are labelled H and T on the diagram.

A circular queue

The head pointer points to the first element in the queue, and the tail pointer points just beyond the last element in the queue. If the tail pointer is before the head pointer, the queue wraps around the end of the array.

/* Q12b-> WAP In C++ To Implement Circular Queue Using Linked List*/

#include<iostream.h>
#include<conio.h>
#include<process.h>
class circlst                 //Class Declaration
{
   private:
	   struct node
	       { int info;             //Node Structure
		 node *next;
	       }*ptr,*first,*last,*track;
   public:
	   circlst()                       //Constructor
	   {ptr=first=last=track=NULL;}
	   void insrt(int);
	   void delnde();
	   void displst();      //Memeber Functions
};
void circlst::insrt(int n)
{
  ptr=new node;
     if(ptr==NULL)
	{ cout<<"\nNode Cannot Be Created!!!";
	  getch();
	  exit(0);
	}
   ptr->info=n;
   ptr->next=ptr;            //Function To Insert Node

   if(first==NULL)
      first=last=ptr;
   else
      { last->next=ptr;
	ptr->next=first;
	last=ptr;
      }
}
void circlst::delnde()
{   if(first==NULL)
      { cout<<"\nThe List Is Empty!!!";
	getch();
	exit(0);
      }                           //Function To Delete Node
  first=first->next;
  last->next=first;
  cout<<"\n\nNode Deleted Succesfully!!!";
}
void circlst::displst()
{ track=first;
  if(first==NULL)
     cout<<"\nThe List Is Empty!!!";
  while((track->next)!=first)
    {                                  //Function To Delete Node
      track=track->next;
      cout<<track->info<<" ";
    }
}
void main()                     //Main
{
  circlst ob;
  char choice;
  int data,ch;
  do
  { clrscr();
    cout<<"\n\n\t\tCREATION OF A CIRCULAR LINKED LIST";
    cout<<"\n\t\t---------------------------------";
    cout<<"\n\n1.INSERT ELEMENT";
    cout<<"\n2.DISPLAY LIST";
    cout<<"\n3.DELETE ELEMENT";         //menu
    cout<<"\n4.EXIT";
    cout<<"\n\nWhich Operation Do You Want To Perform:";
    cin>>ch;
	 switch(ch)
	      {
		 case 1: cout<<"\nEnter the Data To Be Inserted:";
			 cin>>data;
			 ob.insrt(data);
			 break;
		 case 2: ob.displst();
			 break;             //calling functions
		 case 3: ob.delnde();
			 break;
		 case 4: exit(1);
		 default: cout<<"\nPleasae Enter A valid Choice(1-4)!!!";
	       }
    cout<<"\n\nDo you Want to Continue(Y/N):";
    cin>>choice;
   }while(choice=='Y' || choice=='y');
}                   //end of program