Queues and deques in Rust

Think of the line at the canteen. The person who joined first is served first, and new people join at the back. Nobody is allowed to jump to the front.

That is a queue. It is a collection where new items join at the back and items leave from the front. The item that has waited longest is served first. This rule is called FIFO, short for "first in, first out". It is the mirror image of a stack from lesson 4.

A deque (say "deck", short for double-ended queue) is a queue that lets you add and remove at both ends. It can behave as a queue, as a stack, or as a mix.

Reach for a queue whenever things should be handled in the order they arrived: tasks waiting for a worker, messages waiting to be processed, or print jobs. You will meet it again in breadth-first search, a way of exploring a graph one layer at a time.

A queue needs to work at both ends: add at the back, remove from the front. If you store the items in a plain array and remove from the front, everything behind has to shift one place to fill the gap, which gets slower as the queue grows.

The trick is not to move the items at all. Keep a note of where the front is, called start, and how many items there are, called len. Removing from the front just moves start forward by one. The slot it left behind is free to reuse.

When start or the back reaches the last slot, it wraps round to slot 0, as if the row of slots were bent into a ring. The picture shows this: the queue holds four values, the first two in slots 6 and 7, and the others have wrapped to slots 0 and 1. A structure built this way is called a ring buffer (or circular buffer).

Remember: a ring buffer never moves the items. It moves two numbers, start and len.

The tool that does the wrapping is the remainder operator, %. Slot number 8 doesn't exist in an array of eight, but 8 % 8 is 0, which is the first slot. So the next free slot is always (start + len) % capacity.

This queue sits on an array of exactly eight slots, like the fixed array in lesson 1. It refuses new items when it is full, handing the value back, rather than losing it.

/// A queue that sits on a fixed array of eight slots.
/// `start` is the slot of the oldest value, and `len` is how many are in use.
pub struct RingQueue {
    slots: [i32; 8],
    start: usize,
    len: usize,
}

impl RingQueue {
    pub fn new() -> Self {
        RingQueue {
            slots: [0; 8],
            start: 0,
            len: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Adds to the back. If every slot is taken, the value is handed back.
    pub fn push_back(&mut self, value: i32) -> Result<(), i32> {
        if self.len == self.slots.len() {
            return Err(value);
        }
        // The next free slot is `len` places after `start`, wrapping round.
        let end = (self.start + self.len) % self.slots.len();
        self.slots[end] = value;
        self.len += 1;
        Ok(())
    }

    /// Takes from the front: the value that has waited the longest.
    pub fn pop_front(&mut self) -> Option<i32> {
        if self.len == 0 {
            return None;
        }
        let value = self.slots[self.start];
        self.start = (self.start + 1) % self.slots.len();
        self.len -= 1;
        Some(value)
    }

    /// Looks at the front value without taking it.
    pub fn front(&self) -> Option<i32> {
        if self.len == 0 {
            None
        } else {
            Some(self.slots[self.start])
        }
    }
}

impl Default for RingQueue {
    fn default() -> Self {
        Self::new()
    }
}

Go through it in order.

• slots is the array, start is the slot of the oldest value, and len is how many slots are in use.
• push_back finds the next free slot with (self.start + self.len) % self.slots.len(), writes the value there, and adds one to len. If len already equals the number of slots, it returns Err(value).
• pop_front reads the value at start, moves start forward by one (wrapping with %), and takes one off len. An empty queue gives None.
• front looks at the oldest value without removing it.

Nothing is ever copied from one slot to another, so both adding and removing take one step. That is the whole point of the ring.

VecDeque is the standard library's ring buffer. It grows when it is full, it holds any type, and it works at both ends.

use std::collections::VecDeque;

let mut queue = VecDeque::new();
queue.push_back("first");
queue.push_back("second");
queue.push_back("third");

assert_eq!(queue.front(), Some(&"first"));
assert_eq!(queue.pop_front(), Some("first"));
assert_eq!(queue.len(), 2);
println!("{:?}", queue);

push_back and pop_front are the queue moves. front() is a borrowed look at the oldest item, and it returns an Option<&T>, because the queue might be empty.

Because it is a deque, the other end works too:

use std::collections::VecDeque;

let mut deque = VecDeque::new();
deque.push_back(2);
deque.push_back(3);
deque.push_front(1); // O(1) here; on a Vec this would shift everything
deque.push_front(0);

assert_eq!(deque, [0, 1, 2, 3]);
assert_eq!(deque.pop_back(), Some(3));
assert_eq!(deque.pop_front(), Some(0));
assert_eq!(deque[0], 1); // indexing works, from the front
assert_eq!(deque.iter().sum::<i32>(), 3);

push_front is O(1) on a VecDeque. On a Vec it would be insert(0, x), which shifts everything. You can also read by position with deque[0] and loop over it with iter(), and it is the one to reach for whenever you need fast work at the front.

Here, for contrast, is the slow way that a VecDeque exists to avoid:

let mut v = vec![1, 2, 3, 4];
let front = v.remove(0); // shifts every other item one place left: O(n)

assert_eq!(front, 1);
assert_eq!(v, [2, 3, 4]);

For three items, that is nothing. For a long queue, it adds up. Use VecDeque for queues and deques, and Vec when you only work at the end.

The pattern to remember: a Vec is cheap at the back, and a VecDeque is cheap at both ends. Neither is cheap in the middle.

Each problem uses a VecDeque as the line of things waiting. They get harder in order, and the last one is the deque's best-known trick.

pub fn binary_numbers(n: usize) -> Vec<String> {
    todo!("the first n binary numbers, starting at \"1\"")
}

pub fn binary_numbers(n: usize) -> Vec<String> {
    use std::collections::VecDeque;

    let mut result = Vec::with_capacity(n);
    let mut queue = VecDeque::new();
    queue.push_back(String::from("1"));

    while result.len() < n {
        let Some(current) = queue.pop_front() else {
            break; // cannot happen: every pop adds two more
        };
        // The next two numbers in order are this one followed by 0 and by 1.
        queue.push_back(format!("{current}0"));
        queue.push_back(format!("{current}1"));
        result.push(current);
    }
    result
}

pub struct RecentCounter {
    // add the fields you need
}

impl RecentCounter {
    pub fn new() -> Self {
        todo!()
    }

    /// Records a request at `time` (in milliseconds, never going down) and
    /// returns how many requests happened in the last 3000 ms, including this one.
    pub fn ping(&mut self, time: u32) -> usize {
        todo!()
    }
}

use std::collections::VecDeque;

pub struct RecentCounter {
    times: VecDeque<u32>, // requests that may still be inside the window
}

impl RecentCounter {
    pub fn new() -> Self {
        RecentCounter {
            times: VecDeque::new(),
        }
    }

    pub fn ping(&mut self, time: u32) -> usize {
        self.times.push_back(time);
        // Drop requests older than 3000 ms. They sit at the front.
        // Times never go down, so `time - oldest` cannot underflow.
        while let Some(&oldest) = self.times.front() {
            if time - oldest <= 3000 {
                break;
            }
            self.times.pop_front();
        }
        self.times.len()
    }
}

impl Default for RecentCounter {
    fn default() -> Self {
        Self::new()
    }
}

pub fn window_max(nums: &[i32], k: usize) -> Vec<i32> {
    todo!("the largest value in every window of k neighbours")
}

pub fn window_max(nums: &[i32], k: usize) -> Vec<i32> {
    use std::collections::VecDeque;

    if k == 0 || k > nums.len() {
        return Vec::new();
    }
    let mut result = Vec::with_capacity(nums.len() - k + 1);
    // Indexes of candidates, with values falling from front to back.
    let mut candidates: VecDeque<usize> = VecDeque::new();

    for (i, &value) in nums.iter().enumerate() {
        // A smaller value behind a bigger newcomer can never be the maximum.
        while let Some(&last) = candidates.back() {
            if nums[last] > value {
                break;
            }
            candidates.pop_back();
        }
        candidates.push_back(i);

        // The front candidate may have slid out of the window.
        if candidates[0] + k <= i {
            candidates.pop_front();
        }
        // Once the first window is full, the front is its maximum.
        if i + 1 >= k {
            result.push(nums[candidates[0]]);
        }
    }
    result
}

Queues come up in their own right and as part of bigger ideas. A few habits help.

• Spot the signals. "Process in arrival order", "level by level", and "the last k items" all point to a queue or a deque.
• Know the sliding window pattern. Problem 3 is the classic use of a deque. Seeing that the answer only needs the candidates that might still win turns an O(n times k) idea into O(n).
• Expect the classics. Two common questions are building a queue out of two stacks, and building a fixed-size circular queue, which is the ring buffer from this lesson. Draw the start and len values as you go.
• Ask whether it is bounded. Is there a maximum size? What happens when it is full: refuse, overwrite the oldest, or grow? The answer decides your design.
• Say the cost. "Each item is pushed once and popped once, so O(n) in total" is the sentence for most queue problems.
• In Rust, name VecDeque. Saying you would use a VecDeque and not Vec::remove(0), and why, shows you know both the standard library and the cost of shifting.

Made by VeraStack Labs