Experiment No.
5
Implement Circular Queue ADT using array
Name: Patil Pranjal Keshav
Roll No:45
Date of Performance:
Date of Submission:
Marks:
Sign:
Experiment No. 5: Circular Queue
Aim: To Implement Circular Queue ADT using array
Objective:
Circular Queues offer a quick and clean way to store FIFO data with a maximum size
Theory:
Circular queue is an data structure in which insertion and deletion occurs at an two ends rear
and front respectively. Eliminating the disadvantage of linear queue that even though there is
a vacant slots in array it throws full queue exception when rear reaches last element. Here in
an circular queue if the array has space it never throws an full queue exception. This feature
needs an extra variable count to keep track of the number of insertion and deletion in the queue
to check whether the queue is full or not.Hence circular queue has better space utilization as
compared to linear queue. Figure below shows the representation of linear and circular queue.
Linear queue
Front rear
0 … … n
Circular Queue
Algorithm
Algorithm : ENQUEUE(Item)
Input : An item is an element to be inserted in a circular queue.
Output : Circular queue with an item inserted in it if the queue has an empty slot. Data
Structure : Q be an array representation of a circular queue with front and rear pointing to
the first and last element respectively.
1. If front = 0
front = 1
rear =1
Q[front] = item
2. else next=(rear mod length) if next!=front then rear = next
Q[rear] = item
Else
Print “Queue is full”
End if
End if
3. stop
Algorithm : DEQUEUE()
Input : A circular queue with elements.
Output :Deleted element saved in Item.
Data Structure : Q be an array representation of a circular queue with front and rear pointing
to the first and last element respectively.
1. If front = 0
Print “Queue is empty”
Exit
2. else item = Q[front] if front = rear then rear = 0 front=0
else front =
front+1
end if
end if
3. stop
Code:
#include <stdio.h>
//#include <conio.h>
#define MAX 4
int q[MAX];
int front = -1;
int rear = -1;
int num;
void enqueue() {
if (front == (rear + 1) % MAX)
printf("\nQueue is full");
else
printf("\nEnter number ");
scanf("%d", &num);
rear = (rear + 1) % MAX;
q[rear] = num;
if (front == -1)
{
front = 0; // Change front from -1 to 0 (not front++)
void dequeue()
if (front == -1 && rear == -1)
printf("\nQueue is empty\n");
else
num = q[front];
printf("\n%d is deleted\n", num);
if (front == rear)
front = -1;
rear = -1;
else
front = (front + 1) % MAX;
}
void display()
int i;
if (front == -1 && rear == -1)
printf("\nQueue is empty");
else
for (i = front; i != rear; i = (i + 1) % MAX)
printf("%d ", q[i]);
printf("%d ", q[i]); // Display the last element manually
void main()
//clrscr();
enqueue();
enqueue();
enqueue();
dequeue();
display();
enqueue();
display();
//getch();
Output:
Conclusion:
Explain how Josephus Problem is resolved using circular queue and elaborate on operation
used for the same.
The Josephus Problem is a theoretical problem related to a certain elimination game. The classic
version involves n people standing in a circle and eliminating every k-th person until only one
person remains. To solve this problem using a circular queue, we can leverage the properties of a
queue to simulate the elimination process efficiently.
Operations Used
1. Enqueue:
o Add a person to the circular queue. This operation takes constant time
O(1)O(1)O(1).
2. Dequeue:
o Remove a person from the front of the circular queue. This operation also takes
constant time O(1)O(1)O(1).
3. Move Pointer:
o Move the current pointer forward by k-1. This can be implemented efficiently,
wrapping around the end of the queue using modulo operations.
Example
Consider an example with n = 7 and k = 3:
1. Enqueue: People 1 to 7 are enqueued.
2. Start counting from position 1, and move to position 3:
o Persons in the queue: [1, 2, 3, 4, 5, 6, 7]
o Remove person 3. Remaining: [1, 2, 4, 5, 6, 7]
3. Repeat the process:
o Move to position 3: Remove person 6. Remaining: [1, 2, 4, 5, 7]
o Move to position 3: Remove person 4. Remaining: [1, 2, 5, 7]
o Move to position 3: Remove person 2. Remaining: [1, 5, 7]
o Move to position 3: Remove person 7. Remaining: [1, 5]
o Move to position 3: Remove person 5. Remaining: [1]
The last remaining person is 1.
