std::collections::VecDeque — Rust struct

What `VecDeque` does

A double-ended queue implemented as a growable ring buffer.

As a struct, VecDeque bundles related fields into a single named record with a known layout. Each field has a fixed type and offset, so the size of an instance is the sum of its field sizes plus alignment padding. Construction follows ordinary Rust ownership rules: each owned field must itself be constructed or moved before the struct is well-formed, and the compiler will refuse to leave any field uninitialised. The full canonical path is std::collections::VecDeque; bring it into scope with use std::collections::VecDeque; or refer to it by its full path.

When to use it

Use VecDeque when you push or pop from both ends of a sequence: BFS queues, sliding-window buffers, ring buffers. For pure stack-style usage, plain Vec is faster and simpler.

Annotated examples

Sliding window maximum with VecDeque

use std::collections::VecDeque;

fn max_sliding(nums: &[i32], k: usize) -> Vec<i32> {
    let mut out = Vec::new();
    let mut dq: VecDeque<usize> = VecDeque::new();
    for (i, &n) in nums.iter().enumerate() {
        while dq.front().map_or(false, |&j| j + k <= i) { dq.pop_front(); }
        while dq.back().map_or(false, |&j| nums[j] < n) { dq.pop_back(); }
        dq.push_back(i);
        if i + 1 >= k { out.push(nums[*dq.front().unwrap()]); }
    }
    out
}

The deque-based sliding-window-maximum trick runs in O(n). VecDeque's O(1) push/pop on both ends is exactly the data structure this algorithm needs.

For deeper background, see the canonical Rust patterns reference for the broader context behind this section.

BFS on a grid using VecDeque as the frontier

use std::collections::VecDeque;

fn bfs(start: (i32, i32), goal: (i32, i32)) -> Option<u32> {
    let mut frontier = VecDeque::from([(start, 0u32)]);
    while let Some(((x, y), d)) = frontier.pop_front() {
        if (x, y) == goal { return Some(d); }
        for (dx, dy) in [(1,0),(-1,0),(0,1),(0,-1)] {
            frontier.push_back(((x + dx, y + dy), d + 1));
        }
    }
    None
}

BFS's FIFO discipline maps perfectly to push_back / pop_front. A Vec used the same way would be O(n) per pop and turn the algorithm quadratic.

Common pitfalls

VecDeque is a ring buffer, so its memory is not contiguous — `as_slice` may return two slices via `as_slices()`. If you need a flat view, call `make_contiguous()` first; it does an in-place rearrange.

For deeper background, see an in-depth Rust idioms cheat sheet for the broader context behind this section.

Performance & threading notes

Stack-allocated by default. Heap allocation only happens if a field is itself heap-allocated (Vec, String, Box). Cloning copies every field; for read access pass by reference. Send / Sync are automatically derived if every field is Send / Sync.

What VecDeque does