Enqueue Operation in DSA Rust

Mental Model

Add a new item to the back of a line so everyone waits their turn in order.

Analogy: Imagine a queue at a ticket counter where new people join only at the end of the line.

front -> 1 -> 2 -> 3 -> null ← rear
↑

Dry Run Walkthrough

Input: queue: 1 -> 2 -> 3 -> null, enqueue value 4

Goal: Add the value 4 to the end of the queue so it becomes 1 -> 2 -> 3 -> 4 -> null

Step 1: Create a new node with value 4 and next pointer null

new_node: 4 -> null

Why: We need a new node to add to the queue

Step 2: Link the current rear node (3) to the new node

1 -> 2 -> 3 -> [rear->4] -> null

Why: The last node must point to the new node to keep the chain

Step 3: Update rear pointer to the new node (4)

front -> 1 -> 2 -> 3 -> [rear->4] -> null

Why: Rear must always point to the last node for future enqueues

Result:

front -> 1 -> 2 -> 3 -> 4 -> null ← rear

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

#[derive(Debug)]
struct Queue {
    front: Option<Rc<RefCell<Node>>>,
    rear: Option<Rc<RefCell<Node>>>,
}

impl Queue {
    fn new() -> Self {
        Queue { front: None, rear: None }
    }

    fn enqueue(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));
        // If queue is empty, front and rear both point to new node
        if self.rear.is_none() {
            self.front = Some(Rc::clone(&new_node));
            self.rear = Some(Rc::clone(&new_node));
            return;
        }
        // Link current rear's next to new node
        if let Some(rear_node) = &self.rear {
            rear_node.borrow_mut().next = Some(Rc::clone(&new_node));
        }
        // Update rear to new node
        self.rear = Some(Rc::clone(&new_node));
    }

    fn print_queue(&self) {
        let mut current = self.front.as_ref().map(Rc::clone);
        while let Some(node) = current {
            print!("{} -> ", node.borrow().value);
            current = node.borrow().next.as_ref().map(Rc::clone);
        }
        println!("null");
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.print_queue();
}

let new_node = Rc::new(RefCell::new(Node { value: val, next: None }));

Create a new node with the given value and no next node

if self.rear.is_none() { self.front = Some(Rc::clone(&new_node)); self.rear = Some(Rc::clone(&new_node)); return; }

If queue is empty, set front and rear to new node and return

if let Some(rear_node) = &self.rear { rear_node.borrow_mut().next = Some(Rc::clone(&new_node)); }

Link the current rear node's next pointer to the new node

self.rear = Some(Rc::clone(&new_node));

Update rear pointer to the new node

Output

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(1) because enqueue adds the new node directly at the rear without traversal

Space: O(1) because only one new node is created per enqueue operation

vs Alternative: Compared to using an array where adding at the end might require resizing or shifting, linked list enqueue is faster and constant time

Edge Cases

Empty queue

Front and rear both point to the new node after enqueue

DSA Rust

if self.rear.is_none() { self.front = Some(Rc::clone(&new_node)); self.rear = Some(Rc::clone(&new_node)); return; }

When to Use This Pattern

When you see a problem asking to add items in order at the end of a line, reach for the enqueue operation because it efficiently adds to the rear of a queue.

Common Mistakes

Mistake: Not updating the rear pointer after adding the new node
Fix: Always update the rear pointer to the new node after linking it

Summary

Adds a new element to the end of the queue.

Use when you want to maintain order and add items at the back efficiently.

The key is to keep track of the rear pointer to add in constant time.

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