Enqueue Operation in DSA Rust - Execution Trace

Concept Flow - Enqueue Operation

Create new node with value

↓

Is queue empty?

Yes→Set head and tail to new node

| No↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

This flow shows how a new element is added to the end of a queue: create node, check if empty, link at tail, update tail pointer.

Execution Sample

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct Queue {
    head: Option<Box<Node>>,
    tail: *mut Node,
}

impl Queue {
    fn enqueue(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, next: None });
        let raw_node: *mut _ = &mut *new_node;

        if self.head.is_none() {
            self.head = Some(new_node);
            self.tail = raw_node;
        } else {
            unsafe {
                (*self.tail).next = Some(new_node);
            }
            self.tail = raw_node;
        }
    }
}

This code adds a new value to the end of a queue implemented as a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	None	None	null
2	Check if queue is empty	None	None	null
3	Queue empty: set head and tail to new node	10	head -> 10, tail -> 10	10 -> null
4	Create new node with value 20	10	None	10 -> null
5	Check if queue is empty	10	None	10 -> null
6	Queue not empty: set tail.next to new node	10 -> 20	tail.next -> 20	10 -> 20 -> null
7	Update tail to new node	10 -> 20	tail -> 20	10 -> 20 -> null
8	Create new node with value 30	10 -> 20	None	10 -> 20 -> null
9	Check if queue is empty	10 -> 20	None	10 -> 20 -> null
10	Queue not empty: set tail.next to new node	10 -> 20 -> 30	tail.next -> 30	10 -> 20 -> 30 -> null
11	Update tail to new node	10 -> 20 -> 30	tail -> 30	10 -> 20 -> 30 -> null
12	End of enqueue operations	10 -> 20 -> 30	tail -> 30	10 -> 20 -> 30 -> null

💡 All values enqueued; tail points to last node; list correctly linked.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
head	null	Node(10)	Node(10)	Node(10)	Node(10)
tail	null	Node(10)	Node(20)	Node(30)	Node(30)
list size	0	1	2	3	3

Key Moments - 3 Insights

Why do we set both head and tail when the queue is empty?

When the queue is empty (see step 2 and 3), there is no node. The new node becomes both the first (head) and last (tail) element. This ensures the queue is correctly initialized.

Why do we update tail.next before moving tail?

At step 6, tail.next is set to the new node to link it at the end. Then at step 7, tail moves to this new node. This order keeps the list connected without losing the tail reference.

What happens if we forget to update tail after enqueue?

If tail is not updated (missing step 7 or 11), the tail pointer will not point to the last node. Future enqueues will link incorrectly, breaking the queue structure.

Visual Quiz - 3 Questions

Look at the execution table, what is the tail pointer after step 7?

A Node with value 10

B Node with value 20

C Node with value 30

D null

💡 Hint

Check the 'Pointer Changes' column at step 7 in the execution_table.

At which step does the queue first have more than one node?

A Step 3

B Step 5

C Step 6

D Step 10

💡 Hint

Look at the 'Nodes in List' column to see when it changes from one to two nodes.

If the queue was never empty, which steps would be skipped?

A Steps 2 and 3

B Steps 4 and 5

C Steps 6 and 7

D Steps 1 and 2

💡 Hint

Step 3 sets head and tail only if queue is empty (step 2).

Concept Snapshot

Enqueue Operation in Queue:
- Create new node with value
- If queue empty: head and tail point to new node
- Else: tail.next points to new node
- Update tail to new node
- Result: FIFO order maintained

Full Transcript

The enqueue operation adds a new element to the end of a queue. First, a new node is created with the given value. If the queue is empty, both head and tail pointers are set to this new node. Otherwise, the current tail's next pointer is linked to the new node, and then the tail pointer is updated to the new node. This maintains the order of elements in the queue. The execution table shows step-by-step how nodes are added and pointers updated. The variable tracker follows head, tail, and list size changes. Key moments clarify why head and tail are set together when empty, why tail.next is updated before tail, and the importance of updating tail to avoid breaking the queue. The visual quiz tests understanding of pointer positions and step order. This operation ensures the queue grows correctly at the end, preserving FIFO behavior.

Practice

1. What does the enqueue operation do in a queue data structure?

easy

A. Returns the number of elements in the queue

B. Removes an element from the front of the queue

C. Checks if the queue is empty

D. Adds an element to the end of the queue

Solution

1. Step 1: Understand queue behavior

   A queue works like a line where new people join at the end.

2. Step 2: Define enqueue operation

   Enqueue means adding a new element at the back of the queue.

3. Final Answer:

   Adds an element to the end of the queue -> Option D

4. Quick Check:

   Enqueue = Add at end [OK]

Hint: Enqueue always adds at the back of the queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue
• Thinking enqueue removes elements
• Mixing enqueue with checking queue size

2. Which of the following is the correct Rust syntax to enqueue an element 5 into a queue implemented as a VecDeque named queue?

easy

A. queue.push_front(5);

B. queue.enqueue(5);

C. queue.push_back(5);

D. queue.insert(5);

Solution

1. Step 1: Identify VecDeque enqueue method

   In Rust, VecDeque uses push_back to add elements at the end.

2. Step 2: Check options for correct method

   Only queue.push_back(5); correctly adds 5 at the back.

3. Final Answer:

   queue.push_back(5); -> Option C

4. Quick Check:

   VecDeque enqueue = push_back [OK]

Hint: Use push_back to enqueue in VecDeque [OK]

Common Mistakes:

• Using push_front instead of push_back
• Using non-existent enqueue method
• Using insert without index

3. What will be the output of the following Rust code snippet?

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    queue.push_back(10);
    queue.push_back(20);
    queue.push_back(30);
    queue.push_back(40);
    println!("{:?}", queue);
}

medium

A. [10, 20, 30, 40]

B. [40, 30, 20, 10]

C. [10, 20, 30]

D. Compilation error

Solution

1. Step 1: Trace enqueue operations

   Elements 10, 20, 30, 40 are added in order at the back of the queue.

2. Step 2: Understand VecDeque print format

   Printing the queue shows elements in insertion order inside square brackets.

3. Final Answer:

   [10, 20, 30, 40] -> Option A

4. Quick Check:

   Enqueue order preserved in VecDeque [OK]

Hint: VecDeque prints elements in insertion order [OK]

Common Mistakes:

• Assuming push_back adds at front
• Confusing output order
• Expecting compilation error

4. Identify the error in the following Rust code that tries to enqueue an element into a queue:

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    queue.enqueue(15);
    println!("{:?}", queue);
}

medium

A. VecDeque cannot store integers directly

B. VecDeque has no method named 'enqueue'

C. println! macro syntax is incorrect

D. Missing 'mut' keyword for queue variable

Solution

1. Step 1: Check VecDeque methods

   VecDeque does not have an 'enqueue' method; it uses 'push_back' to add elements.

2. Step 2: Verify other code parts

   The queue is mutable and println! syntax is correct; VecDeque supports integers.

3. Final Answer:

   VecDeque has no method named 'enqueue' -> Option B

4. Quick Check:

   Use push_back, not enqueue [OK]

Hint: VecDeque uses push_back, not enqueue [OK]

Common Mistakes:

• Using enqueue method on VecDeque
• Forgetting mut keyword (not error here)
• Misreading println! syntax

5. You want to implement a queue using a Rust Vec where enqueue adds elements at the end and dequeue removes from the front. Which of the following code snippets correctly enqueues the element 7?

hard

A. queue.push(7);

B. queue.insert(0, 7);

C. queue.remove(0); queue.push(7);

D. queue.pop(); queue.push(7);

Solution

1. Step 1: Understand enqueue in Vec-based queue

   Enqueue means adding at the end, so push adds element at the back.

2. Step 2: Analyze options

   queue.push(7); uses push(7) which correctly adds 7 at the end. Others either insert at front or remove elements.

3. Final Answer:

   queue.push(7); -> Option A

4. Quick Check:

   Vec enqueue = push at end [OK]

Hint: Use push to enqueue in Vec-based queue [OK]

Common Mistakes:

• Using insert(0, val) which adds at front
• Removing elements before enqueue
• Using pop which removes last element