Queue vs Stack When to Use Which in DSA Rust - Visual Comparison

Concept Flow - Queue vs Stack When to Use Which

Start

↓

Need to store items?

↓

Stop

Yes↓

Is order important?

↓

Use Stack (LIFO)

Yes↓

Process items in order received?

↓

Use Queue (FIFO)

No↓

Use other data structure or custom logic

↓

Stop

Decide between stack and queue by checking if order matters and how items should be processed.

Execution Sample

DSA Rust

stack.push(1);
stack.push(2);
stack.pop();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue();

Shows pushing and popping from stack (LIFO) and enqueueing and dequeueing from queue (FIFO).

Execution Table

Step	Operation	Stack State	Queue State	Pointer Changes	Visual State
1	stack.push(1)	1	empty	stack top -> 1	Stack: [1] Queue: []
2	stack.push(2)	1 -> 2	empty	stack top -> 2	Stack: [1 -> 2] Queue: []
3	stack.pop()	1	empty	stack top -> 1	Stack: [1] Queue: []
4	queue.enqueue(1)	1	1	queue front & rear -> 1	Stack: [1] Queue: [1]
5	queue.enqueue(2)	1	1 -> 2	queue rear -> 2	Stack: [1] Queue: [1 -> 2]
6	queue.dequeue()	1	2	queue front -> 2	Stack: [1] Queue: [2]
7	End	1	2	No change	Stack: [1] Queue: [2]

💡 Operations complete; stack and queue states show LIFO and FIFO behavior respectively.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
stack	empty	[1]	[1,2]	[1]	[1]	[1]	[1]	[1]
queue	empty	empty	empty	empty	[1]	[1,2]	[2]	[2]
stack top	null	1	2	1	1	1	1	1
queue front	null	null	null	null	1	1	2	2
queue rear	null	null	null	null	1	2	2	2

Key Moments - 3 Insights

Why does stack.pop() remove the last pushed item, not the first?

Because stack follows Last-In-First-Out (LIFO), so the most recent item pushed (step 2) is removed first (step 3), as shown in execution_table rows 2 and 3.

Why does queue.dequeue() remove the first enqueued item, not the last?

Queue follows First-In-First-Out (FIFO), so the earliest item enqueued (step 4) is removed first (step 6), as shown in execution_table rows 4 and 6.

What happens to pointers when we push or enqueue items?

Stack top pointer moves to the new item on push (steps 1 and 2). Queue front and rear pointers update on enqueue and dequeue to track the first and last items (steps 4, 5, and 6), as detailed in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the stack state after stack.pop()?

A [1 -> 2]

B [1]

C empty

D [2]

💡 Hint

Check the 'Stack State' column at step 3 in execution_table.

At which step does the queue front pointer move from 1 to 2?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at 'Pointer Changes' and 'queue front' in variable_tracker around steps 5 and 6.

If we push another item 3 onto the stack after step 3, what would be the new stack top?

A 3

B 1

C 2

D empty

💡 Hint

Stack top always points to the last pushed item; see variable_tracker for stack top changes.

Concept Snapshot

Stack: Last-In-First-Out (LIFO) structure.
Use when you need to reverse order or track recent items.
Operations: push (add), pop (remove last).
Queue: First-In-First-Out (FIFO) structure.
Use when order of processing matters (like waiting lines).
Operations: enqueue (add), dequeue (remove first).

Full Transcript

This lesson compares stack and queue usage. Stack adds and removes items from the top, so last added is first removed (LIFO). Queue adds items at the rear and removes from the front, so first added is first removed (FIFO). The execution trace shows pushing 1 and 2 to stack, popping removes 2 first. Enqueue 1 and 2 to queue, dequeue removes 1 first. Pointers track top for stack and front/rear for queue. Use stack when order reversal or recent item access is needed. Use queue when processing in order received is important.

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