Circular Queue

Circular Queue

Definition Circular queue is a special version of queue where the last element of the queue is connected to the first element of the queue forming a circle.

As we have seen, in case of linear queue the elements get deleted logically. This can be shown by following Fig. 3.5.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. 3.5.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 0th location similarly while deleting the element.

front = (front + 1)% size = (3 + 1) % 5

front= 4

So delete the element at 4" location i.e. element 50

Let us see the 'C' program now,

Ex. 3.5.1: Implementation of circular queue using arrays.

Sol. :

/***************************************************************

Program For circular queue using arrays. It performs the basic operations such as insertion, deletion of the elements by taking care of queue Full and queue Empty conditions. The appropriate display is for displaying the queue

*************************************************************/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define size 5

int queue[size];

int front=-1; /* queue initialization by front = -1 and rear = 0*/

int rear =0;

/*

The qFull Function

Input:none

Output:returns 1 or 0 for q.full or not

Called By:add

Calls:none

*/

int qFull()

{

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

return 1;

else

return 0;

}

/*

The qEmpty Function

Input:none

Output:returns 1 or 0 for q.empty or not

Called By:delete and display  

Calls:none

*/

int qEmpty()

{

if(front ==-1)

return 1;

else

return 0;

}

/*

The add Function

Input:the element to be inserted

Output:none

Called By:main

Calls:qFull

*/

void add(int Item)

{

if(qFull()) /* qFull() returns true value */

printf("\n The circular Queue is full!");

 else

{

if(front ===-1)/* only one element in the queue */

front=rear=0;

else

rear = (rear+1)%size;

queue [rear] = Item;

}

}

/*

the delet Function

Input:none

Output:returns the deleted element

Called By:main

Calls:qEmpty

*/

void delet()

{

int Item;

if(qEmpty())

printf("\n Queue Is Empty!");

else

{

Item-queue[front];

if(front == rear)

{

front=rear=-1;

}

else

front (front+1)%size;

printf("\n The deleted item is %d",Item);

}

}

/*

The display Function

Input: none

Output: prints the contents of the queue

Called By:main

Calls:qEmpty

*/

void display()

{

int i;

if(qEmpty())

{

printf("\nThe Queue Is Empty");

return;

}

i=front;

while(i!=rear)

{

printf("%d", queue[i]);

i=(i+1)%size;

}

printf("%d", queue[i]);

}

/*

The main Function

Input:none

Output:none

Called By:O.S.

Calls:add, delete, display

*/

void main(void)

{

int choice,Item;

char ans;

clrscr();

do

{

printf("\n Main Menu");

printf("\n 1.Insert\n2.Delete\n3.Display");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1: printf("\nEnter The element");

scanf("%d", &Item);

add(Item);

break;

case 2: delet();

break;

case 3: display();

break;

default:exit(0);

}

printf("\n Do u want to continue?");

ans = getch();

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

getch();

}

************************ End Of Main ***********************

Advantages of Circular Queue over Linear Queue

(1) Efficient utilization of memory: There is no wastage of memory in circular queue as it uses the unoccupies space and memory is used properly in an effective manner. Thus, no space is left over.

(2) Flexible insertion and deletion operations: In the circular queue, if the queue is not fully occupied, then the elements can be inserted easily on the vacant locations. But in the case of a linear queue, insertion is not possible once the rear pointer reaches the last index even if there are empty locations present in the queue.

Difference between Linear Queue and Circular Queue

Review Questions

1. Write a routine to implement the circular queue using array.

2. Write an algorithm to convert the infix expression to postfix expression.

3. What are the circular queues. Write the procedure to insert an element to circular queue and delete an element from a circular queue using array implementation.