Queue Implementation Using Array in DSA Rust - Execution Trace

Concept Flow - Queue Implementation Using Array

Initialize array with fixed size

↓

Set front = -1, rear = -1

↓

Enqueue operation?

Yes→Check if queue is full

↓

Add element at rear+1

↓

Update rear pointer

↓

If front == -1, set front = 0

↓

Done Enqueue

No↓

Dequeue operation?

Yes→Check if queue is empty

↓

Remove element at front

↓

Update front pointer

↓

If front > rear, reset front and rear to -1

↓

Done Dequeue

No↓

Exit or wait for next operation

This flow shows how a queue uses an array with front and rear pointers to add (enqueue) and remove (dequeue) elements while checking for full or empty conditions.

Execution Sample

DSA Rust

let mut queue = Queue::new(3);
queue.enqueue(10);
queue.enqueue(20);
queue.dequeue();
queue.enqueue(30);
queue.enqueue(40);

This code creates a queue of size 3, adds two elements, removes one, then adds two more, showing how the queue updates.

Execution Table

Step	Operation	Nodes in Queue	Front Pointer	Rear Pointer	Visual State
1	Initialize queue	[]	-1	-1	[]
2	Enqueue 10	[10]	0	0	[10, _, _]
3	Enqueue 20	[10, 20]	0	1	[10, 20, _]
4	Dequeue	[20]	1	1	[_, 20, _]
5	Enqueue 30	[20, 30]	1	2	[_, 20, 30]
6	Enqueue 40 (Fail - Full)	[20, 30]	1	2	[_, 20, 30]

💡 Step 6 enqueue fails because queue is full (rear at last index and front not advanced enough).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
front	-1	0	0	1	1	1
rear	-1	0	1	1	2	2
queue array	[]	[10, _, _]	[10, 20, _]	[_, 20, _]	[_, 20, 30]	[_, 20, 30]

Key Moments - 3 Insights

Why does front start at -1 and change to 0 after first enqueue?

Initially, front is -1 to indicate the queue is empty. After the first enqueue (Step 2), front is set to 0 to point to the first element, as shown in execution_table row 2.

Why does dequeue not remove the element physically from the array?

Dequeue moves the front pointer forward (Step 4), marking the element as removed logically. The array slot remains but is ignored, as seen in the visual state '[_, 20, _]'.

Why does enqueue fail at Step 6 even though there is an empty slot at index 0?

Because this simple queue implementation does not wrap around (no circular queue), rear is at the last index and front is not at 0, so the queue is considered full, as explained in exit_note.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'front' after Step 4?

A 0

B 1

C -1

D 2

💡 Hint

Check the 'Front Pointer' column in execution_table row for Step 4.

At which step does the queue become full?

A Step 3

B Step 5

C Step 6

D Step 2

💡 Hint

Look at the 'Operation' and 'Visual State' columns in execution_table for Step 6.

If we reset front and rear to -1 after dequeue empties the queue, what would happen if we dequeue again?

A Queue underflow error

B Queue remains empty with front and rear at -1

C Queue adds a new element automatically

D Rear pointer moves forward

💡 Hint

Consider what happens when dequeue is called on an empty queue as per the concept_flow.

Concept Snapshot

Queue using array:
- Use fixed-size array with front and rear pointers
- front = -1 and rear = -1 means empty
- Enqueue: add at rear+1, update rear, set front=0 if empty
- Dequeue: remove at front, update front
- If front > rear after dequeue, reset both to -1
- Simple queue is not circular; full when rear at end

Full Transcript

This visual trace shows how a queue is implemented using an array with front and rear pointers. Initially, both pointers are -1 indicating the queue is empty. When we enqueue, we add elements at rear+1 and update rear. If the queue was empty, front is set to 0. When we dequeue, we remove the element at front by moving front forward. If front passes rear, the queue resets to empty. The example shows enqueueing 10 and 20, dequeuing one element, then enqueueing 30. Trying to enqueue 40 fails because the queue is full. The queue does not wrap around, so empty slots at the start are not reused. This simple model helps understand queue operations step-by-step.

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