Why Queue Implementation Using Array in DSA Rust?

The Big Idea

What if you could manage a long line of people without ever losing track of who's next?

The Scenario

Imagine you are standing in a line at a coffee shop, and you have to remember everyone who came before you manually on a piece of paper.

Every time someone new arrives or someone leaves, you have to rewrite the entire list to keep it correct.

The Problem

Writing down and updating the list manually is slow and confusing.

You might forget someone or mix up the order, causing mistakes and delays.

This makes serving customers inefficient and frustrating.

The Solution

A queue implemented using an array helps manage this line automatically.

It keeps track of who is first and who is last, adding new people at the end and removing from the front smoothly.

This way, the order is always correct, and updates happen quickly without rewriting everything.

Before vs After

✗ Before

let mut line = Vec::new();
// Manually rewrite the entire line every time
line = vec!["Alice", "Bob", "Charlie"];
line.remove(0); // Remove first person
line.push("David"); // Add new person

✓ After

struct Queue {
    data: Vec<String>,
    front: usize,
    rear: usize,
}

impl Queue {
    fn enqueue(&mut self, item: String) {
        self.data.push(item);
        self.rear += 1;
    }

    fn dequeue(&mut self) -> Option<String> {
        if self.front == self.rear {
            None
        } else {
            let item = self.data[self.front].clone();
            self.front += 1;
            Some(item)
        }
    }
}

What It Enables

This lets you handle lines of people or tasks efficiently and correctly, no matter how many come or go.

Real Life Example

Ticket counters use queues to serve customers in the order they arrive, ensuring fairness and smooth service.

Key Takeaways

Manual tracking of order is slow and error-prone.

Queue with array automates adding and removing in order.

It keeps operations fast and the order correct.

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