Circular Queue

In linear queues, we have discussed so far that insertions can be done only at one end called the REAR and deletions are always done from the other end called the FRONT.

Linear queue

Here,FRONT=0 and REAR=9.

Now, if you want to insert another value, it will not be possible because the queue is completely full. There is no empty space where the value can be inserted. Consider a scenario in which two successive deletions are made.

Queue after two successive deletions

Here,FRONT=2 and REAR=9.

• Suppose we want to insert a new element in the queue Even though there is space available, the overflow condition still exists because the condition rear = MAX – 1 still holds true. This is a major drawback of a linear queue.
• To resolve this problem, we have two solutions. First, shift the elements to the left so that the vacantspace can be occupied and utilized efficiently. But this can be very time-consuming, especially when the queue is quite large.
• The second option is to use a circular queue. In the circular queue, the first index comes right after the last index. Conceptually, you can think of a circular queue.

Circular queue

1.) If front = 0 and rear = MAX – 1, then the circular queue is full. Look at the queue illustrates this point.

Full queue

2.) If rear != MAX – 1, then rear will be incremented and the value will be inserted as illustrated.

Queue with vacant locations

3.) If front != 0 and rear = MAX – 1, then it means that the queue is not full. So, set rear = 0 and insert the new element there.

Inserting an element in a circular queue

**Algorithm to insert an element in a circular queue **

	Step 1: IF FRONT = 0 and Rear = MAX-1
			Write OVERFLOW
			Goto step 4
		[End OF IF]
	Step 2: IF FRONT=-1 and REAR=-1
			SET FRONT = REAR = 0
		ELSE IF REAR = MAX-1 and FRONT != 0
			SET REAR = 0
		ELSE
			SET REAR = REAR+1
		[END OF IF]
	Step 3: SET QUEUE[REAR] = VAL
	Step 4: EXIT

Afterseeing how a new element is added in a circular queue, let us now discuss how deletions are performed in this case. To delete an element, again we check for three conditions.

1.) If front = –1, then there are no elementsin the queue. So, an underflow condition will be reported.

Empty queue

2.) If the queue is not empty and front = rear, then after deleting the element at the front the queue becomes empty and so front and rear are set to –1.

Queue with a single element

3.) If the queue is not empty and front = MAX–1, then after deleting the element at the front, front is set to 0.

Queue where FRONT = MAX–1 before deletion

** Algorithm to delete an element from a circular queue ** 

	Step 1: IF FRONT=-1
			Write UNDERFLOW
			Goto Step 4
			[END of IF]
	Step 2: SET VAL = QUEUE[FRONT]
	Step 3: IF FRONT = REAR
			SET FRONT = REAR=-1
		ELSE
		IF FRONT = MAX -1
			SET FRONT = 0
		ELSE
			SET FRONT = FRONT+1
		[END of IF]
		[END OF IF]
	Step 4: EXIT

				*******************
				Programming Example
				*******************

1. Write a program to implement a circular queue.

#include<stdio.h>
#include<conio.h>
#define SIZE 5

int front = -1;
int rear  = -1;
int q[SIZE];

void insert();
void del();
void print();

void main()
{
	int choice,val;

	do
	{
		clrscr();
		printf("1. Insert\n2. Delete\n3. Print\n4. Exit");
		printf("\nEnter Your Choice.... : ");
		scanf("%d",&choice);
		flushall();

		switch(choice)
		{
			case 1:
					insert();
				       //print();
					getch();
					break;
			case 2:
					del();
					//print();
					getch();
					break;
			case 3:
					print();
					getch();
					break;
			case 4:
					exit(0);
		}
	}while(choice != 4);
}

void insert()
{
	int no;

		printf("\nEnter no : ");
		scanf("%d",&no);

	if((rear == SIZE-1 && front == 0) || (front==rear+1) )
	{
		printf("\nQueue overflow...");
		return;
	}
	else if(front == -1 && rear == -1)
	{
		front=rear=0;
		q[rear]=no;
		printf("\n\t%d inserted successfully..",no);
	}
	else if(rear==SIZE-1 && front!= 0)
	{
	 //	printf("\nEnter no : ");
	   //	scanf("%d",&no);

		printf("\n\t%d inserted successfully..",no);
		rear=0;
		q[rear]=no;
	}
	else
	{
		rear++;
		q[rear] = no;

		printf("\n\t%d inserted successfully..",no);
	}
}

void del()
{
	int val;

	if(front == -1 && rear==-1)
	{
		printf("\nQueue Underflow...");
		return;
	}
	else
	{
		val=q[front];
		printf("\t%d deleted successfully...",val);
		if(front== rear)
		{
			front=rear=-1;
		}
		else
		{
			if(front ==SIZE-1)
			{
				front=0;
			}
			else
			{
				front++;

			}
		}
	}

}
void print()
{
	int i;

	if(front == -1)
	{
		printf("\nQueue Underflow...");
		return;
	}
	else
	{
	printf("\n");
	if(front!=-1 && rear !=-1)
	{
		if(front<=rear)
		{
			for(i=front;i<=rear;i++)
			{

				printf("\t %d",q[i]);
			}
		}
		else
		{
			for(i=front;i<SIZE;i++)
			{
				printf("\t %d",q[i]);
			}
			for(i=0;i<rear;i++)
			{
				printf("\t %d",q[i]);
			}
		}
	}
	}
}