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 where people sit in seats numbered 0 to n-1. When you reach the last seat, you go back to the first seat to fill empty spots.

Front and Rear pointers moving in a circle:

[0] -> [1] -> [2] -> [3] -> [4]
 ↑                       ↑
Rear                    Front

Empty spots wrap around the array.

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 enqueue and dequeue work with wrap-around in a circular queue using an array.

Step 1: Enqueue 10

[10] -> [ ] -> [ ] -> [ ] -> [ ]
Front=0, Rear=0

Why: First element goes to index 0, front and rear both point here.

Step 2: Enqueue 20

[10] -> [20] -> [ ] -> [ ] -> [ ]
Front=0, Rear=1

Why: Rear moves forward to index 1 to add new element.

Step 3: Enqueue 30

[10] -> [20] -> [30] -> [ ] -> [ ]
Front=0, Rear=2

Why: Rear moves forward to index 2 to add new element.

Step 4: Dequeue one element (10)

[ ] -> [20] -> [30] -> [ ] -> [ ]
Front=1, Rear=2

Why: Front moves forward to index 1, removing the first element.

Step 5: Enqueue 40

[ ] -> [20] -> [30] -> [40] -> [ ]
Front=1, Rear=3

Why: Rear moves forward to index 3 to add new element.

Step 6: Enqueue 50

[ ] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=4

Why: Rear moves forward to index 4 to add new element.

Step 7: Enqueue 60 (wrap-around)

[60] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=0

Why: Rear wraps to index 0 because array end reached, reusing empty spot.

Result:

[60] -> [20] -> [30] -> [40] -> [50]
Front=1, Rear=0

Annotated Code

DSA C#

using System;

public class CircularQueue
{
    private int[] arr;
    private int front;
    private int rear;
    private int size;

    public CircularQueue(int capacity)
    {
        arr = new int[capacity];
        front = -1;
        rear = -1;
        size = capacity;
    }

    public bool IsEmpty()
    {
        return front == -1;
    }

    public bool IsFull()
    {
        return (rear + 1) % size == front;
    }

    public void Enqueue(int value)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full");
            return;
        }
        if (IsEmpty())
        {
            front = 0; // first element added
        }
        rear = (rear + 1) % size; // move rear forward circularly
        arr[rear] = value; // insert value
    }

    public int Dequeue()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty");
            return -1;
        }
        int result = arr[front];
        if (front == rear)
        {
            front = -1; // queue becomes empty
            rear = -1;
        }
        else
        {
            front = (front + 1) % size; // move front forward circularly
        }
        return result;
    }

    public void PrintQueue()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty");
            return;
        }
        int i = front;
        while (true)
        {
            Console.Write(arr[i] + " ");
            if (i == rear) break;
            i = (i + 1) % size;
        }
        Console.WriteLine();
    }
}

public class Program
{
    public static void Main()
    {
        CircularQueue cq = new CircularQueue(5);
        cq.Enqueue(10);
        cq.Enqueue(20);
        cq.Enqueue(30);
        cq.PrintQueue();

        cq.Dequeue();
        cq.PrintQueue();

        cq.Enqueue(40);
        cq.Enqueue(50);
        cq.PrintQueue();

        cq.Enqueue(60); // wrap-around enqueue
        cq.PrintQueue();
    }
}

if (IsFull())

Check if queue is full before enqueue to avoid overflow

if (IsEmpty()) { front = 0; }

Set front to 0 when adding first element

rear = (rear + 1) % size;

Move rear forward circularly to next index

arr[rear] = value;

Insert new value at rear position

if (IsEmpty())

Check if queue is empty before dequeue

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

Reset front and rear when last element is dequeued

front = (front + 1) % size;

Move front forward circularly after dequeue

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

Traverse queue circularly from front to rear for printing

Output

10 20 30 

20 30 

20 30 40 50 

20 30 40 50 60 

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we use direct index calculations 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 indices, making operations efficient.

Edge Cases

Empty queue dequeue

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

DSA C#

if (IsEmpty()) { Console.WriteLine("Queue is empty"); return -1; }

Full queue enqueue

Prints 'Queue is full' and does not add element

DSA C#

if (IsFull()) { Console.WriteLine("Queue is full"); return; }

Single element enqueue and dequeue

Front and rear reset to -1 after dequeue to mark empty queue

DSA C#

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

When to Use This Pattern

When you need a fixed-size queue that efficiently reuses space without shifting elements, use the circular queue pattern with modular arithmetic to wrap indices.

Common Mistakes

Mistake: Not wrapping rear or front indices using modulo, causing index out of bounds errors.
Fix: Always update rear and front as (index + 1) % size to wrap around the array.

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

Summary

Implements a queue using a fixed-size array where rear and front wrap around to reuse space.

Use when you want efficient enqueue and dequeue in a fixed-size buffer without shifting elements.

The key is to move front and rear pointers circularly using modulo to avoid wasted space.

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 efficiently uses the array space by reusing freed slots.

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

C. It automatically sorts the elements in the queue.

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

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 treats the array as circular, so when rear reaches the end, it wraps around to use empty slots at the front, efficiently using all available space.

3. Final Answer:

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

4. Quick Check:

   Circular queue reuses space = Advantage A [OK]

Hint: Circular queue reuses space freed at front [OK]

Common Mistakes:

• Thinking circular queue increases array size
• Believing it sorts elements automatically
• Assuming it stores different data types

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 == n

B. rear == front

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

D. front == 0 && rear == n - 1

Solution

1. Step 1: Understand circular queue full condition

   In a circular queue, the queue is full when the next position of rear (circularly) is front.

2. Step 2: Express condition mathematically

   This means (rear + 1) modulo n equals front, ensuring no overlap and full queue detection.

3. Final Answer:

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

4. Quick Check:

   Full if next rear equals front = D [OK]

Hint: Full when next rear wraps to front [OK]

Common Mistakes:

• Using rear == front as full (actually empty)
• Checking rear == n ignoring wrap-around
• Using front == 0 && rear == n - 1 only (linear queue)

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = 0 and rear = 3. After performing Enqueue(10) and Dequeue(), what are the values of front and rear?

medium

A. front = 0, rear = 4

B. front = 1, rear = 3

C. front = 0, rear = 3

D. front = 1, rear = 4

Solution

1. Step 1: Perform Enqueue operation

   Enqueue increments rear circularly: rear = (3 + 1) % 5 = 4.

2. Step 2: Perform Dequeue operation

   Dequeue increments front circularly: front = (0 + 1) % 5 = 1.

3. Final Answer:

   front = 1, rear = 4 -> Option D

4. Quick Check:

   Enqueue rear+1=4, Dequeue front+1=1 [OK]

Hint: Increment indices modulo size after enqueue/dequeue [OK]

Common Mistakes:

• Not wrapping indices with modulo
• Updating front on enqueue or rear on dequeue
• Confusing initial and final index values

4. Given this snippet of circular queue code, what is the error?

int n = 5;
int front = 0, rear = 0;
int[] queue = new int[n];

// Enqueue operation
rear = (rear + 1) % n;
queue[rear] = 10;

// Dequeue operation
front = (front + 1) % n;
int x = queue[front];

// Check if queue is empty
if (front == rear)
    Console.WriteLine("Queue is empty");

medium

A. The enqueue operation increments rear before inserting, causing off-by-one error.

B. The initial values of front and rear cause the first enqueue to overwrite data.

C. The empty check condition is incorrect; it should be (rear + 1) % n == front.

D. The dequeue operation should decrement front instead of incrementing.

Solution

1. Step 1: Analyze enqueue operation

   Incrementing rear before inserting means the first element is placed at index 1, skipping index 0, which wastes space and causes off-by-one errors.

2. Step 2: Understand correct enqueue logic

   Enqueue should insert at current rear, then increment rear after insertion or handle indices carefully to avoid skipping slots.

3. Final Answer:

   The enqueue operation increments rear before inserting, causing off-by-one error. -> Option A

4. Quick Check:

   Increment rear before insert = off-by-one error B [OK]

Hint: Insert before incrementing rear to avoid skipping slots [OK]

Common Mistakes:

• Confusing empty and full conditions
• Incrementing front on enqueue or rear on dequeue
• Ignoring initial index positions

5. You have a circular queue of size 6. Initially, front = 4 and rear = 2. The queue currently holds 4 elements. Which of the following sequences of operations will cause the queue to become full?

hard

A. Enqueue three times, then dequeue once, then enqueue once.

B. Dequeue once, then enqueue three times.

C. Enqueue three times without any dequeue.

D. Dequeue twice, then enqueue five times.

Solution

1. Step 1: Calculate current queue state

   Size is 6, front=4, rear=2, holding 4 elements means the queue is partially filled with wrap-around.

2. Step 2: Analyze each operation sequence

   A: Dequeue once (remove 1), enqueue three times (add 3) -> net +2 elements, total 6 (full). B: Enqueue three times (add 3), dequeue once (remove 1), enqueue once (add 1) -> net +3 elements, total 7 (overflow). C: Enqueue three times without dequeue would overflow (since only 2 slots free). D: Dequeue twice (remove 2), enqueue five times (add 5) -> net +3 elements, total 7 (overflow).

3. Step 3: Identify which sequence is valid without overflow

   Only Dequeue once, then enqueue three times. correctly balances operations to reach full without overflow errors.

4. Final Answer:

   Dequeue once, then enqueue three times. -> Option B

5. Quick Check:

   Dequeue 1 + Enqueue 3 fills queue = A [OK]

Hint: Track net enqueue minus dequeue to reach full capacity [OK]

Common Mistakes:

• Ignoring wrap-around effect on indices
• Assuming enqueue always succeeds without checking full
• Miscounting elements after operations