Queue Implementation Using Array in DSA Rust

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to hold the people in order.

Analogy: Imagine a line at a ticket counter. People join at the back and leave from the front, just like a queue using an array where we add at the end and remove from the front.

Front -> [ ] [ ] [ ] [ ] [ ] ← Rear
Indexes:  0   1   2   3   4
Initially empty queue with front and rear pointers.

Dry Run Walkthrough

Input: Start with empty queue of size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter at rear and leave from front using array indexes

Step 1: enqueue 10 at rear

Front=0, Rear=1, Array=[10, _, _, _, _]

Why: Add first element at position 0, rear moves forward

Step 2: enqueue 20 at rear

Front=0, Rear=2, Array=[10, 20, _, _, _]

Why: Add next element at position 1, rear moves forward

Step 3: dequeue from front

Front=1, Rear=2, Array=[_, 20, _, _, _]

Why: Remove element at front index 0 by moving front pointer forward

Step 4: enqueue 30 at rear

Front=1, Rear=3, Array=[_, 20, 30, _, _]

Why: Add new element at position 2, rear moves forward

Result:

Front=1, Rear=3, Array=[_, 20, 30, _, _]
Queue elements from front to rear: 20 -> 30 -> null

Annotated Code

DSA Rust

struct Queue {
    arr: [Option<i32>; 5],
    front: usize,
    rear: usize,
    size: usize,
}

impl Queue {
    fn new() -> Self {
        Queue {
            arr: [None; 5],
            front: 0,
            rear: 0,
            size: 0,
        }
    }

    fn enqueue(&mut self, val: i32) -> bool {
        if self.size == self.arr.len() {
            return false; // Queue full
        }
        self.arr[self.rear] = Some(val); // place value at rear
        self.rear = (self.rear + 1) % self.arr.len(); // move rear forward circularly
        self.size += 1; // increase size
        true
    }

    fn dequeue(&mut self) -> Option<i32> {
        if self.size == 0 {
            return None; // Queue empty
        }
        let val = self.arr[self.front].take(); // take value at front
        self.front = (self.front + 1) % self.arr.len(); // move front forward circularly
        self.size -= 1; // decrease size
        val
    }

    fn print_queue(&self) {
        let mut i = self.front;
        let mut count = 0;
        while count < self.size {
            if let Some(v) = self.arr[i] {
                print!("{} -> ", v);
            }
            i = (i + 1) % self.arr.len();
            count += 1;
        }
        println!("null");
    }
}

fn main() {
    let mut q = Queue::new();
    q.enqueue(10);
    q.enqueue(20);
    q.dequeue();
    q.enqueue(30);
    q.print_queue();
}

if self.size == self.arr.len() { return false; }

check if queue is full before enqueue

self.arr[self.rear] = Some(val);

insert value at rear index

self.rear = (self.rear + 1) % self.arr.len();

move rear pointer forward circularly

self.size += 1;

increase queue size after enqueue

if self.size == 0 { return None; }

check if queue is empty before dequeue

let val = self.arr[self.front].take();

remove value at front index

self.front = (self.front + 1) % self.arr.len();

move front pointer forward circularly

self.size -= 1;

decrease queue size after dequeue

while count < self.size { ... }

iterate from front to rear to print queue elements

Output

20 -> 30 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we use pointers to add or remove elements without shifting.

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

vs Alternative: Compared to a linked list queue, array queue uses fixed space but faster indexing; linked list uses dynamic space but more memory per element.

Edge Cases

enqueue when queue is full

enqueue returns false and does not add element

DSA Rust

if self.size == self.arr.len() { return false; }

dequeue when queue is empty

dequeue returns None and does nothing

DSA Rust

if self.size == 0 { return None; }

wrap around when rear or front reaches end of array

rear and front pointers wrap to start using modulo

DSA Rust

self.rear = (self.rear + 1) % self.arr.len(); and self.front = (self.front + 1) % self.arr.len();

When to Use This Pattern

When you see a problem needing first-in-first-out order with fixed size, reach for array-based queue because it offers fast O(1) enqueue and dequeue using circular indexing.

Common Mistakes

Mistake: Not using modulo to wrap rear and front pointers causing index out of bounds.
Fix: Use modulo operation to wrap pointers circularly within array size.

Mistake: Shifting array elements on dequeue causing O(n) time.
Fix: Use front pointer to track start instead of shifting elements.

Summary

Implements a queue using a fixed-size array with front and rear pointers.

Use when you need a simple, fast queue with known maximum size.

The key is to move front and rear pointers circularly to avoid shifting.

Practice

1. What is the main characteristic of a queue implemented using an array?

easy

A. It follows Last-In-First-Out (LIFO) order

B. It follows First-In-First-Out (FIFO) order

C. It allows random access to elements

D. It stores elements in sorted order

Solution

1. Step 1: Understand queue behavior

   A queue adds elements at the rear and removes from the front, so the first element added is the first removed.

2. Step 2: Compare with options

   This behavior matches FIFO, not LIFO or random access or sorting.

3. Final Answer:

   It follows First-In-First-Out (FIFO) order -> Option B

4. Quick Check:

   Queue = FIFO [OK]

Hint: Remember queue = first in, first out [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking queue allows random access
• Assuming queue sorts elements

2. Which of the following is the correct Rust syntax to declare a fixed-size array of 5 integers for queue storage?

easy

A. let queue: [i32; 5] = [0; 5];

B. let queue = Vec<i32>::new(5);

C. let queue: [i32] = [0, 0, 0, 0, 0];

D. let queue = [5]int{0};

Solution

1. Step 1: Identify Rust array syntax

   In Rust, fixed-size arrays are declared as [type; size], and can be initialized with a repeated value like [0; 5].

2. Step 2: Check options

   let queue: [i32; 5] = [0; 5]; matches this syntax. let queue = Vec<i32>::new(5); uses Vec but with wrong new() usage. let queue: [i32] = [0, 0, 0, 0, 0]; misses size in type. let queue = [5]int{0}; is invalid Rust syntax.

3. Final Answer:

   let queue: [i32; 5] = [0; 5]; -> Option A

4. Quick Check:

   Rust array syntax = [type; size] [OK]

Hint: Rust arrays use [type; size] syntax [OK]

Common Mistakes:

• Using Vec::new with size argument
• Missing size in array type
• Using non-Rust syntax like option D

3. Consider this Rust code snippet for a queue using an array:

let mut queue = [0; 3];
let mut front = 0;
let mut rear = 0;

// Enqueue 10
queue[rear] = 10;
rear += 1;

// Enqueue 20
queue[rear] = 20;
rear += 1;

// Dequeue
front += 1;

// Enqueue 30
queue[rear] = 30;
rear += 1;

println!("{:?}", &queue);

What is the printed output?

medium

A. [10, 0, 30]

B. [0, 20, 30]

C. [20, 30, 0]

D. [10, 20, 30]

Solution

1. Step 1: Trace enqueue and dequeue operations

   Initially queue = [0,0,0], front=0, rear=0. Enqueue 10: queue[0]=10, rear=1 Enqueue 20: queue[1]=20, rear=2 Dequeue: front=1 (10 is logically removed but still in array) Enqueue 30: queue[2]=30, rear=3

2. Step 2: Check final queue array

   Array is [10, 20, 30]. Dequeue only moves front pointer, does not clear value.

3. Final Answer:

   [10, 20, 30] -> Option D

4. Quick Check:

   Array stores all enqueued values [OK]

Hint: Dequeue moves front pointer, array values stay [OK]

Common Mistakes:

• Assuming dequeue clears array slot
• Mixing front and rear indexes
• Confusing array content with logical queue content

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

let mut queue = [0; 3];
let mut front = 0;
let mut rear = 0;

// Enqueue 10
queue[rear] = 10;
rear += 1;

// Enqueue 20
queue[rear] = 20;
rear += 1;

// Enqueue 30
queue[rear] = 30;
rear += 1;

// Enqueue 40
queue[rear] = 40;
rear += 1;

medium

A. Queue does not allow duplicate values

B. front pointer not updated after enqueue

C. Index out of bounds error when enqueueing 40

D. rear pointer should decrement after enqueue

Solution

1. Step 1: Check array size and rear increments

   Array size is 3, rear starts at 0 and increments after each enqueue. After enqueue 30, rear=3.

2. Step 2: Enqueue 40 tries to access queue[3]

   Index 3 is out of bounds for array of size 3, causing runtime error.

3. Final Answer:

   Index out of bounds error when enqueueing 40 -> Option C

4. Quick Check:

   Array size limit exceeded = error [OK]

Hint: Check array size before enqueue to avoid overflow [OK]

Common Mistakes:

• Ignoring array size limit
• Not checking rear before enqueue
• Misunderstanding pointer roles

5. You want to implement a circular queue using an array of size 4 in Rust. Initially, front = 0 and rear = 0. After these operations:

enqueue(5)
enqueue(10)
enqueue(15)
dequeue()
enqueue(20)
dequeue()

What are the values of front and rear pointers, and the queue array content?

hard

A. front = 2, rear = 0, queue = [5, 10, 15, 20]

B. front = 2, rear = 1, queue = [20, 10, 15, 0]

C. front = 1, rear = 3, queue = [5, 10, 15, 20]

D. front = 2, rear = 3, queue = [5, 10, 15, 20]

Solution

1. Step 1: Trace each operation with circular logic

   Array size = 4, front=0, rear=0 initially. - enqueue(5): queue[0]=5, rear=(0+1)%4=1 - enqueue(10): queue[1]=10, rear=2 - enqueue(15): queue[2]=15, rear=3 - dequeue(): front=(0+1)%4=1 - enqueue(20): queue[3]=20, rear=(3+1)%4=0 - dequeue(): front=(1+1)%4=2

2. Step 2: Final pointers and array

   front=2, rear=0, queue = [5, 10, 15, 20]. Dequeue only moves front pointer, does not clear array values.

3. Final Answer:

   front = 2, rear = 0, queue = [5, 10, 15, 20] -> Option A

4. Quick Check:

   Circular queue pointers wrap with modulo [OK]

Hint: Use modulo for circular pointer updates [OK]

Common Mistakes:

• Not using modulo for wrap-around
• Confusing front and rear updates
• Assuming dequeue clears array values