Memory is a precious resource for which programs are optimized all the time. A linear queue comes with the downside of memory wastage, and a circular queue was introduced as an extension to overcome this issue. This comprehensive guide provides an understanding of the circular queue program in C and how to work with this type of data structure in computing.
A simple or linear queue is a basic data structure that operates on the First In, First Out (FIFO) principle. In the queue, elements are inserted at the rear and removed from the front. However, once an element is dequeued, its space cannot be reused, leading to inefficient memory usage if not handled properly. Linear queues are straightforward to implement and are commonly used in task scheduling and managing simple processes.
A circular queue is a linear data structure where elements are added from the front and removed from the rear. When the queue becomes full, it starts overwriting from the beginning. The last element of the circular queue is linked to the element preceding it in the sequence. This structure resembles a circle, which is why it is known as the ring buffer. This circular arrangement enables the queue to extend and start from the beginning once the last position is completed.
In a linear queue, when the rear reaches the last position of the queue and the front is pointing somewhere other than the 0th position, there may be empty spaces available at the beginning. However, if we try to insert an element when the rear is at the last position, it will show that there are no empty spaces in the queue, even though empty slots exist at the front.
One solution to prevent memory wastage is shifting all elements to the left and adjusting the front and rear ends. However, this is not a practically good approach because shifting all elements consumes a lot of time. The optimal solution to avoid memory wastage is to use a circular queue data structure.
Consider an example where elements 1 to 8 are enqueued, with the front pointing to 1 and the rear to 8. If we dequeue 1 and 2 in a linear queue, the first two memory slots become unusable. One solution to overcome this wasted memory space is to shift the remaining elements forward to free up space at the end. However, this approach negatively affects runtime performance. When there is no shifting, the unused memory remains inaccessible, making this approach inefficient, especially with static arrays.
A more efficient solution is a circular queue. In a circular queue, the first position logically follows the last, forming a loop. This structure eliminates wasted space without the need for shifting. Circular queues can be implemented using a circular array, singly linked list, or doubly linked list, making them ideal for optimizing memory usage.
An important benefit that can be obtained in implementing a circular queue is the full utilization of space. A regular queue can become full with empty slots at the front since they are the elements that are first dequeued. This challenge is addressed in circular queues as the first element location always follows the last location and doesn't waste space. This makes circular queues very useful wherever memory is scarce or where there is a constant flow of data input that has to be effectively controlled.
Circular queues support several fundamental operations:
The enqueue operation involves inserting an element into the queue. Here are the steps for performing an enqueue operation in a circular queue:
There are two scenarios in which the queue is not full:
ENQUEUE(queue, value):
IF (rear + 1) % SIZE == front:
PRINT "Queue is full!"
RETURN
IF front == -1: // Queue is empty
front = 0
rear = 0
ELSE:
rear = (rear + 1) % SIZE
queue[rear] = value
The dequeue operation removes an element from the queue. Here are the steps for performing a dequeue operation in a circular queue:
DEQUEUE(queue):
IF front == -1:
PRINT "Queue is empty!"
RETURN
value = queue[front]
IF front == rear: // Only one element left
front = -1
rear = -1
ELSE:
front = (front + 1) % SIZE
RETURN value
// C Program to implement a circular queue using arrays
#include <stdio.h>
// Define the maximum size of the queue
#define MAX_SIZE 7
// Declare the queue array and front, rear variables
int queue[MAX_SIZE];
int front = -1, rear = -1;
// Function to check if the queue is full
int isFull() {
return (rear + 1) % MAX_SIZE == front;
}
// Function to check if the queue is empty
int isEmpty() {
return front == -1;
}
// Function to enqueue (insert) an element
void enqueue(int data) {
if (isFull()) {
printf("Queue overflow\n");
return;
}
if (front == -1) {
front = 0;
}
rear = (rear + 1) % MAX_SIZE;
queue[rear] = data;
printf("Element %d inserted\n", data);
}
// Function to dequeue (remove) an element
int dequeue() {
if (isEmpty()) {
printf("Queue underflow\n");
return -1;
}
int data = queue[front];
if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % MAX_SIZE;
}
return data;
}
// Function to display the queue elements
void display() {
if (isEmpty()) {
printf("Queue is empty\n");
return;
}
printf("Queue elements: ");
int i = front;
while (i != rear) {
printf("%d ", queue[i]);
i = (i + 1) % MAX_SIZE;
}
printf("%d\n", queue[rear]);
}
// Main function
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
enqueue(60);
enqueue(70);
enqueue(80); // This should show "Queue overflow"
display();
printf("Dequeued element: %d\n", dequeue());
printf("Dequeued element: %d\n", dequeue());
display();
enqueue(80);
enqueue(90); // Should be added successfully
display();
return 0;
}
Element 10 inserted
Element 20 inserted
Element 30 inserted
Element 40 inserted
Element 50 inserted
Element 60 inserted
Element 70 inserted
Queue overflow
Queue elements: 10 20 30 40 50 60 70
Dequeued element: 10
Dequeued element: 20
Queue elements: 30 40 50 60 70
Element 80 inserted
Element 90 inserted
Queue elements: 30 40 50 60 70 80 90
=== Code Execution Successful ===
Queue Setup: A circular queue is implemented using an array of size 7 (MAX_SIZE).
Operations:
Circular Queue: Uses modulo arithmetic to handle the wraparound of the front and rear pointers when the queue is full or has available space.
Display: The display() function prints the elements from the front to the rear, considering the circular structure to wrap around the array.
Output: The program enqueues and dequeues elements and prints the queue's state at each step.
// C program for insertion and deletion
// in Circular Queue
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node *front, *rear;
};
struct Node* createNode(int newdata);
// Function to insert element in a Circular queue
void enQueue(struct Queue* q, int value) {
struct Node* newNode = createNode(value);
if (q->front == NULL)
q->front = newNode;
else
q->rear->next = newNode;
q->rear = newNode;
q->rear->next = q->front;
}
// Function to delete element from Circular Queue
int deQueue(struct Queue* q) {
// if queue is empty
if (q->front == NULL) {
return -1;
}
int value;
// If this is the last node to be deleted
if (q->front == q->rear) {
value = q->front->data;
free(q->front);
q->front = q->rear = NULL;
} else {
struct Node* temp = q->front;
value = temp->data;
q->front = q->front->next;
q->rear->next = q->front;
free(temp);
}
return value;
}
void printQueue(struct Queue* q) {
if (q->front == NULL) return;
struct Node* curr = q->front;
do {
printf("%d ", curr->data);
curr = curr->next;
} while (curr != q->front);
printf("\n");
}
// Function to return the front value
int front(struct Queue* q) {
struct Node* front = q->front;
if (front == NULL) {
return -1;
}
return front->data;
}
// Function to return the rear value
int rear(struct Queue* q) {
struct Node* rear = q->rear;
if (rear == NULL) {
return -1;
}
return rear->data;
}
struct Queue* createQueue() {
struct Queue* q =
(struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
struct Node* createNode(int newdata) {
struct Node* newnode
= (struct Node*)malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->next = NULL;
return newnode;
}
int main() {
struct Queue* q = createQueue();
enQueue(q, 14);
enQueue(q, 22);
enQueue(q, 6);
enQueue(q, 20);
printf("Front value: %d\n", front(q));
printf("Rear value: %d\n", rear(q));
printQueue(q);
printf("Deleted value = %d\n", deQueue(q));
printf("Deleted value = %d\n", deQueue(q));
printQueue(q);
return 0;
}
Front value: 14
Rear value: 20
14 22 6 20
Deleted value = 14
Deleted value = 22
6 20
=== Code Execution Successful ===
This circular queue program in C implements a circular queue using a linked list:
Node Structure: Each queue element is represented by a node with data and a pointer (next) to the next node.
Queue Structure: The queue holds two pointers: front (points to the first node) and rear (points to the last node).
enQueue(): This function adds a new node to the rear of the queue. If the queue is empty, both front and rear point to the new node. Otherwise, the new node is linked to the current rear, and rear is updated. The rear's next pointer is linked back to the front to maintain the circular nature.
deQueue(): This function removes a node from the front of the queue. If there's only one node, both front and rear are set to NULL. Otherwise, the front is updated to the next node, and the rear's next is updated to the new front.
printQueue(): This function prints all the elements in the queue, traversing from the front back to the front in a circular manner.
front() and rear(): These functions return the data at the front and rear of the queue, respectively, or -1 if the queue is empty.
createQueue() and createNode(): These helper functions allocate memory for a new queue or node.
Circular queues have numerous practical applications in computing:
Circular queues efficiently manage memory by utilising empty spaces, unlike linear queues.
Circular queues help the operating system manage the insertion and execution of programs.
Circular queues control traffic lights, cycling through red, yellow, and green lights in a loop.
The circular queue in C program implementation is very important for any student and any aspiring software developer as it increases the knowledge and understanding of memory efficiency, structure design, and practical applications. This concept helps to build problem-solving abilities greatly when it comes to optimally using available resources like CPU scheduling and traffic controlling systems. It provides a good background to some of the other complicated areas in data structures and efficient algorithms.
Circular queues enhance memory utilisation since they work around data structures. They optimise available space without wasting memory.
Circular queues can be implemented by array or linked list. For realising the queue in arrays, modulo arithmetic assists in wrapping around the queue, while in linked lists, the actual structure of the link list is changed to make it form a circular chain.
Circular increment ensures that once the target queue has been reached, the next element is placed at the front, hence a continuous circular fashion.
The intended operations are enqueue, which means insertion of an element, and dequeue, which means deletion of an element. Front to obtain the front element and rear for the rear element and isEmpty to know whether the list is empty.
Circular queue program in C are used in many real-life applications, and these are resource allocation, buffering, scheduling, simulation, data transmission, print spooling, real-time systems, networking, and memory management.