Circular Queue Implementation Using Array in DSA Rust

Mental Model

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

Analogy: Imagine a round table with fixed seats. When someone leaves, the next person can sit there without needing a bigger table.

Front -> [ ] [ ] [ ] [ ] [ ] ← Rear
Index -> 0   1   2   3   4
Initially all empty, front and rear point to -1 or null.

Dry Run Walkthrough

Input: Create circular queue of size 5, enqueue 3, enqueue 4, enqueue 5, dequeue 1, enqueue 6

Goal: Show how the circular queue wraps around and reuses space after dequeue

Step 1: enqueue 3 into empty queue

Front=0, Rear=0, Array=[3, _, _, _, _]

Why: First element sets front and rear to 0

Step 2: enqueue 4

Front=0, Rear=1, Array=[3, 4, _, _, _]

Why: Rear moves forward to next index

Step 3: enqueue 5

Front=0, Rear=2, Array=[3, 4, 5, _, _]

Why: Rear moves forward again

Step 4: dequeue one element (3)

Front=1, Rear=2, Array=[3, 4, 5, _, _]

Why: Front moves forward, old value stays but is ignored

Step 5: enqueue 6, rear wraps to index 3

Front=1, Rear=3, Array=[3, 4, 5, 6, _]

Why: Rear moves forward circularly to next free slot

Result:

Front=1, Rear=3, Array=[3, 4, 5, 6, _]
Queue elements in order: 4 -> 5 -> 6 -> null

Annotated Code

DSA Rust

struct CircularQueue {
    size: usize,
    front: isize,
    rear: isize,
    data: Vec<Option<i32>>,
}

impl CircularQueue {
    fn new(size: usize) -> Self {
        Self {
            size,
            front: -1,
            rear: -1,
            data: vec![None; size],
        }
    }

    fn is_empty(&self) -> bool {
        self.front == -1
    }

    fn is_full(&self) -> bool {
        (self.rear + 1) % self.size as isize == self.front
    }

    fn enqueue(&mut self, val: i32) -> bool {
        if self.is_full() {
            return false; // queue full
        }
        if self.is_empty() {
            self.front = 0;
            self.rear = 0;
            self.data[self.rear as usize] = Some(val);
            return true;
        }
        self.rear = (self.rear + 1) % self.size as isize;
        self.data[self.rear as usize] = Some(val);
        true
    }

    fn dequeue(&mut self) -> Option<i32> {
        if self.is_empty() {
            return None; // queue empty
        }
        let val = self.data[self.front as usize].take();
        if self.front == self.rear {
            self.front = -1;
            self.rear = -1;
        } else {
            self.front = (self.front + 1) % self.size as isize;
        }
        val
    }

    fn display(&self) {
        if self.is_empty() {
            println!("Queue is empty");
            return;
        }
        let mut i = self.front;
        loop {
            if let Some(v) = self.data[i as usize] {
                print!("{} -> ", v);
            }
            if i == self.rear {
                break;
            }
            i = (i + 1) % self.size as isize;
        }
        println!("null");
    }
}

fn main() {
    let mut cq = CircularQueue::new(5);
    cq.enqueue(3);
    cq.enqueue(4);
    cq.enqueue(5);
    cq.display();
    cq.dequeue();
    cq.display();
    cq.enqueue(6);
    cq.display();
}

if self.is_full() { return false; }

check if queue is full to prevent overwrite

if self.is_empty() { self.front = 0; self.rear = 0; self.data[self.rear as usize] = Some(val); return true; }

initialize front and rear on first enqueue

self.rear = (self.rear + 1) % self.size as isize; self.data[self.rear as usize] = Some(val);

move rear pointer circularly and insert value

if self.is_empty() { return None; }

check if queue is empty before dequeue

let val = self.data[self.front as usize].take();

remove value at front and store to return

if self.front == self.rear { self.front = -1; self.rear = -1; } else { self.front = (self.front + 1) % self.size as isize; }

update front pointer or reset if queue becomes empty

loop { print value at i; if i == rear break; i = (i + 1) % size; }

iterate circularly from front to rear to display queue

Output

3 -> 4 -> 5 -> null

4 -> 5 -> null

4 -> 5 -> 6 -> null

Complexity Analysis

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

Space: O(n) for fixed size array storing n elements

vs Alternative: Compared to linear queue, circular queue reuses space efficiently without shifting elements, improving enqueue/dequeue speed

Edge Cases

enqueue on full queue

enqueue returns false and does not add element

DSA Rust

if self.is_full() { return false; }

dequeue on empty queue

dequeue returns None indicating empty queue

DSA Rust

if self.is_empty() { return None; }

dequeue last element

front and rear reset to -1 indicating empty queue

DSA Rust

if self.front == self.rear { self.front = -1; self.rear = -1; }

When to Use This Pattern

When you need a fixed-size queue that efficiently reuses space without shifting elements, use a circular queue with array to achieve O(1) enqueue and dequeue.

Common Mistakes

Mistake: Not wrapping rear or front pointers circularly causing index out of bounds
Fix: Use modulo operation to wrap pointers: (pointer + 1) % size

Mistake: Confusing full and empty conditions leading to incorrect enqueue or dequeue
Fix: Use front == -1 for empty and (rear + 1) % size == front for full

Summary

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

Use when you want a queue with fixed capacity and efficient enqueue/dequeue without shifting.

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 efficiently uses all available space by wrapping around the array.

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

C. It automatically sorts the elements in the queue.

D. It uses less memory than a linear queue.

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 is free space 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 spaces and efficient use of the array.

3. Final Answer:

   It efficiently uses all available space by wrapping around the array. -> Option A

4. Quick Check:

   Circular queue = efficient space use [OK]

Hint: Circular queue reuses space by wrapping indices [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing it uses less memory than linear queue
• Assuming it stores different data types

2. Which of the following Rust code snippets correctly initializes a circular queue array of size 5 with front and rear pointers set to -1?

easy

A. let mut queue: [i32; 5]; let front: i32; let rear: i32;

B. let queue = Vec::new(); let front = 0; let rear = 0;

C. let mut queue: [i32; 5] = [1; 5]; let mut front: usize = 0; let mut rear: usize = 0;

D. let mut queue: [i32; 5] = [0; 5]; let mut front: i32 = -1; let mut rear: i32 = -1;

Solution

1. Step 1: Check array initialization

   let mut queue: [i32; 5] = [0; 5]; let mut front: i32 = -1; let mut rear: i32 = -1; initializes a fixed-size array of 5 integers with all zeros, which is correct for a circular queue.

2. Step 2: Check front and rear initialization

   let mut queue: [i32; 5] = [0; 5]; let mut front: i32 = -1; let mut rear: i32 = -1; sets front and rear to -1, indicating the queue is empty, which is standard practice.

3. Final Answer:

   let mut queue: [i32; 5] = [0; 5]; let mut front: i32 = -1; let mut rear: i32 = -1; -> Option D

4. Quick Check:

   Correct array and pointers initialization = let mut queue: [i32; 5] = [0; 5]; let mut front: i32 = -1; let mut rear: i32 = -1; [OK]

Hint: Initialize array with zeros and front/rear as -1 [OK]

Common Mistakes:

• Using Vec instead of fixed-size array
• Not initializing front and rear to -1
• Leaving variables uninitialized

3. Consider this Rust code snippet for a circular queue of size 5. After these operations, what is the state of the queue array?

let mut queue = [0; 5];
let mut front: i32 = -1;
let mut rear: i32 = -1;

// Enqueue 10
if rear == -1 {
    front = 0;
    rear = 0;
    queue[rear as usize] = 10;
} else {
    rear = (rear + 1) % 5;
    queue[rear as usize] = 10;
}

// Enqueue 20
rear = (rear + 1) % 5;
queue[rear as usize] = 20;

// Dequeue
front = (front + 1) % 5;

// Enqueue 30
rear = (rear + 1) % 5;
queue[rear as usize] = 30;

medium

A. [10, 20, 30, 0, 0]

B. [0, 20, 0, 30, 0]

C. [10, 20, 0, 30, 0]

D. [0, 0, 20, 30, 0]

Solution

1. Step 1: Trace enqueue and dequeue operations

   Initially front = -1, rear = -1, queue = [0,0,0,0,0]. - Enqueue 10: front=0, rear=0, queue[0]=10 -> [10,0,0,0,0] - Enqueue 20: rear=(0+1)%5=1, queue[1]=20 -> [10,20,0,0,0] - Dequeue: front=(0+1)%5=1 (10 removed logically) - Enqueue 30: rear=(1+1)%5=2, queue[2]=30 -> [10,20,30,0,0]

2. Step 2: Determine final queue state

   Queue array is [10, 20, 30, 0, 0]. Although 10 is logically dequeued, it remains in the array until overwritten.

3. Final Answer:

   [10, 20, 0, 30, 0] -> Option C

4. Quick Check:

   After dequeue, front moves, old value stays [OK]

Hint: Remember dequeue moves front, old data stays until overwritten [OK]

Common Mistakes:

• Assuming dequeued elements are erased immediately
• Not applying modulo for rear and front
• Mixing up front and rear positions

4. The following Rust code for enqueue in a circular queue has a bug. What is the error?

fn enqueue(queue: &mut [i32; 5], front: &mut i32, rear: &mut i32, value: i32) {
    if (*rear + 1) % 5 == *front {
        println!("Queue is full");
        return;
    }
    if *rear == -1 {
        *front = 0;
        *rear = 0;
    } else {
        *rear = (*rear + 1) % 5;
    }
    queue[*rear as usize] = value;
}

medium

A. The condition to check if queue is full is incorrect.

B. The initial check for empty queue should be *front == -1, not *rear == -1.

C. The queue array should be mutable but is not.

D. The modulo operation should use queue length minus one.

Solution

1. Step 1: Analyze empty queue check

   The code checks if *rear == -1 to detect empty queue, but standard practice is to check if *front == -1 because front indicates the start of queue.

2. Step 2: Understand impact of wrong check

   If *rear == -1 but *front is not -1, the queue might be incorrectly treated as empty, causing logic errors.

3. Final Answer:

   The initial check for empty queue should be *front == -1, not *rear == -1. -> Option B

4. Quick Check:

   Empty queue check uses front pointer [OK]

Hint: Empty queue means front == -1, not rear [OK]

Common Mistakes:

• Checking rear instead of front for empty queue
• Incorrect modulo usage
• Not passing mutable references properly

5. You have a circular queue of size 4 implemented using an array. Initially, front = 2 and rear = 1 (meaning the queue is full). You perform one dequeue operation followed by two enqueue operations with values 50 and 60. What will be the final positions of front and rear pointers?

hard

A. front = 3, rear = 3

B. front = 3, rear = 0

C. front = 3, rear = 1

D. front = 2, rear = 3

Solution

1. Step 1: Understand initial full queue state

   Queue size = 4, front = 2, rear = 1 means the queue is full because (rear + 1) % size == front ( (1+1)%4=2 ).

2. Step 2: Perform dequeue operation

   Dequeue moves front forward: front = (2 + 1) % 4 = 3. Rear remains 1.

3. Step 3: Perform first enqueue (50)

   rear = (1 + 1) % 4 = 2, insert 50 at index 2.

4. Step 4: Perform second enqueue (60)

   rear = (2 + 1) % 4 = 3, insert 60 at index 3.

5. Final Answer:

   front = 3, rear = 3 -> Option A

6. Quick Check:

   After dequeue and two enqueues, pointers wrap correctly [OK]

Hint: Update front on dequeue, rear on enqueue with modulo [OK]

Common Mistakes:

• Not applying modulo after pointer increment
• Confusing front and rear updates
• Assuming queue is empty after dequeue