Circular Array Queue Implementation

Welcome back! In our last lesson, we explored the conceptual foundation of the Queue Abstract Data Type, focusing on its First-In, First-Out (FIFO) behavior and its core operations. You learned what a queue is and why it's useful.

Today, we'll dive into the practical side. Our goal is to implement a queue using a circular array to manage memory efficiently. We'll start by seeing why a simple array implementation is wasteful and then discover how a clever technique—the circular array—solves this problem elegantly and efficiently.

1. The Challenge with a Naive Array Implementation

A simple array seems like a natural starting point for implementing a queue. We could use two indices, front and rear, to keep track of the start and end of the queue.

• To enqueue, we add an element at the rear index and increment rear.
• To dequeue, we remove the element from the front index and increment front.

However, this approach has a significant flaw. As we dequeue elements, the front index moves forward, leaving unused, "dead" space at the beginning of the array. The queue effectively marches across the array until rear hits the end, at which point we can't add any more elements, even if the array is mostly empty!

The following video explains this problem very clearly.

This memory inefficiency is precisely the problem we need to solve. We want to be able to reuse those empty slots at the beginning of the array.

2. The Solution: The Circular Array

The solution is to treat the array not as a line, but as a circle. When the front or rear pointer reaches the end of the array, it "wraps around" to the beginning. This allows us to use the entire capacity of the array continuously.

How do we achieve this "wrap-around" behavior in code? The key is the modulo operator (%). The expression (index + 1) % SIZE will increment an index normally, but when index reaches SIZE - 1, the result of (SIZE - 1 + 1) % SIZE, which is SIZE % SIZE, becomes 0. This elegantly brings the index back to the start of the array.

Let's see this concept explained in the same video.

With this powerful yet simple trick, we can build a much more efficient queue.

3. Implementing a Circular Queue in C

Now, let's translate this concept into a full C implementation. We'll build a dynamic circular queue that can be created with any capacity. A great, modern walkthrough of this is provided by Jacob Sorber. We will follow his implementation strategy.

First, let's define the struct that will represent our queue. It needs to hold the array itself, the indices, and some metadata.

typedef struct {
    int *values;      // Pointer to the dynamically allocated array
    int head, tail;   // Indices for the front and rear
    int num_entries;  // Current number of items in the queue
    int size;         // Total capacity of the array
} queue_t;

Notice the num_entries field. Tracking the number of items directly makes checking if the queue is full or empty very simple and robust.

The following video will guide us through building the functions for this struct.

The video effectively shows that we don't actually "remove" data during a dequeue. We simply move the head pointer. The old data is considered invalid and will eventually be overwritten when the tail pointer wraps around and reaches that position again.

The image below provides a great step-by-step visualization of these operations in action.

4. Complete Code Example

Here is a complete, well-commented C program for a circular queue, based on the implementation you just studied. You can compile and run this code to experiment with it. Try changing the size and the sequence of operations in main to solidify your understanding.

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

// Define the structure for our circular queue
typedef struct {
    int *values;      // Pointer to the dynamically allocated array
    int head, tail;   // Indices for the front (head) and rear (tail)
    int num_entries;  // Current number of items in the queue
    int size;         // Total capacity of the array
} queue_t;

// Function to initialize a new queue
void queue_init(queue_t *q, int size) {
    q->size = size;
    q->values = malloc(sizeof(int) * q->size);
    q->num_entries = 0;
    q->head = 0;
    q->tail = 0;
}

// Function to check if the queue is empty
bool queue_empty(queue_t *q) {
    return (q->num_entries == 0);
}

// Function to check if the queue is full
bool queue_full(queue_t *q) {
    return (q->num_entries == q->size);
}

// Function to add an element to the rear of the queue (enqueue)
bool enqueue(queue_t *q, int value) {
    if (queue_full(q)) {
        return false; // Cannot add to a full queue
    }

    // Place the new value at the tail position
    q->values[q->tail] = value;
    q->num_entries++;
    
    // Update the tail index, wrapping around if necessary
    q->tail = (q->tail + 1) % q->size;

    return true;
}

// Function to remove and return an element from the front of the queue (dequeue)
int dequeue(queue_t *q) {
    if (queue_empty(q)) {
        return INT_MIN; // Return a sentinel value for an empty queue
    }

    // Get the value from the head position
    int result = q->values[q->head];
    q->num_entries--;

    // Update the head index, wrapping around if necessary
    q->head = (q->head + 1) % q->size;

    return result;
}

// Function to free the memory used by the queue
void queue_destroy(queue_t *q) {
    free(q->values);
}

int main() {
    queue_t my_queue;
    int queue_size = 5;
    
    // Initialize the queue with a size of 5
    queue_init(&my_queue, queue_size);

    printf("Enqueuing 5 items...\n");
    enqueue(&my_queue, 10);
    enqueue(&my_queue, 20);
    enqueue(&my_queue, 30);
    enqueue(&my_queue, 40);
    enqueue(&my_queue, 50);

    // This enqueue should fail because the queue is full
    if (!enqueue(&my_queue, 60)) {
        printf("Queue is full. Could not enqueue 60.\n");
    }

    printf("\nDequeuing 3 items...\n");
    printf("Dequeued: %d\n", dequeue(&my_queue));
    printf("Dequeued: %d\n", dequeue(&my_queue));
    printf("Dequeued: %d\n", dequeue(&my_queue));

    printf("\nEnqueuing 2 more items (testing wrap-around)...\n");
    enqueue(&my_queue, 70);
    enqueue(&my_queue, 80);

    printf("\nDequeuing all remaining items...\n");
    while (!queue_empty(&my_queue)) {
        printf("Dequeued: %d\n", dequeue(&my_queue));
    }
    
    // This dequeue should fail because the queue is empty
    int result = dequeue(&my_queue);
    if (result == INT_MIN) {
        printf("\nQueue is empty. Cannot dequeue.\n");
    }

    // Clean up allocated memory
    queue_destroy(&my_queue);

    return 0;
}

Conclusion

In this lesson, you have successfully bridged the gap from theory to practice by implementing a queue. You've learned not just how to implement it, but how to do so efficiently.

Key Takeaways:

• A naive array implementation of a queue is inefficient because it wastes memory as elements are dequeued.
• A circular array solves this by logically connecting the end of the array back to the beginning.
• The modulo operator (%) is the key to implementing the "wrap-around" behavior for the head and tail indices.
• Tracking the number of elements (num_entries) simplifies the logic for checking if the queue is empty or full.
• A complete implementation requires functions for initialization, checking state (isEmpty, isFull), manipulation (enqueue, dequeue), and cleanup (destroy).

Preview of the Next Lesson:
You now have a solid understanding of two fundamental linear data structures: stacks and queues. In the next lesson, we will take a step back to compare them side-by-side. We will also introduce a hybrid data structure called a deque (double-ended queue) and discuss when to choose each of these structures for a given problem.