VecDeque<T>

VecDeque<T> (pronounced "vec-deck") is a double-ended queue built on a growable ring buffer. It lets you push and pop elements from both the front and the back in amortised constant time. If Vec<T> is the Swiss Army knife for single-ended lists, VecDeque<T> is the same but for workloads that need fast insertion and removal at either end.

You reach for VecDeque when you want a queue, a deque, a ring buffer, a sliding window, or any structure where the "ends" matter. It lives in std::collections.

What VecDeque Is and Why It Exists

A plain Vec<T> stores its elements in a single, contiguous chunk of memory. That design makes push at the end fast (amortised O(1)), but inserting at the front is slow: every existing element must shift over, costing O(n).

That is the whole reason VecDeque exists. It sacrifices strict contiguity for speed at both ends. Internally it uses a ring buffer, so pushing or popping at either end moves only a pointer—no shifting of elements. The trade‑off is that indexing still happens in O(1) time, but with a slightly higher constant factor because the deque must compute the ring offset.

In practice, VecDeque is the go‑to collection for:

• FIFO queues (first in, first out)
• Double-ended stacks (undo/redo where you push to one side and pop from the other)
• Ring buffers for real‑time data streams (audio, sensor readings, logs)
• Sliding window algorithms where you only care about recent data
• Breadth‑first search and other graph traversal that processes nodes level by level

The Ring Buffer Under the Hood

Think of a ring buffer as a fixed‑size array that has two markers: head and tail. When you push an element, the tail marker advances and the element is placed there. When you pop from the front, the head advances. If either marker reaches the physical end of the array, it wraps around to the beginning. That’s the “ring” behaviour.

VecDeque extends this idea by making the buffer growable. When the buffer fills up, it allocates a larger block of memory, copies the existing elements (possibly re‑ordering them to sit contiguously), and adjusts the capacity. This reallocation is amortised, just like Vec, so the occasional cost is spread over many operations.

Because the elements are not necessarily contiguous in memory, you cannot get a single slice of the entire deque without calling make_contiguous. Instead, the deque exposes two slices via as_slices.

This diagram shows a conceptual layout when elements have wrapped:

[ _, _, E3, E4, E5, E1, E2, _ ]
       ^head        ^tail

The actual data starts at head and continues to tail, wrapping around. E1 and E2 are logically at the front, even though they sit at higher indices.

Understanding this internal model helps you avoid mistakes: taking a slice of the internal buffer directly is not how you access deque elements. Use indexing, iteration, or as_slices.

Creating a VecDeque

The most direct way to get a VecDeque is VecDeque::new(), but you can also pre‑allocate capacity or initialise from an array.

use std::collections::VecDeque;
// Empty deque with default capacity.
let mut deq: VecDeque<i32> = VecDeque::new();
// Pre-allocate space for at least 10 elements.
let mut deq = VecDeque::with_capacity(10);
// From a fixed array (requires Rust 1.56+).
let deq = VecDeque::from([1, 2, 3]);

Using with_capacity avoids repeated reallocations when you know roughly how many elements you will store. The same pattern you use with Vec applies here: reserve ahead of time if you can estimate the final size.

Adding and Removing Elements

The four foundational methods are push_front, push_back, pop_front, and pop_back. Each operates in amortised O(1) time.

use std::collections::VecDeque;
let mut deq = VecDeque::new();
deq.push_back(10);   // [10]
deq.push_front(5);   // [5, 10]
deq.push_back(15);   // [5, 10, 15]
deq.push_front(0);   // [0, 5, 10, 15]
let front = deq.pop_front(); // Some(0),  deque becomes [5, 10, 15]
let back  = deq.pop_back();  // Some(15), deque becomes [5, 10]
assert_eq!(deq.len(), 2);

Both pop_front and pop_back return Option<T>, returning None when the deque is empty. This avoids panics and encourages you to handle the empty case explicitly.

If you call pop_front repeatedly on a Vec, each call shifts all remaining elements left—an O(n) operation. VecDeque avoids that entirely, making it the correct choice for FIFO workloads of any size.

You can also add a whole iterator of elements with extend:

deq.extend([100, 200, 300]);

extend pushes each item to the back, preserving order.

Accessing Elements by Index

VecDeque provides O(1) random access via get, get_mut, and the index operator []. Index 0 is always the front of the deque, and index len() - 1 is the back.

use std::collections::VecDeque;
let mut deq = VecDeque::from([1, 2, 3]);
let second = deq.get(1);             // Some(&2)
let last   = &deq[deq.len() - 1];    // &3
if let Some(elem) = deq.get_mut(0) {
    *elem = 10;
}
assert_eq!(deq[0], 10);

The index operator deq[i] panics if i is out of bounds, while get returns None. Use get when the index might be invalid—it is the idiomatic, panic‑free approach.

Because the elements are not contiguous in memory, the constant factor for indexing is slightly higher than Vec. In most real‑world code this difference is invisible, but it’s worth remembering if you are writing extremely hot inner loops.

Iterating Over a VecDeque

You can iterate forward or backward, by reference or by value. The deque implements IntoIterator, iter, and iter_mut, and also supports the double‑ended iterator trait, giving you .rev().

use std::collections::VecDeque;
let deq = VecDeque::from([1, 2, 3]);
// Immutable reference iteration (front to back)
for val in deq.iter() {
    println!("{val}");
}
// Mutable reference iteration
let mut deq = deq.clone();
for val in deq.iter_mut() {
    *val *= 2;
}
// deq is now [2, 4, 6]
// Consuming iteration (takes ownership)
for val in deq {
    println!("{val}");
}
// Reverse iteration without allocating
let deq = VecDeque::from([1, 2, 3]);
for val in deq.iter().rev() {
    println!("{val}"); // 3, 2, 1
}

Iterating consumes each element from front to back by default. Reverse iteration is zero‑cost; no allocation or copying occurs because the ring buffer already knows where the back is.

When you need to iterate and possibly mutate the deque, use iter_mut only if you are not changing the deque’s length. Adding or removing elements while iterating requires a different approach—collect the changes and apply them after.

Managing Capacity

Like Vec, VecDeque exposes capacity, reserve, reserve_exact, shrink_to_fit, and the nightly try_* variants.

let mut deq: VecDeque<i32> = VecDeque::with_capacity(5);
deq.push_back(1);
assert!(deq.capacity() >= 5);
// Guarantee we can add 100 more without reallocation.
deq.reserve(100);
assert!(deq.capacity() >= 101);
// Shrink to current len, saving memory when done adding.
deq.shrink_to_fit();

Pre‑allocating with with_capacity or reserve removes the amortised reallocation cost entirely when you know the expected size. This is especially important in performance‑sensitive contexts like game loops, real‑time audio, or high‑throughput network buffers.

Reordering and Slicing

Several operations let you rearrange or extract parts of the deque.

swap

swap(i, j) exchanges the elements at two indices in O(1) time. Both indices must be in bounds, otherwise the call panics.

let mut deq = VecDeque::from([10, 20, 30]);
deq.swap(0, 2);
assert_eq!(deq, [30, 20, 10]);

remove

remove(index) removes and returns the element at index, shifting all elements after it toward the front. Its cost is O(min(i, n‑i)), which is faster than Vec::remove for elements near the front or back.

let mut deq = VecDeque::from([1, 2, 3, 4]);
let mid = deq.remove(2);
assert_eq!(mid, 3);
assert_eq!(deq, [1, 2, 4]);

append and split_off

append(&mut other) moves all elements from other to the end of self, emptying other. split_off(index) splits the deque at index, returning a new VecDeque containing the elements from index onward. Both are O(1) if the second deque is empty, or O(n) for the movement, but they avoid per‑element shifting overhead.

let mut deq1 = VecDeque::from([1, 2]);
let mut deq2 = VecDeque::from([3, 4]);
deq1.append(&mut deq2);
assert_eq!(deq1, [1, 2, 3, 4]);
assert!(deq2.is_empty());
let mut deq = VecDeque::from([1, 2, 3, 4]);
let tail = deq.split_off(2);
assert_eq!(deq, [1, 2]);
assert_eq!(tail, [3, 4]);

make_contiguous and Slicing

Because the ring buffer may be wrapped, you cannot obtain a single slice of all elements directly. make_contiguous rotates the buffer so that all elements sit in one contiguous block, and returns a mutable slice to that block. This is useful for sorting or passing the data to functions that expect a &[T].

let mut deq = VecDeque::from([3, 4, 1, 2]);
// Simulate a wrapped state (implementation detail; for illustration)
// In practice, this happens after many push/pop cycles.
let slice = deq.make_contiguous();
slice.sort();
assert_eq!(deq, [1, 2, 3, 4]);

After make_contiguous, the order of elements remains the same (the logical front is still at index 0). The returned mutable slice borrows the deque mutably, so you cannot call other methods on deq while the slice lives.

If you only need to read the elements as two slices (without altering the deque), use as_slices:

let deq = VecDeque::from([1, 2, 3]);
let (front_slice, back_slice) = deq.as_slices();
// front_slice: &[1, 2, 3], back_slice: &[] (no wrap)

When the deque is wrapped, the first slice contains elements from the head to the physical end of the buffer, and the second contains the wrapped portion from the start of the buffer to the tail. This is rarely needed in application code but is crucial if you are implementing low‑level algorithms or interoperating with C libraries.

Performance Characteristics

Knowing how each operation scales helps you pick the right collection. Here is a focused summary for VecDeque (n = number of elements, i = index):

*append is O(m) for moving m elements, but it avoids per‑element shifting.

Compared to Vec, VecDeque has a small memory overhead for the ring buffer bookkeeping (head/tail pointers and possibly block metadata). The elements themselves are stored inline in the buffer, so per‑element overhead is the same as Vec.

VecDeque is almost always a better queue than Vec because Vec::remove(0) is O(n). It is also generally faster than LinkedList for queues due to far better cache locality, despite LinkedList having theoretically O(1) push/pop at both ends.

Common Use Cases and Examples

The following patterns show VecDeque in action. Each example includes realistic code you can adapt.

FIFO Queue (Job Processing)

A simple job queue where tasks are pushed to the back and processed from the front.

use std::collections::VecDeque;
fn main() {
    let mut queue: VecDeque<String> = VecDeque::new();
    // Enqueue jobs
    for id in 1..=3 {
        queue.push_back(format!("Job-{id}"));
    }
    // Process until empty
    while let Some(job) = queue.pop_front() {
        println!("Processing {job}");
    }
    // Output:
    // Processing Job-1
    // Processing Job-2
    // Processing Job-3
}

There is no index manipulation; the deque handles the order. If you were using a Vec with remove(0), each pop_front equivalent would become O(n), and processing 100,000 jobs would grind to a halt. This example is the textbook reason VecDeque exists.

Fixed-Size Ring Buffer

A rolling buffer that discards the oldest element when a new one arrives, keeping only the last capacity items.

use std::collections::VecDeque;
struct RingBuffer<T> {
    data: VecDeque<T>,
    capacity: usize,
}
impl<T> RingBuffer<T> {
    fn new(capacity: usize) -> Self {
        RingBuffer {
            data: VecDeque::with_capacity(capacity),
            capacity,
        }
    }
    fn push(&mut self, item: T) {
        if self.data.len() == self.capacity {
            self.data.pop_front(); // drop oldest
        }
        self.data.push_back(item);
    }
    fn as_slices(&self) -> (&[T], &[T]) {
        self.data.as_slices()
    }
    fn len(&self) -> usize {
        self.data.len()
    }
}
fn main() {
    let mut buf = RingBuffer::new(3);
    buf.push(1);
    buf.push(2);
    buf.push(3);
    buf.push(4); // 1 is dropped
    assert_eq!(buf.len(), 3);
    // Logical content: [2, 3, 4]
}

This is the foundation of audio sample buffers, sliding‑window statistics, and many real‑time monitoring tools. The buffer never reallocates after initial construction because with_capacity sets aside enough space for the maximum size.

Breadth-First Search (BFS)

Traversing a graph level by level relies on a FIFO queue. Here is a minimal BFS on an adjacency list:

use std::collections::VecDeque;
fn bfs(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut queue = VecDeque::new();
    let mut visited = vec![false; graph.len()];
    let mut order = Vec::new();
    queue.push_back(start);
    visited[start] = true;
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &neighbour in &graph[node] {
            if !visited[neighbour] {
                visited[neighbour] = true;
                queue.push_back(neighbour);
            }
        }
    }
    order
}

The pop_front call is the essential FIFO behaviour: nodes discovered first are explored first. VecDeque gives you exactly that at O(1) per operation, keeping the BFS overall runtime at O(V + E).

Sliding Window Maximum

Given an array and a window size k, find the maximum in each window efficiently. A common O(n) solution uses a VecDeque that stores indices, maintaining the deque such that its front is always the maximum of the current window.

use std::collections::VecDeque;
fn sliding_window_max(nums: &[i32], k: usize) -> Vec<i32> {
    let mut deq: VecDeque<usize> = VecDeque::new();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        // Remove indices that are out of this window
        while deq.front().map_or(false, |&front| front + k <= i) {
            deq.pop_front();
        }
        // Remove indices whose corresponding values are <= current value
        while deq.back().map_or(false, |&back| nums[back] <= nums[i]) {
            deq.pop_back();
        }
        deq.push_back(i);
        // The front is the max for the window ending at i
        if i >= k - 1 {
            result.push(nums[*deq.front().unwrap()]);
        }
    }
    result
}

This example uses pop_front, pop_back, and push_back on the deque, each O(1). A Vec would make removing from the front O(n), rendering the algorithm far slower. The pattern appears in many competitive programming problems and time‑series analysis tools.

Pitfalls and Misconceptions

Assuming elements are contiguous.
You cannot pass a &VecDeque<T> directly to a function expecting a &[T]. Use deq.make_contiguous() if you must have a single slice, or redesign your interface to accept an iterator.

Holding references across mutations.
Borrowing rules prevent you from calling push or pop while a reference obtained via get or iter is alive. This is the same as with Vec. However, the make_contiguous slice imposes an especially strict mutable borrow—no method calls on the deque at all while the slice exists.

Comparing performance by only looking at big‑O.
The constants matter. VecDeque indexing is slightly slower than Vec indexing because of the ring offset calculation. In most programs you will never notice, but if you are doing millions of random accesses per second and only ever push/pop at the back, Vec may be a better choice.

Expecting pop_front to free capacity.
Collections in Rust’s standard library do not automatically shrink. Even after many pops, the allocated capacity remains. Call shrink_to_fit if you need to release memory.

Using VecDeque as an array replacement without reason.
If all your insertions and removals happen at the back, Vec is simpler, has lower overhead, and gives you direct slice access. VecDeque introduces ring‑buffer complexity you don’t need.

When to Use VecDeque (and When Not)

Choose VecDeque when:

• You need a FIFO queue with frequent push/pop at opposite ends.
• You need a double‑ended stack where both ends see activity.
• You implement a ring buffer or sliding window that requires removal from the front.
• You want to avoid the O(n) shift cost of Vec::remove(0).

Stick with Vec when:

• You only push and pop at the back.
• You require a contiguous slice of all elements frequently.
• You are primarily doing indexed random access and the code is performance‑critical.

Prefer LinkedList almost never—its only real advantage is O(1) insertion/removal at arbitrary positions when holding a cursor to that position, and even then the cache‑unfriendliness often destroys performance.

Summary

VecDeque<T> fills the gap that Vec cannot cover efficiently: fast operations at both ends. Its growable ring buffer gives you amortised O(1) push and pop at front and back, O(1) indexed access, and a rich set of manipulation methods. The trade‑off is that the data is not always contiguous, and indexing has a marginally higher constant cost.

The mental model to keep: it’s a Vec that can grow and shrink at both ends without shifting elements. That’s it. When your code naturally does push_back and pop_front (or the reverse), VecDeque is the right tool.