Circular Queue Implementation Using Array in DSA C

Mental Model

A circular queue uses an array where the end connects back to the start, so we reuse empty spaces efficiently.

Analogy: Imagine a round table with seats numbered in a circle. When you reach the last seat, you go back to the first seat to sit if it's free.

Front -> [ ] [ ] [ ] [ ] [ ] ← Rear
Index -> 0   1   2   3   4
Initially all empty, front and rear at -1

Dry Run Walkthrough

Input: Create circular queue of size 5, enqueue 3 elements (10, 20, 30), dequeue 1 element, enqueue 2 elements (40, 50), then enqueue 1 element (60) to test wrap-around

Goal: Show how elements wrap around in the array and how front and rear pointers move

Step 1: Enqueue 10

10 -> null, front=0, rear=0, array=[10, _, _, _, _]

Why: First element sets front and rear to 0

Step 2: Enqueue 20

10 -> 20 -> null, front=0, rear=1, array=[10, 20, _, _, _]

Why: Rear moves forward to add new element

Step 3: Enqueue 30

10 -> 20 -> 30 -> null, front=0, rear=2, array=[10, 20, 30, _, _]

Why: Rear moves forward again

Step 4: Dequeue (remove 10)

20 -> 30 -> null, front=1, rear=2, array=[10, 20, 30, _, _]

Why: Front moves forward to remove element

Step 5: Enqueue 40

20 -> 30 -> 40 -> null, front=1, rear=3, array=[10, 20, 30, 40, _]

Why: Rear moves forward to add element

Step 6: Enqueue 50

20 -> 30 -> 40 -> 50 -> null, front=1, rear=4, array=[10, 20, 30, 40, 50]

Why: Rear moves forward to last index

Step 7: Enqueue 60 (wrap-around)

20 -> 30 -> 40 -> 50 -> 60 -> null, front=1, rear=0, array=[60, 20, 30, 40, 50]

Why: Rear wraps to start of array to reuse space

Result:

20 -> 30 -> 40 -> 50 -> 60 -> null, front=1, rear=0, array=[60, 20, 30, 40, 50]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

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

void initQueue(CircularQueue *q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(CircularQueue *q) {
    return ((q->rear + 1) % SIZE == q->front);
}

int isEmpty(CircularQueue *q) {
    return (q->front == -1);
}

void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
        q->rear = 0;
        q->arr[q->rear] = value;
        return;
    }
    q->rear = (q->rear + 1) % SIZE; // move rear forward circularly
    q->arr[q->rear] = value;
}

int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int val = q->arr[q->front];
    if (q->front == q->rear) {
        // only one element was present
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % SIZE; // move front forward circularly
    }
    return val;
}

void display(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    int i = q->front;
    while (1) {
        printf("%d", q->arr[i]);
        if (i == q->rear) break;
        printf(" -> ");
        i = (i + 1) % SIZE;
    }
    printf(" -> null\n");
}

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

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    display(&q);

    int removed = dequeue(&q);
    printf("Dequeued: %d\n", removed);
    display(&q);

    enqueue(&q, 40);
    enqueue(&q, 50);
    display(&q);

    enqueue(&q, 60); // should wrap around
    display(&q);

    return 0;
}

if (isFull(q)) {

check if queue is full to prevent overflow

if (isEmpty(q)) {

initialize front and rear when queue is empty

q->rear = (q->rear + 1) % SIZE;

advance rear pointer circularly to next position

int val = q->arr[q->front];

store value at front to return after dequeue

if (q->front == q->rear) {

reset queue when last element is dequeued

q->front = (q->front + 1) % SIZE;

advance front pointer circularly after dequeue

while (1) { ... i = (i + 1) % SIZE; }

iterate from front to rear circularly to display queue

Output

10 -> 20 -> 30 -> null

Dequeued: 10

20 -> 30 -> null

20 -> 30 -> 40 -> 50 -> null

20 -> 30 -> 40 -> 50 -> 60 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we only move pointers and assign values without shifting elements

Space: O(n) because we use a fixed-size array of size n to store elements

vs Alternative: Compared to a normal queue using array that shifts elements on dequeue (O(n)), circular queue avoids shifting by wrapping pointers, making operations O(1)

Edge Cases

Empty queue dequeue

Prints 'Queue is empty' and returns -1 without crashing

DSA C

if (isEmpty(q)) { printf("Queue is empty\n"); return -1; }

Full queue enqueue

Prints 'Queue is full' and does not add element

DSA C

if (isFull(q)) { printf("Queue is full\n"); return; }

Single element enqueue and dequeue

Front and rear reset to -1 after removing last element

DSA C

if (q->front == q->rear) { q->front = -1; q->rear = -1; }

When to Use This Pattern

When you need a queue with fixed size and want to reuse freed spaces efficiently, use circular queue with array to avoid costly shifts.

Common Mistakes

Mistake: Not wrapping rear or front pointers using modulo, causing index out of bounds
Fix: Always update pointers with modulo operation: (pointer + 1) % SIZE

Mistake: Not resetting front and rear to -1 when queue becomes empty after dequeue
Fix: Check if front equals rear after dequeue and reset both to -1

Summary

Implements a queue using a fixed-size array where rear wraps to front to reuse space.

Use when you want efficient fixed-size queue operations without shifting elements.

The key is to move front and rear pointers circularly using modulo to manage wrap-around.