Deques

A double-ended queue (deque), implemented in the standard library as std::collections::VecDeque<T>, is a growable ring buffer (circular buffer) that supports $O(1)$ insertion and removal at both the front and the back while still providing $O(1)$ indexed random access (deque[i]).

`VecDeque<T>` Circular Ring Buffer Layout in Heap Memory:

  Logical Order:   [ A, B, C, D, E ] (len = 5, cap = 8)

  Physical Buffer when wrapped around end of allocation (`head = 6`):
  Index:   0     1     2     3     4     5     6     7
         +-----+-----+-----+-----+-----+-----+-----+-----+
         |  C  |  D  |  E  |  .  |  .  |  .  |  A  |  B  |
         +-----+-----+-----+-----+-----+-----+-----+-----+
         |<-- 2nd Slice -->|                 |<-1st Slice|
                                               ^
                                             `head`

Key Operations on VecDeque<T>

Why VecDeque Does Not Deref to &[T] (and How as_slices / make_contiguous Work)

Because a ring buffer can wrap around the end of its underlying heap allocation (as shown in the diagram above), its elements may occupy two disjoint contiguous slices rather than one single slice. Therefore, VecDeque<T> cannot implement Deref<Target = [T]>:

• When you want to inspect the underlying slices without moving elements, call deque.as_slices(), which returns (&[T], &[T]) (where the second slice is empty &[] whenever the buffer has not wrapped).
• When you need a single contiguous &mut [T] slice (for example, to pass into a C FFI function or sort with .sort_unstable()), call deque.make_contiguous().

Practical Example: Sliding Window Maximum ($O(n)$ Monotonic Deque)

A classic algorithm enabled by a double-ended queue is computing the maximum of every sliding window of size $k$ across an array of length $n$ in $O(n)$ total time (only 2 operations per element!) by maintaining candidate indices in decreasing order of their values:

use std::collections::VecDeque;

/// Computes the maximum value in every sliding window of width `k` in O(n) time
/// using a monotonic decreasing `VecDeque` of indices.
pub fn sliding_window_max(nums: &[i32], k: usize) -> Vec<i32> {
    if nums.is_empty() || k == 0 || k > nums.len() {
        return Vec::new();
    }

    let mut result = Vec::with_capacity(nums.len() - k + 1);
    let mut deque: VecDeque<usize> = VecDeque::with_capacity(k);

    for (i, &val) in nums.iter().enumerate() {
        // 1. Evict front index if it has slid outside the window `[i + 1 - k ..= i]`
        if let Some(&front_idx) = deque.front() {
            if front_idx + k <= i {
                deque.pop_front();
            }
        }

        // 2. Pop smaller elements from the back so the deque remains monotonically decreasing
        while let Some(&back_idx) = deque.back() {
            if nums[back_idx] <= val {
                deque.pop_back();
            } else {
                break;
            }
        }

        deque.push_back(i);

        // 3. Once the first full window is reached, the front of the deque is the window max!
        if i + 1 >= k {
            result.push(nums[*deque.front().unwrap()]);
        }
    }

    result
}

fn main() {
    let readings = [1, 3, -1, -3, 5, 3, 6, 7];
    let maxes = sliding_window_max(&readings, 3);
    assert_eq!(maxes, vec![3, 3, 5, 5, 6, 7]);
    println!("Sliding window max (k=3): {maxes:?}");

    // Demonstrate wrapping and `make_contiguous`:
    let mut ring = VecDeque::from([20, 30]);
    ring.push_front(10); // Wraps `10` to the end of the internal buffer!
    let (s1, s2) = ring.as_slices();
    println!("Wrapped slices: s1={s1:?}, s2={s2:?}");

    let contiguous: &mut [i32] = ring.make_contiguous();
    println!("After make_contiguous(): {contiguous:?}");
}

Sliding window max (k=3): [3, 3, 5, 5, 6, 7]
Wrapped slices: s1=[10], s2=[20, 30]
After make_contiguous(): [10, 20, 30]