Queue vs Stack When to Use Which in DSA Rust - Trade-offs & Analysis

Mental Model

A stack adds and removes items from the top only, like a stack of plates. A queue adds items at the back and removes from the front, like a line at a store.

Analogy: Imagine a stack as a pile of books where you can only add or take the top book. A queue is like people waiting in line: new people join at the end, and the person at the front leaves first.

Stack (top on right): bottom -> 1 -> 2 -> 3 ↑top
Queue (front on left): ↑front 1 -> 2 -> 3 -> back

Dry Run Walkthrough

Input: Stack: push 1, push 2, pop; Queue: enqueue 1, enqueue 2, dequeue

Goal: Show how stack and queue add and remove elements differently

Step 1: Push 1 onto stack

Stack: 1 ↑top
Queue: empty

Why: Add first item to stack at the top

Step 2: Push 2 onto stack

Stack: 1 -> 2 ↑top
Queue: empty

Why: Add second item on top of first in stack

Step 3: Pop from stack

Stack: 1 ↑top
Queue: empty

Why: Remove top item from stack (last in, first out)

Step 4: Enqueue 1 into queue

Stack: 1 ↑top
Queue: 1 ↑front -> back

Why: Add first item to back of queue

Step 5: Enqueue 2 into queue

Stack: 1 ↑top
Queue: 1 ↑front -> 2 -> back

Why: Add second item to back of queue

Step 6: Dequeue from queue

Stack: 1 ↑top
Queue: 2 ↑front -> back

Why: Remove front item from queue (first in, first out)

Result:

Stack final: 1 ↑top
Queue final: 2 ↑front -> back

Annotated Code

DSA Rust

use std::collections::VecDeque;
use std::vec::Vec;

struct Stack<T> {
    data: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack { data: Vec::new() }
    }

    fn push(&mut self, value: T) {
        self.data.push(value); // add to top
    }

    fn pop(&mut self) -> Option<T> {
        self.data.pop() // remove from top
    }

    fn to_string(&self) -> String where T: std::fmt::Display {
        let mut s = String::new();
        for v in &self.data {
            s.push_str(&format!("{} -> ", v));
        }
        s.push_str("top");
        s
    }
}

struct Queue<T> {
    data: VecDeque<T>,
}

impl<T> Queue<T> {
    fn new() -> Self {
        Queue { data: VecDeque::new() }
    }

    fn enqueue(&mut self, value: T) {
        self.data.push_back(value); // add to back
    }

    fn dequeue(&mut self) -> Option<T> {
        self.data.pop_front() // remove from front
    }

    fn to_string(&self) -> String where T: std::fmt::Display {
        let mut s = String::new();
        for v in &self.data {
            s.push_str(&format!("{} -> ", v));
        }
        s.push_str("back");
        s
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    let popped = stack.pop();

    let mut queue = Queue::new();
    queue.enqueue(1);
    queue.enqueue(2);
    let dequeued = queue.dequeue();

    println!("Stack final: {}", stack.to_string());
    println!("Queue final: {}", queue.to_string());
}

self.data.push(value); // add to top

push adds element on top of stack

self.data.pop() // remove from top

pop removes element from top of stack

self.data.push_back(value); // add to back

enqueue adds element at back of queue

self.data.pop_front() // remove from front

dequeue removes element from front of queue

Output

Stack final: 1 -> top

Queue final: 2 -> back

Complexity Analysis

Time: O(1) for push/pop in stack and enqueue/dequeue in queue because operations happen at one end only

Space: O(n) because both store all elements in memory

vs Alternative: Compared to arrays where removing from front is O(n), queue uses pointers to remove front in O(1), making it efficient for FIFO tasks

Edge Cases

Empty stack pop or queue dequeue

Returns None safely without error

DSA Rust

self.data.pop() // remove from top

Single element stack or queue

Push/enqueue adds element, pop/dequeue removes it leaving empty structure

DSA Rust

self.data.pop_front() // remove from front

When to Use This Pattern

When a problem needs last-in-first-out order, use a stack; when it needs first-in-first-out order, use a queue.

Common Mistakes

Mistake: Using stack pop to remove from front like a queue
Fix: Use queue dequeue which removes from front, not stack pop which removes from top

Mistake: Trying to enqueue at front or pop from back in queue
Fix: Always enqueue at back and dequeue from front in queue

Summary

Stack stores items with last-in-first-out order; queue stores items with first-in-first-out order.

Use stack when you need to reverse order or track recent items; use queue when order of arrival matters.

Remember: stack adds/removes only at top; queue adds at back and removes from front.

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