C Program to Implement Queue Using Circular Array

A queue is one of the fundamental data structures in computer science, following the FIFO (First In, First Out) principle. This structure is widely used in scenarios such as task scheduling, resource management, and buffering in networks.

In this article, we will delve into the implementation of a queue using a circular array, a method that optimizes space utilization by reusing previously allocated memory.

What Is a Circular Queue?

A circular queue, unlike a linear queue, connects the last position back to the first position, forming a circle. This arrangement ensures that unused space is minimized as elements are dequeued.

Why Use a Circular Queue?

• Efficient Space Utilization: Prevents the unused memory problem seen in linear queues.
• Real-World Applications: Useful in process scheduling, I/O buffers, and traffic management systems.

Key Operations in a Circular Queue

1. Enqueue (Insert): Add an element to the rear of the queue.
2. Dequeue (Delete): Remove an element from the front of the queue.
3. Peek/Front: Retrieve the front element without removing it.
4. IsEmpty: Check if the queue is empty.
5. IsFull: Check if the queue is full.

Implementation in C

Below is the code for a circular queue using an array. Each operation is explained with inline comments for clarity:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10  // Define the maximum size of the queue

typedef struct {
    int items[SIZE];
    int front, rear;
} CircularQueue;

// Initialize the queue
void initializeQueue(CircularQueue *q) {
    q->front = -1;
    q->rear = -1;
}

// Check if the queue is full
int isFull(CircularQueue *q) {
    return (q->front == (q->rear + 1) % SIZE);
}

// Check if the queue is empty
int isEmpty(CircularQueue *q) {
    return (q->front == -1);
}

// Enqueue operation
void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % SIZE;
    q->items[q->rear] = value;
    printf("Inserted: %d\n", value);
}

// Dequeue operation
int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int value = q->items[q->front];
    if (q->front == q->rear) {  // Queue becomes empty
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % SIZE;
    }
    printf("Removed: %d\n", value);
    return value;
}

// Display the queue
void displayQueue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Queue: ");
    int i = q->front;
    while (1) {
        printf("%d ", q->items[i]);
        if (i == q->rear) break;
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

int main() {
    CircularQueue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    displayQueue(&q);

    dequeue(&q);
    dequeue(&q);

    displayQueue(&q);

    enqueue(&q, 60);

    displayQueue(&q);

    return 0;
}

Inserted: 10
Inserted: 20
Inserted: 30
Inserted: 40
Inserted: 50
Queue: 10 20 30 40 50 
Removed: 10
Removed: 20
Queue: 30 40 50 
Inserted: 60
Queue: 30 40 50 60 

Explanation of the Code

• Initialization: The queue is initialized with front and rear set to -1, indicating an empty state.
• Circular Indexing: Both enqueue and dequeue use the modulo operator (% SIZE) to wrap around the indices.
• Dynamic Behavior: The queue can reuse vacated slots, maximizing efficiency.

Advantages of Circular Queue

• Space Efficiency: Fully utilizes the allocated array.
• Faster Operations: Constant time complexity for insertion and deletion.

Conclusion

Circular queues are a powerful extension of linear queues, ideal for scenarios where memory efficiency and constant time operations are critical. By implementing this structure in C, you gain a deeper understanding of data structure fundamentals and practical coding techniques.