Queue Implementation Using Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Enqueue and Dequeue Operations

What is the printed state of the queue after performing these operations in order: enqueue 10, enqueue 20, dequeue, enqueue 30?

DSA Rust

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

struct Queue {
    front: Option<Box<Node>>,
    rear: Option<*mut Node>,
}

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

    fn enqueue(&mut self, val: i32) {
        let mut new_node = Box::new(Node { data: val, next: None });
        let raw_node = &mut *new_node as *mut Node;
        if self.rear.is_none() {
            self.front = Some(new_node);
            self.rear = Some(raw_node);
        } else {
            unsafe {
                (*self.rear.unwrap()).next = Some(new_node);
            }
            self.rear = Some(raw_node);
        }
    }

    fn dequeue(&mut self) -> Option<i32> {
        self.front.take().map(|front_node| {
            self.front = front_node.next;
            if self.front.is_none() {
                self.rear = None;
            }
            front_node.data
        })
    }

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

fn main() {
    let mut q = Queue::new();
    q.enqueue(10);
    q.enqueue(20);
    q.dequeue();
    q.enqueue(30);
    q.print_queue();
}

A 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 30 -> null

D 10 -> 30 -> null

💡 Hint

Remember that dequeue removes the front element from the queue.

After enqueueing 10 and 20, the queue is 10 -> 20 -> null. Dequeue removes 10, so queue becomes 20 -> null. Enqueue 30 adds it to the rear, so queue is 20 -> 30 -> null.

🧠 Conceptual

intermediate

Understanding Queue Rear Pointer

Why does the queue implementation using a linked list keep a rear pointer in addition to the front pointer?

A To keep track of the number of elements in the queue

B To allow O(1) time deletion from the end of the queue

C To allow O(1) time insertion at the end of the queue

D To reverse the queue efficiently

💡 Hint

Think about how adding elements at the end of a linked list works.

The rear pointer allows direct access to the last node, so enqueue operations can add new nodes in constant time without traversing the entire list.

🔧 Debug

advanced

Identify the Error in Dequeue Implementation

What error will occur when running this dequeue method if the queue is empty? fn dequeue(&mut self) -> Option { let front_node = self.front.take().unwrap(); self.front = front_node.next; if self.front.is_none() { self.rear = None; } Some(front_node.data) }

A Panic due to unwrap on None when queue is empty

B Compilation error due to missing return statement

C No error, returns None correctly

D Memory leak due to not freeing nodes

💡 Hint

What happens if unwrap is called on None?

Calling unwrap on None causes a panic at runtime. The dequeue method should handle the empty queue case safely.

❓ Predict Output

advanced

Output After Multiple Enqueue and Dequeue

What is the printed queue after these operations? enqueue 5 enqueue 15 dequeue enqueue 25 dequeue dequeue enqueue 35 print queue

DSA Rust

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

struct Queue {
    front: Option<Box<Node>>,
    rear: Option<*mut Node>,
}

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

    fn enqueue(&mut self, val: i32) {
        let mut new_node = Box::new(Node { data: val, next: None });
        let raw_node = &mut *new_node as *mut Node;
        if self.rear.is_none() {
            self.front = Some(new_node);
            self.rear = Some(raw_node);
        } else {
            unsafe {
                (*self.rear.unwrap()).next = Some(new_node);
            }
            self.rear = Some(raw_node);
        }
    }

    fn dequeue(&mut self) -> Option<i32> {
        self.front.take().map(|front_node| {
            self.front = front_node.next;
            if self.front.is_none() {
                self.rear = None;
            }
            front_node.data
        })
    }

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

fn main() {
    let mut q = Queue::new();
    q.enqueue(5);
    q.enqueue(15);
    q.dequeue();
    q.enqueue(25);
    q.dequeue();
    q.dequeue();
    q.enqueue(35);
    q.print_queue();
}

A 15 -> 25 -> 35 -> null

B 35 -> null

C 25 -> 35 -> null

D null

💡 Hint

Track each enqueue and dequeue carefully to see which elements remain.

After enqueue 5 and 15, queue is 5 -> 15 -> null. Dequeue removes 5, queue is 15 -> null. Enqueue 25, queue is 15 -> 25 -> null. Dequeue removes 15, queue is 25 -> null. Dequeue removes 25, queue is empty. Enqueue 35, queue is 35 -> null.

🧠 Conceptual

expert

Why Use Unsafe Pointer for Rear in Rust Queue?

In the Rust linked list queue implementation, why is the rear pointer stored as Option<*mut Node> (a raw mutable pointer) instead of Option> or Option<&mut Node>?

A Because raw pointers are safer and prevent data races automatically

B Because &mut Node is immutable and cannot be used to modify the queue

C Because Box<Node> cannot be used in structs due to size constraints

D Because Box owns the data and cannot have two owners, and &mut Node cannot live beyond a single function call, so raw pointer allows mutable access without ownership issues

💡 Hint

Think about Rust's ownership and borrowing rules and how they affect linked structures.

Box owns the node, so having two Boxes pointing to the same node would violate ownership rules. &mut references cannot be stored long-term due to borrowing rules. Using a raw pointer allows mutable access to the rear node without ownership conflicts, but requires unsafe code.

Practice

1. What is the main advantage of implementing a Queue using a linked list instead of an array?

easy

A. Simpler to implement than arrays

B. Faster access to elements by index

C. Dynamic size without fixed capacity limit

D. Uses less memory for small queues

Solution

1. Step 1: Understand queue size behavior

   Arrays have fixed size or require resizing, linked lists grow dynamically.

2. Step 2: Compare memory and resizing

   Linked lists allocate nodes as needed, so no fixed capacity limit exists.

3. Final Answer:

   Dynamic size without fixed capacity limit -> Option C

4. Quick Check:

   Linked list queues grow dynamically = D [OK]

Hint: Linked lists grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked lists allow fast random access
• Assuming arrays use less memory always
• Confusing implementation simplicity

2. Which of the following is the correct Rust syntax to define a node struct for a linked list queue?

easy

A. struct Node { data: i32, next: Option }

B. struct Node { data: i32, next: Node }

C. struct Node { data: i32, next: &Node }

D. struct Node { data: i32, next: Box<Node> }

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust requires heap allocation for recursive types using Box and Option for nullable links.

2. Step 2: Analyze options

   struct Node { data: i32, next: Option } uses Option which is correct for nullable next pointer; others cause infinite size or borrowing issues.

3. Final Answer:

   struct Node { data: i32, next: Option } -> Option A

4. Quick Check:

   Use Option for nullable next in Rust [OK]

Hint: Use Option for next pointer in Rust linked list [OK]

Common Mistakes:

• Using direct Node type causes infinite size error
• Using references (&Node) without lifetime causes errors
• Omitting Option for nullable next pointer

3. Given the following Rust code snippet for a queue implemented with a linked list, what will be printed after enqueueing 10, 20 and then dequeueing once?

let mut queue = Queue::new();
queue.enqueue(10);
queue.enqueue(20);
let val = queue.dequeue();
println!("Dequeued: {:?}", val);
queue.print();

medium

A. Dequeued: Some(10)
20 -> null

B. Dequeued: Some(20)
10 -> null

C. Dequeued: None
10 -> 20 -> null

D. Dequeued: Some(10)
10 -> 20 -> null

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10 adds node with 10, then enqueue 20 adds node with 20 at the end.

2. Step 2: Trace dequeue operation

   Dequeue removes front node (10), returns Some(10). Remaining queue has 20 only.

3. Final Answer:

   Dequeued: Some(10) 20 -> null -> Option A

4. Quick Check:

   First in first out, dequeue returns 10, queue left with 20 [OK]

Hint: Dequeue removes front, so first enqueued is first out [OK]

Common Mistakes:

• Assuming dequeue removes last element
• Printing queue before dequeue
• Confusing Some and None return values

4. Identify the bug in this Rust enqueue method for a linked list queue:

fn enqueue(&mut self, data: i32) {
    let new_node = Box::new(Node { data, next: None });
    if self.tail.is_none() {
        self.head = Some(new_node);
    } else {
        self.tail.as_mut().unwrap().next = Some(new_node);
    }
    self.tail = Some(new_node);
}

medium

A. Not updating head when queue is empty

B. Using Box instead of Rc for nodes

C. Missing return statement in enqueue

D. Assigning new_node to tail after moving it causes use-after-move error

Solution

1. Step 1: Analyze ownership of new_node

   new_node is moved into head or tail.next, so cannot be moved again.

2. Step 2: Identify use-after-move error

   Assigning self.tail = Some(new_node) after moving new_node causes compile error.

3. Final Answer:

   Assigning new_node to tail after moving it causes use-after-move error -> Option D

4. Quick Check:

   Moving new_node twice causes error [OK]

Hint: Don't move ownership twice; clone or restructure [OK]

Common Mistakes:

• Ignoring Rust ownership rules
• Not updating tail pointer correctly
• Confusing Box and Rc usage

5. You want to implement a method peek for your linked list queue in Rust that returns the front element without removing it. Which approach is correct?

hard

A. Return Option<i32> by cloning data from head node

B. Return Option<&i32> by borrowing data from head node

C. Return i32 directly, panicking if queue is empty

D. Return Option by moving head node

Solution

1. Step 1: Understand peek method goal

   Peek returns front element without removing it, so no ownership transfer.

2. Step 2: Choose correct return type

   Borrowing data with Option<&i32> avoids cloning or moving, safe and efficient.

3. Final Answer:

   Return Option<&i32> by borrowing data from head node -> Option B

4. Quick Check:

   Peek borrows front data, no ownership change [OK]

Hint: Peek borrows front data, don't move or clone unnecessarily [OK]

Common Mistakes:

• Moving head node causing queue modification
• Returning owned data causing unnecessary clone
• Panicking instead of returning Option