Queue vs Stack When to Use Which in DSA Rust - Build Both Approaches

Queue vs Stack: When to Use Which

📖 Scenario: Imagine you are managing a line of customers waiting for service and a stack of plates in a kitchen. You want to understand how to organize and process these items using two common data structures: a queue and a stack.

🎯 Goal: You will create a queue and a stack in Rust, add items to each, then remove items to see how their order differs. This will help you understand when to use a queue or a stack in real life.

📋 What You'll Learn

Create a queue using a VecDeque with exact customer names

Create a stack using a Vec with exact plate labels

Add a helper variable to track the number of customers

Use the correct methods to remove items from the queue and stack

Print the final state of the queue and stack after removals

💡 Why This Matters

🌍 Real World

Queues are used in real life to manage lines, like customers waiting for service. Stacks are used in situations like undo actions or managing plates where the last item added is the first to be used.

💼 Career

Understanding queues and stacks is important for software developers to manage data flow, process tasks in order, and solve problems efficiently.

1

Create a queue of customers

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

DSA Rust

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

Hint

Use VecDeque::from to create the queue with the exact names inside square brackets.

2

Create a stack of plates and count customers

Create a Vec called plates with these exact labels in order: "Plate1", "Plate2", "Plate3". Then create a variable called customer_count and set it to the length of customers.

DSA Rust

use std::collections::VecDeque;

let mut customers: VecDeque = VecDeque::from(["Alice", "Bob", "Charlie", "Diana"]);
// Create a Vec called plates with "Plate1", "Plate2", "Plate3"
// Create a variable customer_count equal to customers.len()
// Your code here

Hint

Use vec![...] to create the stack of plates. Use customers.len() to get the number of customers.

3

Remove one customer from the queue and one plate from the stack

Remove one customer from the front of customers using pop_front(). Remove one plate from the top of plates using pop(). Store the removed customer in served_customer and the removed plate in used_plate.

DSA Rust

use std::collections::VecDeque;

let mut customers: VecDeque = VecDeque::from(["Alice", "Bob", "Charlie", "Diana"]);

let mut plates: Vec = vec!["Plate1", "Plate2", "Plate3"];

let customer_count = customers.len();
// Remove one customer from customers using pop_front() and store in served_customer
// Remove one plate from plates using pop() and store in used_plate
// Your code here

Hint

Use pop_front() to remove from the queue front and pop() to remove from the stack top.

4

Print the final state of the queue and stack

Print the customers queue and the plates stack to show their current order after removals.

DSA Rust

use std::collections::VecDeque;

let mut customers: VecDeque = VecDeque::from(["Alice", "Bob", "Charlie", "Diana"]);

let mut plates: Vec = vec!["Plate1", "Plate2", "Plate3"];

let customer_count = customers.len();

let served_customer = customers.pop_front();
let used_plate = plates.pop();
// Print customers
// Print plates
// Your code here

Hint

Use println!("Customers in queue: {:?}", customers); and similarly for plates.

Practice

1. Which data structure should you use when you want to process items in the exact order they arrive, like a line at a ticket counter?

easy

A. Queue

B. Stack

C. HashMap

D. Tree

Solution

1. Step 1: Understand the order requirement

   Processing items in the exact order they arrive means first-in, first-out (FIFO).

2. Step 2: Match order to data structure

   Queue follows FIFO, so it fits the requirement perfectly.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   FIFO = Queue [OK]

Hint: Use queue for first-in, first-out order [OK]

Common Mistakes:

• Choosing stack which is last-in, first-out
• Confusing queue with other data structures
• Ignoring the order requirement

2. Which Rust syntax correctly creates an empty stack using a vector?

easy

A. let mut stack: Vec<i32> = Vec::new();

B. let stack = Vec::empty();

C. let stack = new Vec<i32>();

D. let mut stack = Vec<i32>::init();

Solution

1. Step 1: Recall Rust vector creation syntax

   In Rust, Vec::new() creates an empty vector.

2. Step 2: Check mutability and type annotation

   Stack needs to be mutable to push/pop, and type must be specified or inferred.

3. Final Answer:

   let mut stack: Vec<i32> = Vec::new(); -> Option A

4. Quick Check:

   Vec::new() creates empty vector [OK]

Hint: Use Vec::new() with mut for stack in Rust [OK]

Common Mistakes:

• Using Vec::empty() which does not exist
• Using new keyword like other languages
• Missing mut keyword for modification

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

let mut stack = Vec::new();
stack.push(10);
stack.push(20);
stack.push(30);
while let Some(top) = stack.pop() {
    print!("{} ", top);
}

medium

A. 10 20 30

B. Compilation error

C. 30 20 10

D. 20 30 10

Solution

1. Step 1: Understand stack push order

   Items pushed: 10, then 20, then 30. Stack top is 30.

2. Step 2: Pop items prints in last-in, first-out order

   Pop removes 30 first, then 20, then 10, printing "30 20 10 ".

3. Final Answer:

   30 20 10 -> Option C

4. Quick Check:

   LIFO order = 30 20 10 [OK]

Hint: Stack pops in reverse order of pushes [OK]

Common Mistakes:

• Assuming FIFO order for stack
• Confusing push and pop order
• Expecting compilation error

4. The following Rust code tries to implement a queue using a vector. What is the main problem?

let mut queue = Vec::new();
queue.push(1);
queue.push(2);
queue.remove(0);
queue.remove(0);
println!("{:?}", queue);

medium

A. remove(0) causes a compilation error

B. Using remove(0) is inefficient for large queues

C. push() does not add elements to the vector

D. queue is immutable

Solution

1. Step 1: Understand vector remove(0) behavior

   remove(0) deletes first element but shifts all others left, costly for large vectors.

2. Step 2: Identify inefficiency in queue implementation

   Repeated remove(0) causes O(n) shifts, making it inefficient for queues.

3. Final Answer:

   Using remove(0) is inefficient for large queues -> Option B

4. Quick Check:

   remove(0) shifts elements = inefficient [OK]

Hint: remove(0) shifts all elements, slow for queues [OK]

Common Mistakes:

• Thinking remove(0) causes error
• Assuming push() does not add elements
• Ignoring performance impact

5. You need to design a system that processes tasks in the order they arrive but sometimes needs to undo the last task quickly. Which data structure combination is best in Rust?

hard

A. Use only a stack for both processing and undo

B. Use a HashMap to store tasks and undo

C. Use only a queue for both processing and undo

D. Use a queue for tasks and a stack for undo operations

Solution

1. Step 1: Understand processing order requirement

   Tasks must be processed in arrival order, so a queue (FIFO) is needed.

2. Step 2: Understand undo requirement

   Undo last task quickly means last-in, first-out order, so a stack fits undo.

3. Step 3: Combine data structures

   Use queue for normal processing and stack to track tasks for undo.

4. Final Answer:

   Use a queue for tasks and a stack for undo operations -> Option D

5. Quick Check:

   Queue for order + Stack for undo = Use a queue for tasks and a stack for undo operations [OK]

Hint: Queue for order, stack for undo actions [OK]

Common Mistakes:

• Using only stack loses arrival order
• Using only queue cannot undo last task easily
• Choosing HashMap which doesn't preserve order