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.

Practice

1. What is the main advantage of using a circular queue over a simple linear queue when implemented using an array?

easy

A. It automatically sorts the elements in the queue

B. It allows storing different data types in the same queue

C. It increases the maximum size of the queue beyond the array length

D. It efficiently uses the array space by reusing freed slots

Solution

1. Step 1: Understand linear queue limitation

   In a linear queue using an array, once the rear reaches the end, no more elements can be added even if there are empty slots at the front.

2. Step 2: Circular queue advantage

   A circular queue connects the end of the array back to the front, allowing reuse of empty slots freed by dequeuing, thus using space efficiently.

3. Final Answer:

   It efficiently uses the array space by reusing freed slots -> Option D

4. Quick Check:

   Circular queue reuses space = Advantage [OK]

Hint: Circular queue reuses space freed by dequeue [OK]

Common Mistakes:

• Thinking circular queue increases array size
• Believing it sorts elements automatically
• Confusing data type flexibility with queue type

2. Which of the following is the correct condition to check if a circular queue is full when using an array of size n with front and rear indices?

easy

A. rear == (front + 1) % n

B. front == rear

C. front == (rear + 1) % n

D. rear == n - 1

Solution

1. Step 1: Recall circular queue full condition

   The queue is full when the next position of rear (circularly) is front, meaning no space to insert new element.

2. Step 2: Express condition mathematically

   This condition is: front == (rear + 1) % n, where % is modulo operator to wrap around.

3. Final Answer:

   front == (rear + 1) % n -> Option C

4. Quick Check:

   Full if front is next to rear circularly = Condition B [OK]

Hint: Full when front is just after rear modulo array size [OK]

Common Mistakes:

• Using rear == (front + 1) % n (wrong direction)
• Checking front == rear (means empty, not full)
• Checking rear == n - 1 (linear queue condition)

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = -1 and rear = -1. After the following operations:
enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50), enqueue(60)
What will be the values of front and rear?

medium

A. front = 1, rear = 0

B. front = 0, rear = 4

C. front = 1, rear = 3

D. front = 2, rear = 1

Solution

1. Step 1: Trace enqueue and dequeue operations

   Start: front = -1, rear = -1
   enqueue(10): front=0, rear=0
   enqueue(20): rear=1
   enqueue(30): rear=2
   dequeue(): front=1 (removed 10)
   enqueue(40): rear=3
   enqueue(50): rear=4
   enqueue(60): rear wraps to 0 (circular)

2. Step 2: Final front and rear values

   After last enqueue, front=1, rear=0

3. Final Answer:

   front = 1, rear = 0 -> Option A

4. Quick Check:

   After wrap, rear=0 and front moved to 1 [OK]

Hint: Track front/rear step-by-step with wrap-around [OK]

Common Mistakes:

• Not updating front after dequeue
• Forgetting rear wraps to 0 after reaching end
• Mixing front and rear indices

4. Given the following code snippet for dequeue operation in a circular queue, identify the error:

int dequeue() {
  if (front == -1) {
    printf("Queue is empty\n");
    return -1;
  }
  int data = queue[front];
  if (front == rear) {
    front = rear = -1;
  } else {
    front = front + 1;
  }
  return data;
}

medium

A. front should be updated as (front + 1) % size to wrap around

B. rear should be incremented instead of front

C. The check for empty queue is incorrect

D. Data should be returned after updating front

Solution

1. Step 1: Understand circular queue front update

   In circular queue, front index must wrap around using modulo when incremented to stay within array bounds.

2. Step 2: Identify error in front update

   Code uses front = front + 1; which can go beyond array size. Correct is front = (front + 1) % size.

3. Final Answer:

   front should be updated as (front + 1) % size to wrap around -> Option A

4. Quick Check:

   Use modulo for front increment in circular queue [OK]

Hint: Use modulo when incrementing front or rear [OK]

Common Mistakes:

• Incrementing front without modulo wrap
• Confusing front and rear updates
• Returning data before updating front

5. You have a circular queue of size 6. After performing these operations:
enqueue(5), enqueue(10), enqueue(15), dequeue(), dequeue(), enqueue(20), enqueue(25), enqueue(30), enqueue(35)
What will be the queue content from front to rear?

hard

A. 5 -> 10 -> 15 -> 20 -> 25 -> 30 -> null

B. 15 -> 20 -> 25 -> 30 -> 35 -> null

C. 10 -> 15 -> 20 -> 25 -> 30 -> null

D. 20 -> 25 -> 30 -> 35 -> 5 -> null

Solution

1. Step 1: Trace each operation step-by-step

   Start front = -1, rear = -1
   enqueue(5): front=0, rear=0, queue=[5]
   enqueue(10): rear=1, queue=[5,10]
   enqueue(15): rear=2, queue=[5,10,15]
   dequeue(): front=1 (removed 5)
   dequeue(): front=2 (removed 10)
   enqueue(20): rear=3, queue=[5,10,15,20]
   enqueue(25): rear=4, queue=[5,10,15,20,25]
   enqueue(30): rear=5, queue=[5,10,15,20,25,30]
   enqueue(35): rear wraps to 0, queue=[35,10,15,20,25,30]

2. Step 2: Identify current front and rear and queue content

   front=2, rear=0
   Queue elements from front to rear circularly: 15 (index 2), 20 (3), 25 (4), 30 (5), 35 (0)

3. Final Answer:

   15 -> 20 -> 25 -> 30 -> 35 -> null -> Option B

4. Quick Check:

   Queue content from front to rear matches 15 -> 20 -> 25 -> 30 -> 35 -> null [OK]

Hint: Track front and rear indices carefully with wrap-around [OK]

Common Mistakes:

• Ignoring wrap-around when rear reaches end
• Listing elements linearly without circular order
• Forgetting to update front after dequeues