Module 4Stack, Queue & DequeLesson 16 of 2320 min

Queue with VecDeque

push_back + pop_front; BFS-ready queue.

Why not Vec for queue?

remove(0) is O(n). VecDeque gives O(1) at both ends.

rust

use std::collections::VecDeque;

fn main() {
    let mut q = VecDeque::new();
    q.push_back(1);
    q.push_back(2);
    let x = q.pop_front(); // Some(1)
    println!("dequeued={x:?} rest={q:?}");
}

Output

dequeued=Some(1) rest=[2]

BFS skeleton

rust

while let Some(node) = q.pop_front() {
    for nxt in neighbors(node) {
        if seen.insert(nxt) { q.push_back(nxt); }
    }
}

Queue only API discipline

Interview: enqueue back, dequeue front — do not use random indexing unless deque problem.

Challenge

Simulate BFS distance on a line graph 0..n-1 with edges i->i+1, start 0.

Tips

VecDeque for O(1) front
pop_front enqueue pattern
pair with HashSet visited

Try it live

Queue with VecDequeRust 2021

Loading editor…

Output

Press Run to compile and execute.