Collection Adapters and Specialized Types

pop_front() and pop_back()

The .pop_front() and .pop_back() methods (along with .pop_front_if() and .pop_back_if()) remove and return the first or last element of a VecDeque<T> in guaranteed $O(1)$ time, returning None if the deque is empty.

Signatures and Companion Inspection Methods

impl<T> VecDeque<T> {
    pub fn pop_front(&mut self) -> Option<T>;
    pub fn pop_back(&mut self) -> Option<T>;

    pub fn front(&self) -> Option<&T>;
    pub fn front_mut(&mut self) -> Option<&mut T>;
    pub fn back(&self) -> Option<&T>;
    pub fn back_mut(&mut self) -> Option<&mut T>;
}
Operation Front (Index 0) Back (Index len - 1) Ring Buffer Update
Read without removing q.front() q.back() None
Mutate without removing q.front_mut() q.back_mut() None
Remove and return (Option<T>) q.pop_front() q.pop_back() Advances head = (head + 1) % cap (front) or decrements len (back)
Conditional remove q.pop_front_if(pred) q.pop_back_if(pred) Pops only if pred(&mut elem) returns true

Breadth-First Search (BFS) Using push_back() and pop_front()

A classic FIFO queue for Breadth-First Search pushes newly discovered neighbors to the back (push_back) and dequeues the next node to visit from the front (pop_front):

use std::collections::VecDeque;

fn bfs_shortest_levels(adj: &[Vec<usize>], start: usize) -> Vec<Option<u32>> {
    let mut dist = vec![None; adj.len()];
    let mut queue = VecDeque::new();

    dist[start] = Some(0);
    queue.push_back(start);

    while let Some(u) = queue.pop_front() {
        let next_d = dist[u].unwrap() + 1;
        for &v in &adj[u] {
            if dist[v].is_none() {
                dist[v] = Some(next_d);
                queue.push_back(v);
            }
        }
    }
    dist
}

fn main() {
    // 0 -> 1 -> 3, 0 -> 2 -> 3
    let graph = vec![vec![1, 2], vec![3], vec![3], vec![]];
    let distances = bfs_shortest_levels(&graph, 0);
    println!("Shortest hop distances from node 0: {distances:?}");
}

Shortest hop distances from node 0: [Some(0), Some(1), Some(1), Some(2)]

Two-Ended Consumption (Palindrome / Work-Stealing Deque Pattern)

Because both pop_front() and pop_back() are $O(1)$, algorithms can consume elements from both ends toward the middle—such as checking whether a sequence is a palindrome or allowing worker threads to pop local tasks from one end while thieves steal from the other:

use std::collections::VecDeque;

fn is_palindrome<T: Eq>(items: impl IntoIterator<Item = T>) -> bool {
    let mut deque: VecDeque<T> = items.into_iter().collect();

    // When 0 or 1 element remains, `pop_front()` and `pop_back()` stop:
    while deque.len() > 1 {
        if deque.pop_front() != deque.pop_back() {
            return false;
        }
    }
    true
}

fn main() {
    println!("[1, 2, 3, 2, 1]: {}", is_palindrome([1, 2, 3, 2, 1]));
    println!("[1, 2, 3, 4]:    {}", is_palindrome([1, 2, 3, 4]));
}

[1, 2, 3, 2, 1]: true
[1, 2, 3, 4]:    false