Designing a Circular Queue 🎯

Welcome to this comprehensive guide on designing a Circular Queue! In this lesson, we'll delve into the world of data structures, focusing on circular queues. By the end of this tutorial, you'll be well-equipped to implement circular queues in your own projects. Let's get started!

What is a Circular Queue? 📝

A Circular Queue is a type of queue that uses a single, fixed-size buffer (array) as if it were connected end-to-end. This structure allows us to utilize all the elements in the array efficiently, as the last element is treated as if it were followed by the first one. This makes circular queues particularly useful when memory is limited.

Creating a Circular Queue 💡

Defining the Types

First, let's define the necessary types for our circular queue:

cpp

#define MAX_SIZE 100
typedef int DataType;

struct CircularQueue {
    DataType* arr;
    int front;
    int rear;
    int size;
};

Here, MAX_SIZE is the maximum capacity of our queue, DataType is the data type that our queue will hold, and CircularQueue is our custom data structure.

Initializing the Circular Queue

Now, let's create a function to initialize our circular queue:

cpp

CircularQueue createCircularQueue(int size) {
    CircularQueue queue;
    queue.arr = (DataType*)malloc(size * sizeof(DataType));
    queue.size = size;
    queue.front = queue.rear = -1;
    return queue;
}

In this function, we allocate memory for our array, set the queue size, and initialize both the front and rear indices to -1, indicating that the queue is currently empty.

Adding Items to the Circular Queue

To add items to the queue, we'll create a function called enqueue:

cpp

void enqueue(CircularQueue* queue, DataType value) {
    if ((queue->rear + 1) % queue->size == queue->front) {
        printf("Queue is full. Cannot enqueue %d.\n", value);
        return;
    }

    queue->rear = (queue->rear + 1) % queue->size;
    queue->arr[queue->rear] = value;
}

Here, we check if the queue is full before adding a new item. If it is, we print an error message and return. Otherwise, we update the rear index and store the new value in the array.

Removing Items from the Circular Queue

To remove items from the queue, we'll create a function called dequeue:

cpp

DataType dequeue(CircularQueue* queue) {
    if (queue->front == -1) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }

    DataType value = queue->arr[queue->front];
    queue->front = (queue->front + 1) % queue->size;
    return value;
}

In this function, we check if the queue is empty before trying to remove an item. If it is, we print an error message and return an invalid value. Otherwise, we update the front index and return the removed value.

Practical Example 💡

Let's see a practical example of using our circular queue:

cpp

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 5
typedef int DataType;

struct CircularQueue {
    DataType* arr;
    int front;
    int rear;
    int size;
};

CircularQueue createCircularQueue(int size) {
    CircularQueue queue;
    queue.arr = (DataType*)malloc(size * sizeof(DataType));
    queue.size = size;
    queue.front = queue.rear = -1;
    return queue;
}

void enqueue(CircularQueue* queue, DataType value) {
    if ((queue->rear + 1) % queue->size == queue->front) {
        printf("Queue is full. Cannot enqueue %d.\n", value);
        return;
    }

    queue->rear = (queue->rear + 1) % queue->size;
    queue->arr[queue->rear] = value;
}

DataType dequeue(CircularQueue* queue) {
    if (queue->front == -1) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }

    DataType value = queue->arr[queue->front];
    queue->front = (queue->front + 1) % queue->size;
    return value;
}

int main() {
    CircularQueue queue = createCircularQueue(MAX_SIZE);

    enqueue(&queue, 1);
    enqueue(&queue, 2);
    enqueue(&queue, 3);
    enqueue(&queue, 4);
    enqueue(&queue, 5);

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Dequeued: %d\n", dequeue(&queue)); // This will print an error message

    return 0;
}

In this example, we create a circular queue with a size of 5, enqueue 5 items, and then dequeue them one by one. The final dequeue attempt results in an error message, as the queue is empty.

Quiz 💡

That's it for our Circular Queue lesson! You now have a solid understanding of what a circular queue is, how to create one, and how to add and remove items. Happy coding! 🚀