Circular Queue

Circular Queue

• Definition : A circular queue is a linear data structure in which the last position is connected back to the first position, forming a circle.

• As we have seen, in case of linear queue the elements get deleted logically. This can be shown by following Fig. 4.8.1.

• We have deleted the elements 10, 20 and 30 means simply the front pointer is shifted ahead. We will consider a queue from front to rear always. And now if we try to insert any more element then it won't be possible as it is going to give "queue full !" message. Although there is a space of elements 10, 20 and 30 (these are deleted elements), we can not utilize them because queue is nothing but a linear array !

• Hence there is a concept called circular queue. The main advantage of circular queue is we can utilize the space of the queue fully. The circular queue is shown by following Fig. 4.8.2.

• Considering that the elements deleted are 10, 20 and 30.

• There is a formula which has to be applied for setting the front and rear pointers, for a circular queue.

rear = (rear + 1) % size

front = (front + 1) % size.

rear = (rear + 1)% size

       = (4 + 1) % 5

rear = 0

So we can store the element 60 at 0^th location similarly while deleting the element.

front = (front + 1)% size

         = (3 + 1) % 5

front = 4

So delete the element at 4^th location i.e. element 50

Let us see the 'C++' program now,

C++ Program

#include<iostream>

using namespace std;

#define MAX 10

class Queue

int Que[MAX];

int front,rear;

public:

Queue()//constructor defined

{

   front=‒1;

   rear=0;

}

void init();

void insert(int ch);

int delet();

void display();

};

void Queue::init()

{

   int i;

   for(i=0;i<MAX;i++)

   Que[i]=0;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

insert function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Queue::insert(int item)

{

   if (front==(rear+1)%MAX)

   {

      cout<<"Queue is full\n";

   }

   else

   {

      //setting front pointer for a single element in Queue,

      if(front= =‒1)

      front= rear=0;

      else

      rear=(rear+1)%MAX;

      Que[rear]=item;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

delet function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

int Queue::delet()

{

int val;

if(front= =‒1)

{

   cout << "Queue is empty\n";

   return 0; // return null on empty Queue

}

val= Que[front]://item to be deleted

if(front= =rear)//when single element is present

{

   front= rear=‒1;

}

else

   front (front+1)%MAX;

return val;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Display function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Queue::display()

{

int i;

i=front;

while(il = rear)

{

   cout<<Que[i]<<" ";

   i=(i+1)%MAX;

}

cout<<Que[i] <<endl;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The main function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void main()

{

   int i,choice,item;

   char ans='y';

   clrscr();

   Queue obj;

   obj.init();

   do

   {

      cout<<" Menu" <endl;

      cout<<"1.Insert \n 2.Delete \n 3.Display"<<endl;

      cout<<"Enter Your choice"<<endl;

      cin>>choice;

      switch(choice)

      {

         case 1:cout<<"Enter the element"<<endl;

              cin>item;

              obj.insert(item);

              break;

         case 2:cout<<"The element to be deleted is"<<endl;

              cout<<obj.delet();

              break;

         case 3:obj.display();

              break;

      }

   cout<<"Do You Want to Continue?"<<endl;

   ans=getche();

} while(ans= ='Y' || ans= ='y');

getch();

}

Output

Menu

1.Insert

2.Delete

3.Display

Enter Your choice: 1

Enter the element

10

Do You Want to Continue? y

Menu

1.Insert

2.Delete

3.Display

Enter Your choice: 1

Enter the element

20

Do You Want to Continue? y

Menu

1.Insert

2.Delete

3.Display

Enter Your choice: 1

Enter the element

30

Do You Want to Continue? y

Menu

1.Insert

2.Delete

3.Display

Enter Your choice: 3

10 20 30

Do You Want to Continue? y

Menu

1.Insert

2.Delete

3.Display

Enter Your choice: 2

The element to be deleted is

10

Do You Want to Continue? y

Menu

1.Insert

2.Delete

3.Display

Enter Your choice: 3

20 30

Do You Want to Continue? n

 

Example: 1

Suppose a queue is maintained by circular array QUEUE with N = 12 memory cells. Find the number of elements in the queue when :

i) FRONT = 4, REAR = 8,

ii) FRONT = 10, REAR = 3

iii) FRONT = 5, REAR = 6,

iv) Delete two elements after step (iii)

Solution :

The circular queue with 12 Cell is.

 

Advantages of Circular Queue Over Linear Queue

1. Better memory utilization :

Circular queue reuses the empty spaces created after deletions. So no wastage of space as in linear queue.

2. No "Queue Full" problem when space exists :

Even if some space exists at the beginning, a linear queue cannot insert new elements once rear reaches the end.

3. Efficient use of array :

The array acts like a continuous loop, allowing insertion and deletion without shifting elements.

4. Faster operations :

Both insertion and deletion take O(1) time without requiring shifting.

 

Review Question

1. What is circular queue ? Implement insert and delete operations.