Data Structures and Algorithms - Old Questions
3. What is circular queue? Write an algorithm and C function to implement Circular queue.
Circular Queue is a linear data
structure in which the operations are performed based on FIFO (First In First
Out) principle and the last position is connected back to the first position to
make a circle.
Graphical representation of a circular queue is as follows:
Initialization of
Circular queue:
rear=front=MAXSIZE-1
Algorithms for inserting an element in a circular queue:
This
algorithm is assume that rear and front are initially set to MAZSIZE-1.
1.
if (front==(rear+1)%MAXSIZE)
print Queue is full and exit
else
rear=(rear+1)%MAXSIZE; [increment rear by 1]
2.
cqueue[rear]=item;
3.
end
Algorithms for deleting an element from a circular queue:
This
algorithm is assume that rear and front are initially set to MAZSIZE-1.
1.
if (rear==front) [checking empty condition]
print Queue is empty and exit
2.
front=(front+1)%MAXSIZE; [increment front by 1]
3.
item=cqueue[front];
4.
return item;
5. end.
#include<stdio.h>
#include<conio.h>
#define
SIZE 5
void
enQueue(int);
void
deQueue();
void
display();
int
cQueue[SIZE], front = -1, rear = -1;
void
main()
{
int choice, value;
clrscr();
while(1){
printf("\\n****** MENU
******\\n");
printf("1. Insert\\n2. Delete\\n3.
Display\\n4. Exit\\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("\\nEnter the value to be
insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\\nPlease select the
correct choice!!!\\n");
}
}
}
void
enQueue(int value)
{
if((front == 0 && rear == SIZE - 1)
|| (front == rear+1))
printf("\\nCircular Queue is Full!
Insertion not possible!!!\\n");
else{
if(rear == SIZE-1 && front != 0)
rear = -1;
cQueue[++rear] = value;
printf("\\nInsertion
Success!!!\\n");
if(front == -1)
front = 0;
}
}
void
deQueue()
{
if(front == -1 && rear == -1)
printf("\\nCircular Queue is Empty!
Deletion is not possible!!!\\n");
else{
printf("\\nDeleted element :
%d\\n",cQueue[front++]);
if(front == SIZE)
front = 0;
if(front-1 == rear)
front = rear = -1;
}
}
void
display()
{
if(front == -1)
printf("\\nCircular Queue is
Empty!!!\\n");
else{
int i = front;
printf("\\nCircular Queue Elements
are : \\n");
if(front <= rear){
while(i <= rear)
printf("%d\\t",cQueue[i++]);
}
else{
while(i <= SIZE - 1)
printf("%d\\t", cQueue[i++]);
i
= 0;
while(i <= rear)
printf("%d\\t",cQueue[i++]);
}
}
}