Queue Concept and FIFO Principle in DSA Rust - Build from Scratch

Queue Concept and FIFO Principle

📖 Scenario: Imagine a line at a coffee shop where customers wait their turn to order. The first person to get in line is the first person to be served. This is called FIFO - First In, First Out. We will create a queue to simulate this line.

🎯 Goal: Build a simple queue using a Rust VecDeque to add customers to the line and serve them in the order they arrived.

📋 What You'll Learn

Create a queue using VecDeque with initial customers

Add a new customer to the queue

Remove the first customer from the queue following FIFO

Print the queue state after operations

💡 Why This Matters

🌍 Real World

Queues are used in real life to manage lines, like customers waiting, tasks waiting to run, or messages waiting to be processed.

💼 Career

Understanding queues helps in software development for managing tasks, requests, and data streams efficiently.

1

Create the initial queue

Create a VecDeque called queue with these exact customers in order: "Alice", "Bob", "Charlie".

DSA Rust

# Create a VecDeque called queue with "Alice", "Bob", "Charlie"
// Your code here

Hint

Use VecDeque::from with an array of strings to create the queue.

2

Add a new customer to the queue

Add a new customer "Diana" to the end of the queue using the push_back method.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque = VecDeque::from(["Alice", "Bob", "Charlie"]);
    // Add "Diana" to the end of queue
    // Your code here
}

Hint

Use queue.push_back("Diana") to add Diana at the end.

3

Serve the first customer

Remove the first customer from the queue using the pop_front method and store it in a variable called served.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque = VecDeque::from(["Alice", "Bob", "Charlie"]);
    queue.push_back("Diana");
    // Remove the first customer and save to served
    // Your code here
}

Hint

Use let served = queue.pop_front(); to remove the first customer.

4

Print the queue after serving

Print the current state of the queue using println! with the format: "Queue: {:?}".

DSA Rust

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque = VecDeque::from(["Alice", "Bob", "Charlie"]);
    queue.push_back("Diana");
    let served = queue.pop_front();
    // Print the queue
    // Your code here
}

Hint

Use println!("Queue: {:?}", queue); to show the queue.

Practice

1. What does the FIFO principle mean in the context of a queue?

easy

A. First In, Last Out - the first element added is the last removed

B. Last In, Last Out - the last element added is the last removed

C. Last In, First Out - the last element added is the first removed

D. First In, First Out - the first element added is the first removed

Solution

1. Step 1: Understand FIFO principle

   FIFO means the first element added to the queue will be the first one to leave.

2. Step 2: Match FIFO with queue behavior

   Queues follow FIFO, so the first inserted element is removed first.

3. Final Answer:

   First In, First Out - the first element added is the first removed -> Option D

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue = line; first come, first served [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking queue removes last added first
• Mixing stack behavior with queue

2. Which of the following is the correct way to create an empty queue using Rust's standard library?

easy

A. let mut queue = Queue::new();

B. let mut queue = VecDeque::new();

C. let queue = Queue::empty();

D. let queue = Vec::queue();

Solution

1. Step 1: Identify Rust queue type

   Rust's standard library uses VecDeque for queue operations.

2. Step 2: Check correct syntax for empty VecDeque

   VecDeque::new() creates an empty queue correctly.

3. Final Answer:

   let mut queue = VecDeque::new(); -> Option B

4. Quick Check:

   VecDeque::new() creates empty queue [OK]

Hint: Use VecDeque::new() for empty queue in Rust [OK]

Common Mistakes:

• Using non-existent Queue::empty() method
• Confusing Vec with queue type
• Missing mut keyword for mutable queue

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

use std::collections::VecDeque;

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

medium

A. Some(10)
[20, 30]

B. Some(30)
[10, 20]

C. None
[10, 20, 30]

D. Some(20)
[10, 30]

Solution

1. Step 1: Trace queue insertions

   Elements 10, 20, 30 are added to the back in order.

2. Step 2: Pop front element

   pop_front() removes and returns the first element, which is 10.

3. Step 3: Print results

   first prints Some(10), queue now contains [20, 30].

4. Final Answer:

   Some(10) [20, 30] -> Option A

5. Quick Check:

   pop_front() returns first element [OK]

Hint: pop_front() removes first inserted element [OK]

Common Mistakes:

• Thinking pop_front() removes last element
• Confusing push_back with push_front
• Expecting None when queue is not empty

4. Identify the error in the following Rust code that tries to implement a queue using VecDeque:

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    queue.push_front(1);
    queue.push_back(2);
    let first = queue.pop_back();
    println!("{:?}", first);
}

medium

A. Error: push_front() is invalid method for VecDeque

B. No error; code works and prints Some(2)

C. Error: pop_back() should be pop_front() to follow FIFO

D. Error: queue must be immutable for pop_back()

Solution

1. Step 1: Analyze queue operations

   push_front(1) adds 1 at front, push_back(2) adds 2 at back.

2. Step 2: Check pop_back() usage

   pop_back() removes last element (2), but FIFO requires removing first element.

3. Step 3: Correct method for FIFO

   pop_front() should be used to remove the first inserted element.

4. Final Answer:

   Error: pop_back() should be pop_front() to follow FIFO -> Option C

5. Quick Check:

   FIFO needs pop_front(), not pop_back() [OK]

Hint: Use pop_front() to remove first element in queue [OK]

Common Mistakes:

• Using pop_back() instead of pop_front() for FIFO
• Thinking push_front() is invalid
• Forgetting mut keyword for mutable queue

5. You want to simulate a queue in Rust that processes tasks in order. Given this code snippet, what will be the final state of the queue after all operations?

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    queue.push_back("task1");
    queue.push_back("task2");
    queue.push_back("task3");
    queue.pop_front();
    queue.push_back("task4");
    queue.pop_front();
    println!("{:?}", queue);
}

hard

A. ["task3", "task4"]

B. ["task2", "task3", "task4"]

C. ["task1", "task4"]

D. ["task4"]

Solution

1. Step 1: Trace queue after initial pushes

   Queue after pushes: ["task1", "task2", "task3"]

2. Step 2: First pop_front()

   Removes "task1", queue: ["task2", "task3"]

3. Step 3: Push "task4"

   Queue: ["task2", "task3", "task4"]

4. Step 4: Second pop_front()

   Removes "task2", queue: ["task3", "task4"]

5. Final Answer:

   ["task3", "task4"] -> Option A

6. Quick Check:

   FIFO removes oldest tasks first [OK]

Hint: Pop front removes oldest; push back adds newest [OK]

Common Mistakes:

• Removing wrong elements with pop_back()
• Forgetting order of operations
• Assuming pop_front() removes last element