Circular Queues - Introduction and Implementation


Circular Queue is a variation of queue data structure. They can be implemented using arrays or linked lists. In this article, I am going to discuss a brief on circular queues and then the C programs to implement circular queues using arrays and linked lists.

Introduction to Circular Queues

A Queue is a data structure which follows FIFO (first in first out) principle. The element which is entered first into the queue (first in) is the element which can be first deleted from the queue (first out). Two operations ENQUEUE and DEQUEUE are commonly used for queues. Here, ENQUEUE means insertion and DEQUEUE means deletion. Operations like insertion, deletion can be performed at both ends of a queue. Two pointers called FRONT and REAR are used for queues. Here, FRONT represents the end at which deletion can be performed and REAR represents the end at which insertion can be performed. A circular queue is a variation of a queue in which the last element is connected to first element. There are some other operations for queues which are PEEK, ISFULL and ISEMPTY. Here, PEEK is used to get the first element of the queue without removing it and ISFULL, ISEMPTY are used to check whether the queue is full (over flow error) or empty (under flow error) respectively. The image below shows a circular queue, it operations (only insertion and deletion but not others) and pointers.

Circular Queue

Implementation of Circular Queues

Circular Queues can be implemented using arrays or linked lists.

C Program to implement Circular Queues using Arrays


Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAXSIZE 5
int cqueue[MAXSIZE];
int front,rear;
void insert_element(int item)
{
if(front==(rear+1)%MAXSIZE)
printf("\n CIRCULAR QUEUE IS FULL : OVERFLOW ERROR");
else
{
if(front==-1)
{
front=0;
rear=0;
}
else
rear=(rear+1)%MAXSIZE;
cqueue[rear]=item;
}
}
void delete_element(void)
{
int a;
if(front==-1)
printf("\n CIRCULAR QUEUE IS EMPTY : UNDERFLOW ERROR");
else
{
a=cqueue[front];
cqueue[front]=0;
if(front==rear)
{
front=-1;
rear=-1;
}
else
front=(front+1)%MAXSIZE;
printf("\n Element deleted from Circular Queue is : %d",a);
}
}
void display_cqueue(void)
{
int i;
printf("\n Circular Queue is : ");
for(i=0;i<MAXSIZE;i++)
printf("%d ",cqueue[i]);
}
void main(void)
{
int choice,i,num;
front=-1;
rear=-1;
clrscr();
for(i=0;i<MAXSIZE;i++)
cqueue[i]=0;
while(1)
{
printf("\n\n Circular Queue Operations");
printf("\n 1.Insert");
printf("\n 2.Delete");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the element to insert : ");
scanf("%d",&num);
insert_element(num);
break;
case 2:
delete_element();
break;
case 3:
display_cqueue();
break;
case 4:
exit(0);
break;
default:
printf("\n INVALID CHOICE : TRY AGAIN");
break;
}
}
}

Output
Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 10

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 20

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 30

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 40

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 50

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
CIRCULAR QUEUE IS FULL : OVERFLOW ERROR

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 10 20 30 40 50

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 10

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 20

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 30

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 40

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 50

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
CIRCULAR QUEUE IS EMPTY : UNDERFLOW ERROR

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 0 0 0 0 0

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 5
INVALID CHOICE : TRY AGAIN

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4

C Program to implement Circular Queue using Linked Lists

Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct queue
{
int info;
struct queue *link;
}*front=NULL,*rear=NULL;
int count=0;
void insert_element(int n)
{
struct queue *newnode;
newnode=(struct queue*)malloc(sizeof(struct queue));
newnode->info=n;
newnode->link=NULL;
if(count==0)
front=newnode;
else
rear->link=newnode;
rear=newnode;
rear->link=front;
count++;
}
int delete_element(void)
{
int n;
struct queue *temp;
if(count==0)
return -1;
count--;
if(front==rear)
{
n=front->info;
free(front);
front=NULL;
rear=NULL;
}
else
{
temp=front;
n=temp->info;
front=front->link;
rear->link=front;
free(temp);
}
return n;
}
void display_cqueue(void)
{
struct queue *temp;
int i;
if(count==0)
printf("NULL");
else
{
temp=front;
for(i=0;i<count;i++)
{
printf("%d ",temp->info);
temp=temp->link;
}
}
printf("\n");
}
void main(void)
{
int n,choice;
clrscr();
while(1)
{
printf("\n\n Circular Queue Operations");
printf("\n 1.Insert");
printf("\n 2.Delete");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the element to insert : ");
scanf("%d",&n);
insert_element(n);
break;
case 2:
n=delete_element();
if(n==-1)
printf("\n Circular Queue is Empty");
else
printf("\n Element deleted from circular queue is %d",n);
break;
case 3:
printf("\n Circular Queue is : ");
display_cqueue();
break;
case 4:
exit(0);
break;
default:
printf("\n INVALID CHOICE : TRY AGAIN");
break;
}
}
}

Output
Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 5

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 5

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 3

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 5 3

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 1
Enter the element to insert : 1

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 5 3 1

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 5

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 3 1

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 3

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : 1

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 2
Element deleted from Circular Queue is : 1

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 3
Circular Queue is : NULL

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 5
INVALID CHOICE : TRY AGAIN

Circular Queue Operations
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice : 4


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: