Standard Collections

VecDeque<T>

VecDeque<T> (std::collections::VecDeque<T>) is a growable double-ended queue implemented as a circular ring buffer on the heap, supporting amortized $O(1)$ insertion and removal at both the front and the back, as well as $O(1)$ indexing.

Ring Buffer Memory Layout

Unlike Vec<T>, whose logical element 0 always sits at physical offset 0 of its heap allocation (making vec.insert(0, x) an $O(n)$ shift), VecDeque<T> tracks a head index and len that wrap around the end of the allocated buffer:

Physical Heap Buffer (capacity = 6, head = 4, len = 4):
+------+------+------+------+------+------+
|  C   |  D   |  --  |  --  |  A   |  B   |
+------+------+------+------+------+------+
  [0]    [1]    [2]    [3]    [4]    [5]
         ▲                    ▲
       tail                 head (logical index 0)

Logical View (q[0]..q[3]): [ A, B, C, D ]

Core Double-Ended Queue Operations

Operation Front (Index 0) Back (Index len - 1) Time Complexity
Insert element q.push_front(x) q.push_back(x) Amortized $O(1)$
Remove element q.pop_front() -> Option<T> q.pop_back() -> Option<T> $O(1)$
Inspect element q.front() -> Option<&T> q.back() -> Option<&T> $O(1)$
Mutate element q.front_mut() -> Option<&mut T> q.back_mut() -> Option<&mut T> $O(1)$
Index by offset q[i] / q.get(i) — $O(1)$ 
use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::from(["middle"]);

    deque.push_front("first");
    deque.push_back("last");

    println!("Queue:      {deque:?}");
    println!("Front:      {:?}, Back: {:?}", deque.front(), deque.back());
    println!("Popped FIFO: {:?}", deque.pop_front());
    println!("Remaining:  {deque:?}");
}

Queue:      ["first", "middle", "last"]
Front:      Some(&"first"), Back: Some(&"last")
Popped FIFO: Some("first")
Remaining:  ["middle", "last"]

Accessing Contiguous Slices (as_slices() and make_contiguous())

Because the ring buffer can wrap around the physical end of its allocation, a VecDeque<T> is not guaranteed to be a single contiguous slice &[T] (and therefore does not implement Deref<Target = [T]>):

  • q.as_slices() -> (&[T], &[T]) returns the two contiguous halves (head_to_end, start_to_tail) in $O(1)$ time without moving any elements.
  • q.make_contiguous() -> &mut [T] rotates the internal buffer in place so all elements sit in one contiguous slice &mut [T] (allowing you to call slice methods like .sort()):
use std::collections::VecDeque;

fn main() {
    let mut q = VecDeque::with_capacity(4);
    q.push_back(30);
    q.push_back(10);
    q.push_front(20); // Wraps around physical buffer

    let (first_half, second_half) = q.as_slices();
    println!("Before make_contiguous: {first_half:?} and {second_half:?}");

    let contiguous: &mut [i32] = q.make_contiguous();
    contiguous.sort();
    println!("Sorted contiguous slice: {contiguous:?}");
}

Before make_contiguous: [20] and [30, 10]
Sorted contiguous slice: [10, 20, 30]