Step 2 of 6

Queues with VecDeque

A queue is FIFO: first in, first out, like a line at a ticket counter, jobs waiting for a printer, or messages waiting for a worker. You could build one from a Vec with push at the back and remove(0) at the front, but remove(0) shifts every remaining element one place left. That's O(n) per removal, so serving a queue of n people costs O(n²) in total.

std::collections::VecDeque (say "vec-deck", short for double-ended queue) fixes that. It's a ring buffer: one block of memory like a Vec, but the front can start anywhere and the items wrap around the end of the block. Adding or removing at either end is O(1).

use std::collections::VecDeque;

fn main() {
    let mut jobs: VecDeque<&str> = VecDeque::new();
    jobs.push_back("report.pdf");
    jobs.push_back("photo.png");
    jobs.push_back("invoice.pdf");
    jobs.push_front("URGENT.txt");

    println!("next up: {:?}", jobs.front());
    println!("{} jobs, third is {}", jobs.len(), jobs[2]);
    while let Some(job) = jobs.pop_front() {
        println!("printing {job}");
    }

    let numbers: VecDeque<i32> = (1..=4).collect();
    println!("{numbers:?}");
}

next up: Some("URGENT.txt")
4 jobs, third is photo.png
printing URGENT.txt
printing report.pdf
printing photo.png
printing invoice.pdf
[1, 2, 3, 4]

You can build one with VecDeque::new(), VecDeque::from(vec![...]), VecDeque::from([1, 2, 3]) or .collect(), and {:?} prints it front to back like a Vec.

Common mistakes

• Calling pop(). A VecDeque has two ends, so there's no plain pop; you pick a side:

use std::collections::VecDeque;

fn main() {
    let mut jobs: VecDeque<&str> = VecDeque::from(["a", "b"]);
    println!("{:?}", jobs.pop());
}

error[E0599]: no method named `pop` found for struct `VecDeque<T, A>` in the current scope

• Mixing up the ends. push_back with pop_back is a stack, not a queue. A queue goes in at one end and out at the other.
• Expecting one slice. Because the items can wrap around, a VecDeque isn't always one contiguous slice: &q[..] doesn't work. Use q.iter(), or q.make_contiguous() when you really need a &mut [T].
• Vec::remove(0) in a loop. It works on small inputs and falls over on big ones. If you see it in review, suggest VecDeque.

Your task

Run the food truck line. Read commands from standard input, one per line:

• join NAME: NAME joins the back of the line
• vip NAME: NAME goes straight to the front
• serve: serve the person at the front and print served NAME, or print nobody waiting if the line is empty

After the last command, print still waiting: followed by the names front to back, separated by , , or still waiting: nobody. Use a VecDeque<String>.

Challenge 2

An operating system shares one CPU between tasks with round-robin scheduling: the task at the front of the queue runs for at most quantum time units; if it still needs time, it goes to the back of the queue.

Write fn round_robin(tasks: &[(&str, u32)], quantum: u32) -> Vec<String> that returns the task names in the order they finish. Each task is (name, time needed). quantum is at least 1. A task that needs 0 time finishes on its first turn.

With [("build", 5), ("lint", 2), ("test", 4)] and quantum 2: build runs 2 (3 left, back of the queue), lint runs 2 and finishes, test runs 2 (2 left), build runs 2 (1 left), test finishes, build finishes: ["lint", "test", "build"].

Challenge 3

The monitoring dashboard shows the average response time of the last N requests. Write a small type for it:

struct RecentReadings { /* your fields */ }
impl RecentReadings {
    fn new(capacity: usize) -> Self
    fn push(&mut self, millis: u64)   // drops the oldest reading when there are more than capacity
    fn average(&self) -> Option<f64>  // None when there are no readings yet
}

The dashboard calls average() after every reading, and the tests push 300,000 readings with a capacity of 100,000. Adding up the whole window on every call would be O(capacity) per call: far too slow. Keep a running sum: add the new reading, subtract the one you drop. Then average is O(1).

Previous: Stacks with Vec Next: Priority queues with BinaryHeap