A circular queue is a linear data structure that follows FIFO principle. In circular queue, the last node is connected back to the first node to make a circle. In Circular queue elements are added at the rear and elements are deleted from front.
We can represent circular queue using array as well as linked list. In this article we will see how we can implement circular queue using array and we will see writing program for it.
What is Circular Queue?
A Circular Queue is a smarter version of a regular queue that avoids wasting space. Imagine a regular queue as a straight line where you can only add things at one end and take them from the other. Once you reach the end, even if there are free spaces at the beginning, you can’t use them without shifting everything. But, in a circular queue, the line is more like a circle, so when you reach the end, it wraps around to the start, using any empty spaces.
How Circular Queue Works?
- Starting Point: Think of an array as a row of boxes. In a circular queue, we have two markers,
frontandrear, to keep track of where the line starts and ends. - Adding Items (Enqueue): When you add an item, you put it where
rearpoints to, then moverearone spot ahead. Ifrearreaches the end and there’s space at the beginning, it jumps back to the start. - Removing Items (Dequeue): To take an item out, you remove it from where
frontpoints, then movefrontahead. Likerear, iffrontreaches the end and there are still items, it wraps around to the beginning. - Circular Movement: This looping action is why it’s called “circular.” You can keep using the array without wasting space.
Below C Program has three methods to perform Circular queue operations
enqueue(int val):- This function will insert a value at the rear of the circular queue. Before insertion, it will checks whether the circular queue is empty or not. If a queue is empty then print “Queue Overflow” otherwise new item will be added to the circular queue.
dequeue():- This function will delete items from the front. Before deletion, it will checks whether the circular queue is empty or not. If it is empty then “Queue Underflow” will be print otherwise dequeue operation will be performed.
display():- display() function will first check circular queue is empty or not? If it is empty then print “Queue is Empty” and if not empty then print all the items of the circular queue.
C Program to implement Circular Queue using Array
#include <stdio.h>
#include <stdlib.h>
int cqueue[6];
int front = -1, rear = -1, n = 6;
void enqueue(int val) {
if ((front == 0 && rear == n - 1) || (front == rear + 1)) {
printf("Queue Overflow \n");
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val;
}
void dequeue() {
if (front == -1) {
printf("Queue Underflow\n");
return;
}
printf("Element deleted from queue is : %d\n", cqueue[front]);
if (front == rear) {
front = -1;
rear = -1;
} else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void display() {
int f = front, r = rear;
if (front == -1) {
printf("Queue is empty\n");
return;
}
printf("Queue elements are :\n");
if (f <= r) {
while (f <= r) {
printf("%d ", cqueue[f]);
f++;
}
} else {
while (f <= n - 1) {
printf("%d ", cqueue[f]);
f++;
}
f = 0;
while (f <= r) {
printf("%d ", cqueue[f]);
f++;
}
}
printf("\n");
}
int menu() {
int choice;
printf("\n1.Add value to the list");
printf("\n2.Delete value from the list");
printf("\n3.Traverse/View List");
printf("\n4.Exit");
printf("\nPlease enter your choice: ");
scanf("%d", &choice);
return(choice);
}
int main() {
int value;
while (1) {
switch (menu()) {
case 1:
printf("Input for insertion: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0; // Use return 0; since main is declared as int.
}
Output
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 1
Input for insertion: 3
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 1
Input for insertion: 5
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 1
Input for insertion: 9
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 1
Input for insertion: 1
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 3
Queue elements are :
3 5 9 1
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 2
Element deleted from queue is : 3
1.Add value to the list
2.Delete value from the list
3.Traverse/View List
4.Exit
Please enter your choice: 3
Queue elements are :
5 9 1 Explanations
Headers
#include <stdio.h>: Includes the Standard Input Output library for basic input/output operations, likeprintfandscanf.#include <stdlib.h>: Includes the Standard Library for theexitfunction, which terminates the program.
Global Variables
cqueue[6]: This is an array of integers acting as the circular queue with a fixed size of 6 elements.front: An integer variable indicating the front of the queue. Initialized to-1to indicate that the queue is empty.rear: An integer variable indicating the rear of the queue. Also initialized to-1.n = 6: Represents the maximum size of the queue.
Functions
enqueue(int val): Adds an integer valuevalto the rear of the queue. It first checks for queue overflow (if the queue is full), then inserts the value and adjusts therearposition accordingly. If the queue is initially empty (frontis-1), bothfrontandrearare set to 0.dequeue(): Removes an element from the front of the queue and displays it. It checks for queue underflow (if the queue is empty) first. If there’s only one element in the queue, resettingfrontandrearto-1indicates that the queue is empty again.display(): Prints all elements in the queue fromfronttorear. If the queue is empty, it prints a message. It handles the circular nature of the queue by wrapping around when reaching the end of the array.menu(): Displays a menu of operations that can be performed on the circular queue and returns the user’s choice. The operations include adding a value, deleting a value, viewing the queue, and exiting the program.main(): The entry point of the program. It uses an infinite loop (while(1)) to continuously display the menu and perform actions based on the user’s choice. The loop terminates when the user chooses to exit (option 4). It handles user inputs for queue operations and calls the corresponding functions.
How It Works
- Start: The program starts in the
mainfunction, displaying a menu of actions. - User Interaction: The user selects an action by entering a number. Options include inserting a value into the queue, deleting a value from the queue, displaying the queue, or exiting the program.
- Performing Actions:
- Insert (Enqueue): Adds a new value at the
rearof the queue. If the queue is full or reaches the end of the array, it loops back to the beginning (if there’s space). - Delete (Dequeue): Removes the value at the
frontof the queue and adjusts thefrontposition accordingly. If the queue becomes empty,frontandrearare reset. - Display: Shows all the current elements in the queue, handling the circular nature appropriately.
- Exit: Ends the loop and terminates the program.
- Insert (Enqueue): Adds a new value at the
- Loop: The process repeats until the user decides to exit.