C-Language-Series-#170-Implementing-Circular-Queue

Understanding and Implementing Circular Queues in C

Queues are fundamental linear data structures that follow the First-In, First-Out (FIFO) principle. While simple queues are straightforward, they often suffer from a significant drawback: once an element is dequeued from the front, that memory space often remains unused, even if there's room at the back. This leads to inefficient memory utilization. Enter the **Circular Queue**. A circular queue addresses this inefficiency by treating the queue's underlying array as a circle. When the rear reaches the end of the array, it "wraps around" to the beginning, provided there's empty space. This allows for better memory management and continuous use of the allocated space.

Why Choose a Circular Queue?

The primary advantage of a circular queue over a linear queue is its efficient use of space. In a linear queue, after several dequeue operations, the front pointer moves forward, leaving empty slots at the beginning of the array. Even if the queue is not full, subsequent enqueue operations might fail if the rear pointer has reached the end of the array. A circular queue overcomes this by allowing elements to be inserted at the beginning of the array if space is available.

Common applications include:

• Operating systems (e.g., CPU scheduling, buffer management)
• Traffic management systems
• Data streaming and buffering

Key Concepts and Structure

We'll implement the circular queue using a fixed-size array. To manage the queue, we need:

• queue_array[]: The array to store elements.
• MAX_SIZE: The maximum capacity of the queue.
• front: An index pointing to the first (oldest) element in the queue.
• rear: An index pointing to the last (newest) element in the queue.

Initially, both front and rear will be set to -1, indicating an empty queue. The logic for updating front and rear involves the modulo operator (%) to handle the wrap-around behavior efficiently.

Core Operations

A circular queue typically supports the following operations:

1. isFull(): Checks if the queue is full.
2. isEmpty(): Checks if the queue is empty.
3. enqueue(value): Adds an element to the rear of the queue.
4. dequeue(): Removes and returns an element from the front of the queue.
5. peek(): Returns the front element without removing it.
6. display(): Prints all elements in the queue.

1. Initializing the Queue

Before any operations, the queue is empty. Both front and rear are set to -1.

#include <stdio.h>
#include <stdbool.h> // For bool type

#define MAX_SIZE 5 // Define the maximum size of the circular queue

int circularQueue[MAX_SIZE];
int front = -1;
int rear = -1;

2. isEmpty() Function

The queue is empty if front is -1. When the last element is dequeued, both front and rear are reset to -1.

bool isEmpty() {
    return front == -1;
}

3. isFull() Function

This is where the circular logic is crucial. The queue is full if:

• front is at the beginning (0) and rear is at the end (MAX_SIZE - 1).
• OR, front is right next to rear in a circular manner (front == rear + 1).

bool isFull() {
    return (front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1);
}

4. enqueue(value) Function

To add an element:

1. First, check if the queue is full. If so, print an error and return.
2. If the queue is initially empty (front == -1), set both front and rear to 0.
3. Otherwise, increment rear. If rear reaches MAX_SIZE - 1, wrap it around to 0 using rear = (rear + 1) % MAX_SIZE;.
4. Finally, insert the value at circularQueue[rear].

void enqueue(int value) {
    if (isFull()) {
        printf("Queue is full! Cannot enqueue %d\n", value);
    } else {
        if (isEmpty()) {
            front = 0;
            rear = 0;
        } else {
            rear = (rear + 1) % MAX_SIZE; // Circular increment for rear
        }
        circularQueue[rear] = value;
        printf("Enqueued: %d\n", value);
    }
}

5. dequeue() Function

To remove an element:

1. First, check if the queue is empty. If so, print an error and return -1 (or throw an exception in other languages).
2. Store the element at circularQueue[front] to return it later.
3. If there was only one element in the queue (front == rear), reset both front and rear to -1.
4. Otherwise, increment front. If front reaches MAX_SIZE - 1, wrap it around to 0 using front = (front + 1) % MAX_SIZE;.
5. Return the stored element.

int dequeue() {
    int dequeuedValue;
    if (isEmpty()) {
        printf("Queue is empty! Cannot dequeue.\n");
        return -1; // Indicate error
    } else {
        dequeuedValue = circularQueue[front];
        if (front == rear) { // Only one element in queue
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % MAX_SIZE; // Circular increment for front
        }
        printf("Dequeued: %d\n", dequeuedValue);
        return dequeuedValue;
    }
}

6. peek() Function

To view the front element without removing it:

1. Check if the queue is empty.
2. If not, return the element at circularQueue[front].

int peek() {
    if (isEmpty()) {
        printf("Queue is empty! No element to peek.\n");
        return -1; // Indicate error
    } else {
        return circularQueue[front];
    }
}

7. display() Function

To print the elements:

1. Check if the queue is empty.
2. If not, iterate from front to rear. This requires careful handling of the wrap-around:
   • If front <= rear, a simple loop for (i = front; i <= rear; i++) works.
   • If front > rear, it means the queue has wrapped around. You'll need two loops: one from front to MAX_SIZE - 1, and another from 0 to rear.

void display() {
    if (isEmpty()) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements: ");
    int i = front;
    if (front <= rear) {
        while (i <= rear) {
            printf("%d ", circularQueue[i]);
            i++;
        }
    } else { // Queue has wrapped around
        while (i < MAX_SIZE) {
            printf("%d ", circularQueue[i]);
            i++;
        }
        i = 0;
        while (i <= rear) {
            printf("%d ", circularQueue[i]);
            i++;
        }
    }
    printf("\n");
}

Putting It All Together: Complete C Program

Here's the full C code for the circular queue, including a main function to demonstrate its operations.

#include <stdio.h>
#include <stdbool.h> // For bool type

#define MAX_SIZE 5 // Define the maximum size of the circular queue

int circularQueue[MAX_SIZE];
int front = -1;
int rear = -1;

// Function to check if the queue is empty
bool isEmpty() {
    return front == -1;
}

// Function to check if the queue is full
bool isFull() {
    return (front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1);
}

// Function to add an element to the queue (enqueue)
void enqueue(int value) {
    if (isFull()) {
        printf("Queue is full! Cannot enqueue %d\n", value);
    } else {
        if (isEmpty()) {
            front = 0;
            rear = 0;
        } else {
            rear = (rear + 1) % MAX_SIZE; // Circular increment for rear
        }
        circularQueue[rear] = value;
        printf("Enqueued: %d\n", value);
    }
}

// Function to remove an element from the queue (dequeue)
int dequeue() {
    int dequeuedValue;
    if (isEmpty()) {
        printf("Queue is empty! Cannot dequeue.\n");
        return -1; // Indicate error
    } else {
        dequeuedValue = circularQueue[front];
        if (front == rear) { // Only one element in queue
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % MAX_SIZE; // Circular increment for front
        }
        printf("Dequeued: %d\n", dequeuedValue);
        return dequeuedValue;
    }
}

// Function to peek at the front element of the queue
int peek() {
    if (isEmpty()) {
        printf("Queue is empty! No element to peek.\n");
        return -1; // Indicate error
    } else {
        return circularQueue[front];
    }
}

// Function to display elements of the queue
void display() {
    if (isEmpty()) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Queue elements: ");
    int i = front;
    if (front <= rear) {
        while (i <= rear) {
            printf("%d ", circularQueue[i]);
            i++;
        }
    } else { // Queue has wrapped around
        while (i < MAX_SIZE) {
            printf("%d ", circularQueue[i]);
            i++;
        }
        i = 0;
        while (i <= rear) {
            printf("%d ", circularQueue[i]);
            i++;
        }
    }
    printf("\n");
}

int main() {
    display(); // Queue is empty

    enqueue(10);
    enqueue(20);
    enqueue(30);
    display(); // Expected: 10 20 30

    dequeue(); // Expected: Dequeued: 10
    display(); // Expected: 20 30

    enqueue(40);
    enqueue(50);
    display(); // Expected: 20 30 40 50

    enqueue(60); // Queue should be full now

    printf("Front element: %d\n", peek()); // Expected: 20

    dequeue(); // Expected: Dequeued: 20
    dequeue(); // Expected: Dequeued: 30
    display(); // Expected: 40 50

    enqueue(60); // Enqueue after dequeue, demonstrating wrap-around
    enqueue(70);
    display(); // Expected: 40 50 60 70

    enqueue(80); // Queue should be full again
    display(); // Expected: 40 50 60 70 80

    dequeue(); // Expected: Dequeued: 40
    dequeue(); // Expected: Dequeued: 50
    dequeue(); // Expected: Dequeued: 60
    dequeue(); // Expected: Dequeued: 70
    dequeue(); // Expected: Dequeued: 80
    display(); // Queue is empty

    dequeue(); // Attempt to dequeue from empty queue

    return 0;
}

Advantages and Considerations

Advantages:

• Efficient Memory Utilization: Avoids wasted memory space that occurs in linear queues by reusing dequeued slots.
• Continuous Data Flow: Ideal for buffering and managing a continuous stream of data where old data is constantly being replaced by new.

Considerations:

• Fixed Size: When implemented with arrays, the size of the circular queue is fixed. If more elements need to be stored than MAX_SIZE, resizing is required, which can be complex.
• Complexity: The logic for isFull() and managing front and rear pointers, especially during wrap-around, is slightly more complex than a linear queue.

Conclusion

The circular queue is a powerful and efficient variant of the traditional queue, offering significant improvements in memory utilization by reusing space. Understanding its underlying principles and mastering its implementation in C is a crucial skill for any developer working with data structures, particularly in scenarios requiring robust buffering and scheduling mechanisms. By carefully handling the front and rear pointers with modulo arithmetic, we can create a resilient and effective circular queue.