Why was the concept of the circular queue introduced?
There was one limitation in the array implementation of Queue.
If the rear reaches to the end position of the Queue then there might
be possibility that some vacant spaces are left in the beginning which
cannot be utilized.
The queue after inserting all the elements into it is as follows...
Now consider the following situation after deleting three elements from the queue...
So, to overcome such limitations, the concept of the
circular queue was introduced.
What is Circular Queue?
A circular queue is similar to a linear queue as it is also based on the
FIFO (First In First Out) principle except that the last position is
connected to the first position in a circular queue that forms a circle.
It is also known as a Ring Buffer.
Implementation of Circular Queue
To implement a circular queue data structure using an array, we first
perform the following steps before we implement actual operations.
- Step 1 - Include all the header files which are used in the program and define a constant 'SIZE' with specific value.
- Step 2 - Declare all user defined functions used in circular queue implementation.
- Step 3 - Create a one dimensional array with above defined SIZE (int cQueue[SIZE])
- Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1, rear = -1)
- Step 5 -
Implement main method by displaying menu of operations list and make
suitable function calls to perform operation selected by the user on
circular queue.
enQueue(value) - Inserting value into the Circular Queue
Case 1: Check if queue is full
(front == 0 && rear == SIZE - 1) || (rear + 1) % SIZE == front
Either rear is at the end and front is at the start (like a full circle),
Or the next position of rear is equal to front.
Size = 5
queue = [10, 20, 30, 40, 50]
front = 0
rear = 4
(rear + 1) % SIZE = 0 == front → Queue is full
Action :
Show message: “Queue is Full! Insertion not possible!”
Case 2: First element Insertion
front == -1 && rear == -1
The queue is empty.
Set front = 0, rear =
0
Insert value at queue[rear]
Before:
queue = [_, _, _, _, _]
front = -1, rear = -1
Insert 10
After:
queue = [10, _, _, _, _]
front = 0, rear = 0
Case 3: Two or three elements present
Queue is not full AND not empty
Move rear one step ahead
rear = (rear + 1) % SIZE;
queue[rear] = value;
queue = [10, 20, _, _, _]
front = 0
rear = 1
Insert 30
rear = (1 + 1) % 5 = 2
queue[2] = 30
queue = [10, 20, 30, _, _]
front = 0
rear = 2
deQueue() - Deleting a value from the Circular Queue
Case 1: Check if queue is empty
front = = -1
Action :
Show: "Queue is Empty! Deletion not possible!"
Case 2: Only one element in queue
front == rear
queue = [10, _, _, _, _]
front = 0
rear = 0
Action:
Delete queue[front]
Set front == -1 , rear == -1 (Queue is empty)
Case 3: More than one element in queue
front != rear
Action:
Delete queue[front]
Move front one step ahead.
front = (front + 1) % SIZE;
queue = [10, 20, 30, _, _]
front = 0
rear = 2
Delete 10
queue = [ _, 20, 30, _, _]
front = 1
rear = 2
display() - Displays the elements of a Circular Queue
Case 1: Queue is empty
front == -1
Print : "Queue is empty"
Case 2: Queue has elements
There are two sub-cases
Sub Case A : front < =rear Sub Case B : front > rear
Sub case A:
queue = [10, 20, 30, _, _]
front = 0
rear = 2
Print from index 0 to 2.
Sub case B:
queue = [40, 50, _, _, 10, 20]
front = 4
rear = 1
Print from index 4 to end, then 0 to 1.
Let's understand the enqueue and dequeue operation through the diagrammatic representation.
Implementation of circular queue using Array
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
// Function to insert an element
void enQueue(int value) {
if ((front == 0 && rear == SIZE - 1) || (rear + 1) % SIZE == front) {
printf("\nQueue is Full!\n");
} else {
if (front == -1) front = 0; // first element
rear = (rear + 1) % SIZE;
queue[rear] = value;
printf("\nInserted %d\n", value);
}
}
// Function to delete an element
void deQueue() {
if (front == -1) {
printf("\nQueue is Empty!\n");
} else {
printf("\nDeleted %d\n", queue[front]);
if (front == rear) {
front = rear = -1; // queue becomes empty
} else {
front = (front + 1) % SIZE;
}
}
}
// Function to display the queue
void display() {
if (front == -1) {
printf("\nQueue is Empty!\n");
} else {
printf("\nQueue elements: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf("\n");
}
}
// Main function
int main() {
int choice, value;
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("Enter value to insert: ");
scanf("%d", &value);
enQueue(value);
break;
case 2:
deQueue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice! Try again.\n");
}
}
return 0;
}
Output
