Circular queue in C
Circular queue in C
Introduction
A crucial part of programming and a vital factor in enhancing software programme performance is the efficient usage of data structures. The circular queue is one such data structure that enables smooth data input and removal, making it ideal for circumstances where the order of the data bits matters. In this post, we shall cover the architecture, functionality, and benefits of a circular queue program implemented in C.
Understanding Circular Queues
The typical queue data structure is modified to create a circular queue, which has the advantage of looping around at the end of the underlying array. A circular queue effectively reuses the freed-up memory space, maximizing resource utilization, unlike a linear queue, which may result in memory waste when components are dequeued.
![Circular queue in C](https://static.tutorialandexample.com/c/circular-queue-in-c1.png)
Design and Implementation
We need to establish the structure representing the circular queue and the necessary variables to track its front and rear indices before we can write a circular queue program in C. Here is an illustration of its use:
#include<stdio.h>
#define MAX_SIZE 100
struct CircularQueue {
int items[MAX_SIZE];
int front;
int rear;
};
// Function prototypes
void enqueue(struct CircularQueue* queue, int data);
int dequeue(struct CircularQueue* queue);
void display(struct CircularQueue* queue);
int main() {
struct CircularQueue queue;
queue.front = -1;
queue.rear = -1;
// Perform queue operations
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
dequeue(&queue);
display(&queue);
return 0;
}
void enqueue(struct CircularQueue *queue, int data){
if((queue-> font == 0 && queue-> rear == MAX_SIZE-1) ||
(queue->font == queue->rear+1)){
printf("Circular Queue is full. Cannot enqueue %d\n", data);
return;
} else if (queue->front == -1) {
queue->front = 0;
queue->rear = 0;
} else if (queue->rear == MAX_SIZE - 1) {
queue->rear = 0;
} else {
queue->rear++;
}
queue->items[queue->rear] = data;
}
int dequeue(struct CircularQueue* queue) {
if (queue->front == -1) {
printf("Circular Queue is empty. Cannot dequeue.\n");
return -1;
}
int data = queue->items[queue->front];
queue->items[queue->front] = -1;
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else if (queue->front == MAX_SIZE - 1) {
queue->front = 0;
} else {
queue->front++;
}
return data;
}
void display(struct CircularQueue* queue) {
if (queue->front == -1) {
printf("Circular Queue is empty.\n");
return;
}
printf("Elements in the Circular Queue are: ");
int i;
if (queue->rear >= queue->front) {
for (i = queue->front; i <= queue->rear; i++)
printf("%d",queue->items[i]);
} else {
for(i=queue->front; i < MAX_SIZE; i++)
printf("%d ",queue->items[i]);
for (i = 0; i <= queue->rear; i++)
printf("%d ",queue->items[i]);
}
printf("\n");
}
Output:
![Circular queue in C](https://static.tutorialandexample.com/c/circular-queue-in-c2.png)
Explanation:
The circular queue is represented by an array of items in the code snippet above, and the variables "front" and "rear" indicate the indices of the front and rear components.
Advantages of Circular Queue
1.Efficient Memory Utilization
When items are dequeued, circular queues reuse the freed space, maximizing memory use and minimizing waste.
2.Constant Time Complexity
Circular queue enqueuing and dequeuing procedures have an O(1) time complexity, making them extremely effective even for big datasets.
3.Handling Sequential Data
Circular queues are especially helpful when handling sequential data, such as in a circular buffer where data is read and written in cycles.
4. Implementation Flexibility
According to the application's needs, circular queues can be built using arrays, linked lists, or dynamic memory allocation.
Disadvantages of Circular Queue
1. Limited Capacity
Because of the amount of the allotted memory or the underlying array, circular queues have a fixed capacity. More en queue actions will cause overflow after the queue reaches its maximum capacity. This restriction might be troublesome when working with dynamic or uncertain data sizes.
2. Fixed Size
A circular queue cannot simply be enlarged after being initialized with a certain size; instead, a new queue must be created, and the old components must be copied. This restriction may be an issue if the program's requirements change on the fly and a flexible data structure that may expand or contract is needed.
3. Memory Fragmentation
Memory fragmentation can result from repeated enqueue and dequeue operations on a circular queue. The circular queue's allotted memory might fragment over time, leading to ineffective memory usage and eventual performance reduction.
4. Complex Implementation
Due to the wrapping around of indices and the handling of specific instances where the front and rear indices intersect, circular queues are more difficult to build than linear queues. The likelihood of creating defects or errors during installation and maintenance might rise due to complexity.
Conclusion
This tutorial we learnt about circular queue program's C implementation. Compared to linear queues, circular queues provide many advantages, including effective memory utilization and constant-time complexity for enqueueing and dequeuing operations. Software application speed may be greatly improved by comprehending and using data structures like circular queues, particularly when the order of data pieces is important. Programmers may improve their code, provide more effective and reliable solutions, and use circular queues.