Experiment No.

6
Aim :- Write a program in C/C++ to implement queue as circular link list then we need only
one pointer at rear to locate both front and rear. Write function to process a queue stored in
this way:
a) Initialize b) Add node c) Delete Node
Tool :- Online C Compiler
Theory :- To implement queue using linked list, we need to set the following things before
implementing actual operations.
Step 1 - Include all the header files which are used in the program. And declare all the user defined
functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
Step 4 - Implement the main method by displaying Menu of list of operations and make suitable
function calls in the main method to perform user selected operation.
Enqueue(value) - Inserting an element into the Queue We can use the following steps to insert a new
node into the queue...
Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.
Step 2 - Check whether queue is Empty (rear == NULL)
Step 3 - If it is Empty then, set front = newNode and rear = newNode.
Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode
Dequeue() - Deleting an Element from Queue We can use the following steps to delete a node from
the queue...
Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate
from the function
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).
display() - Displaying the elements of Queue We can use the following steps to display the elements
(nodes) of a queue...
Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp' reaches
to 'rear' (temp → next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.
A 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.
Insertion in Circular queue-
There are three scenario of inserting an element in a queue.
1. If (rear + 1)%maxsize = front, the queue is full. In that case, overflow occurs and therefore,
insertion can not be performed in the queue.
2. If rear != max - 1, then rear will be incremented to the mod(maxsize) and the new value will be
inserted at the rear end of the queue.
3. If front != 0 and rear = max - 1, then it means that queue is not full therefore, set the value of rear to
0 and insert the new element there.
Algorithm to insert an element in circular queue
Step 1: IF (REAR+1)%MAX = FRONT 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) % MAX [END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Introduction to delete an element from a circular queue-
To delete an element from the circular queue, we must check for the three following conditions.
1. If front = -1, then there are no elements in the queue and therefore this will be the case of an
underflow condition.
2. If there is only one element in the queue, in this case, the condition rear = front holds and therefore,
both are set to -1 and the queue is deleted completely.
3. If front = max -1 then, the value is deleted from the front end the value of front is set to 0.
4. Otherwise, the value of front is incremented by 1 and then delete the element at the front end.
Algorithm-
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

Program :-
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next;
};
struct node *f = NULL;
struct node *r = NULL;
void enqueue(int d) //Insert elements in Queue
{
struct node* n;
n = (struct node*)malloc(sizeof(struct node));
n->data = d;
n->next = NULL;
if((r==NULL)&&(f==NULL))
{
f = r = n;
r->next = f;
}
else
{
r->next = n;
r = n;
n->next = f;
}
}
void dequeue() // Delete an element from Queue
{
struct node* t;
t = f;
if((f==NULL)&&(r==NULL))
printf("\nQueue is Empty");
else if(f == r){
f = r = NULL;
free(t);
}
else{
 f = f->next;
r->next = f;
free(t);
}
}
void print(){ // Print the elements of Queue
struct node* t;
t = f;
if((f==NULL)&&(r==NULL))
printf("\nQueue is Empty");
else{
do{
printf("\n%d",t->data);
t = t->next;
}while(t != f);
}
}
int main()
{
int ch,n,i,data;
printf("Enter Your Choice:-");
do{
printf("\n1.for Insert the Data in Queue\n2.for show the Data in Queue \n3.for Delete
the data from the Queue\n4.for Exit\n");
scanf("%d",&ch);
switch(ch){
case 1:
printf("\nEnter the number of data\n");
scanf("%d",&n);
printf("\nEnter your data\n");
i=0;
while(i<n){
scanf("%d",&data);
 enqueue(data);
i++;
}
break;
case 2:
print();
break;
case 3:
dequeue();
break;
case 0:
break;
default:
printf("\nIncorrect Choice, Put Correct Choice");

}
}while(ch!=0);
return 0;
}
Screen Shot :-
Result :-