Chapter 9 – Circular Queues

Chapter 9: Circular Queues

---

Welcome to Chapter 9! In this chapter, we’ll explore Circular Queues, which are an extension of the basic queue structure. Circular queues optimize memory usage by reusing spaces that are freed when elements are dequeued. This makes them highly useful for scenarios with fixed-size buffers, like operating systems and network packet handling.

---

What is a Circular Queue?

A Circular Queue is a type of queue in which the last position is connected back to the first position, making the queue circular. This means that when the rear of the queue reaches the end of the array, it wraps around to the front (if there’s space) to reuse the vacated positions. Circular queues solve the problem of wasted space in a standard queue implementation where elements are removed from the front but the space isn’t reused.

Here’s a basic diagram of a circular queue:

        Front
         ↓
        [5] -> [6] -> [7] -> [8] -> [0]
                                    ↑
                                   Rear

In this circular queue, after adding an element to the rear, we’ll wrap around to the front to fill any vacated positions.

---

Why Use a Circular Queue?

In a normal queue, once the rear pointer reaches the end of the array, no more elements can be added, even if there are free spaces in the front due to dequeued elements. Circular queues resolve this by allowing the rear pointer to wrap around to the front and reuse those free spaces.

At Emancipation Edutech Private Limited, a circular queue could be used in systems where students access learning modules. When students complete a module and move on, their slot in the queue can be reused by another student.

---

Operations on Circular Queues

The operations on circular queues are similar to those on regular queues but with a few modifications to handle the circular nature. The following are the main operations:

1. Enqueue: Add an element to the rear of the circular queue.
2. Dequeue: Remove an element from the front of the circular queue.
3. Front: Get the front element of the circular queue.
4. IsFull: Check if the queue is full.
5. IsEmpty: Check if the queue is empty.

Let’s see how to implement these operations using an array-based circular queue.

---

Circular Queue Implementation Using an Array

Define the Queue Structure

#include <stdio.h>
#include <stdlib.h>
#define MAX 5 // Size of the circular queue

struct CircularQueue {
    int front, rear;
    int arr[MAX];
};

• front: Index of the front element.
• rear: Index of the rear element.
• arr: Array to store the elements.

Initialize the Circular Queue

void initialize(struct CircularQueue* q) {
    q->front = -1;
    q->rear = -1; // Queue is initially empty
}

Enqueue Operation

void enqueue(struct CircularQueue* q, int value) {
    if ((q->rear + 1) % MAX == q->front) { // Check if the queue is full
        printf("Queue Overflow\n");
        return;
    }
    if (q->front == -1) // If queue is initially empty
        q->front = 0;
    q->rear = (q->rear + 1) % MAX; // Increment rear in a circular manner
    q->arr[q->rear] = value; // Add the value
}

In this case, we use the modulo (%) operator to wrap around the rear pointer when it reaches the end of the array.

Dequeue Operation

int dequeue(struct CircularQueue* q) {
    if (q->front == -1) { // Check if the queue is empty
        printf("Queue Underflow\n");
        return -1; // Return -1 to indicate an error
    }
    int value = q->arr[q->front]; // Store the front value
    if (q->front == q->rear) { // If there was only one element
        q->front = -1;
        q->rear = -1; // Reset the queue
    } else {
        q->front = (q->front + 1) % MAX; // Increment front in a circular manner
    }
    return value;
}

Front Operation

int front(struct CircularQueue* q) {
    if (q->front == -1) { // Check if the queue is empty
        printf("Queue is Empty\n");
        return -1;
    }
    return q->arr[q->front]; // Return the front value
}

Example Usage

int main() {
    struct CircularQueue queue;
    initialize(&queue);

    // Enqueue elements
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);

    // Dequeue an element
    printf("Dequeued element: %d\n", dequeue(&queue));

    // Enqueue another element
    enqueue(&queue, 50);

    // Print the front element
    printf("Front element: %d\n", front(&queue));

    return 0;
}

Output:

Dequeued element: 10
Front element: 20

Notice how, after dequeueing 10, we enqueue another element 50, reusing the space previously held by 10.

---

Circular Queue vs. Linear Queue

Let’s compare circular queues and linear queues to understand the key differences:

Feature	Circular Queue	Linear Queue
Memory Utilization	Utilizes memory efficiently by reusing vacated positions after dequeueing.	Wastes memory as vacated positions aren’t reused.
Overflow Condition	Occurs only when all positions are filled, even if front has moved from the first index.	Occurs when the rear reaches the end, even if there are empty spaces at the front.
Example Usage	Used in scheduling, buffering, and resource management systems like CPU scheduling or network packet handling.	Used in simpler cases, like managing a single queue of tasks.

Circular queues are perfect when you need to manage fixed-size buffers and prevent wasted space.

At Emancipation Edutech Private Limited, circular queues might be used in our learning management systems to efficiently handle student queries or manage the flow of study resources—ensuring no slot goes to waste. To learn more, visit digilearn.cloud, where you can read this book and other educational resources for free.

---

Applications of Circular Queues

Circular queues are used in several real-world applications:

1. CPU Scheduling: Circular queues are often used to manage processes in the round-robin CPU scheduling algorithm. In this method, each process is given an equal share of the CPU, and once its time slice is over, it goes back to the end of the queue.

2. Network Buffers: Circular queues are used in network systems to handle incoming data packets. When one packet is processed, the slot is reused for a new incoming packet, preventing overflow until all slots are filled.

3. Job Scheduling: Printers and other resource management systems use circular queues to manage multiple print jobs without wasting space.

4. Real-Time Systems: In real-time computing environments, circular queues help in managing time-critical tasks efficiently by allowing quick addition and removal of tasks.

---

Advantages and Disadvantages of Circular Queues

Advantages:

• Efficient Memory Utilization: Circular queues allow you to reuse space, making them more memory-efficient than linear queues.
• Prevents Wastage: Since the rear pointer wraps around to the front, the queue can utilize all available positions.
• Great for Fixed Buffers: Ideal for applications that need to manage a fixed number of resources, like buffer handling.

Disadvantages:

• Complex Implementation: The wrap-around behavior introduces some complexity in managing the front and rear pointers.
• Fixed Size: If implemented with arrays, circular queues still suffer from a fixed size limit unless dynamically resized.

---

Conclusion

Circular queues are a powerful extension of linear queues, offering an efficient way to utilize memory, particularly in fixed-size buffers. By mastering circular queues, you’ll be better equipped to handle a variety of real-world problems involving scheduling, buffering, and resource management.

In the next chapter, we will delve deeper into Priority Queues, where elements are dequeued based on their priority rather than their order in the queue.

Until then, keep practicing, stay curious, and remember that learning is a continuous process—just like a circular queue!

---

Next Chapter: Priority Queues