Queue Implementation Using Array in DSA Rust - Time & Space Complexity

Time Complexity: Queue Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how the time to add or remove items from a queue changes as the queue grows.

How does the queue's size affect the speed of its main operations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

impl Queue {
    fn enqueue(&mut self, val: i32) {
        if self.rear < self.size {
            self.data[self.rear] = val;
            self.rear += 1;
        }
    }

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

This code shows a queue using an array with front and rear pointers to add and remove items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item by moving front or rear index.
• How many times: Each enqueue or dequeue moves pointers once, no loops inside these methods.

How Execution Grows With Input

Each enqueue or dequeue does a fixed number of steps regardless of queue size.

Input Size (n)	Approx. Operations
10	1 operation per enqueue or dequeue
100	1 operation per enqueue or dequeue
1000	1 operation per enqueue or dequeue

Pattern observation: The time to add or remove an item stays the same no matter how big the queue is.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes the same short time no matter how many items are in the queue.

Common Mistake

[X] Wrong: "Enqueue or dequeue takes longer as the queue grows because the array is bigger."

[OK] Correct: The code only moves pointers and accesses one position, so the size does not affect the time.

Interview Connect

Understanding this constant time behavior shows you know how queues work efficiently, a key skill for many coding tasks.

Self-Check

"What if we used a linked list instead of an array? How would the time complexity of enqueue and dequeue change?"

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