Circular Queue
A circular queue is an abstract data type that contains a collection of data which allows addition of data at the end of the queue and removal of data at the beginning of the queue. Circular queues have a fixed size.Circular queue follows FIFO principle. Queue items are added at the rear end and the items are deleted at front end of the circular queue.
Algorithm for Insertion in a circular queue
Insert CircularQueue ( ) 1. If (FRONT == 1 and REAR == N) or (FRONT == REAR + 1) Then 2. Print: Overflow 3. Else 4. If (REAR == 0) Then [Check if QUEUE is empty] (a) Set FRONT = 1 (b) Set REAR = 1 5. Else If (REAR == N) Then [If REAR reaches end if QUEUE] 6. Set REAR = 1 7. Else 8. Set REAR = REAR + 1 [Increment REAR by 1] [End of Step 4 If] 9. Set QUEUE[REAR] = ITEM 10. Print: ITEM inserted [End of Step 1 If] 11. Exit
Implementation of insertion in circular queue
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<ctype.h>
#include<stdlib.h>
#define size 8
int rear, front;
int no;
int q[size];
int rear=-1;
int front=-1;
/* Function to create queue */
void Insert_queue()
{
char ans;
printf("\n Enter 'n' for break:-");
ans=getch();
while(ans!='n')
{
printf("\n Input the Element : ");
scanf("%d",&no);
if((front==0) && (rear==size-1))
{
printf("\n Queue is Overflow");
return;
}
else if(rear==front-1)
{
printf("\n Queue is overflow");
return;
}
else if(front < 0) /* Insert First Element */
{
front=0;
rear=0;
q[rear]=no;
}
else if(rear==size-1)
{
rear=0;
q[rear]=no;
}
else
{
rear++;
if(rear==front)
{
printf("\n Queue is overflow ");
return;
}
else
{
q[rear]=no;
}
}
printf("\n Enter 'n' for break:-");
ans = getch();
}
}
void Display_queue()
{
int i;
if(front < 0)
{
printf("\n Queue is underflow");
return;
}
printf("\nItems are:\n");
if(rear>=front)
{
for(i=front; i<=rear; i++)
{
printf("\n q[%d] = %d",i,q[i]);
}
}
else
{
for(i=front;i < size; i++)
{
printf("\n l-2 q[%d] = %d",i,q[i]);
}
for(i=0;i<=rear;i++)
{
printf("\n l-3 q[%d] = %d",i,q[i]);
}
}
}
/* Function main */
void main()
{
clrscr();
Insert_queue();
Display_queue();
getch();
}
Algorithm for Deletion in a circular queue
Delete CircularQueue ( ) 1. If (FRONT == 0) Then [Check for Underflow] 2. Print: Underflow 3. Else 4. ITEM = QUEUE[FRONT] 5. If (FRONT == REAR) Then [If only element is left] (a) Set FRONT = 0 (b) Set REAR = 0 6. Else If (FRONT == N) Then [If FRONT reaches end if QUEUE] 7. Set FRONT = 1 8. Else 9. Set FRONT = FRONT + 1 [Increment FRONT by 1] [End of Step 5 If] 10. Print: ITEM deleted [End of Step 1 If] 11. Exit
C fuction of deletion in circular queue
void Delete_queue()
{
if(front < 0)
{
printf("\n Queue is Underflow");
return;
}
no=q[front];
q[front]=NULL;
printf("\n Element deleted : ",no);
if(front==rear)
{
front=-1;
rear=-1;
}
else if(front==size-1)
{
front=0;
}
else
{
front++;
}
}