353 Intermediate

353: VecDeque Double-Ended Queue

Functional Programming

Tutorial

The Problem

Vec supports O(1) push/pop at the back but O(n) at the front (shifting all elements). When you need O(1) at both ends — sliding window algorithms, BFS queues, ring buffers, undo/redo stacks — VecDeque is the right tool. Implemented as a ring buffer (circular array), it maintains head and tail indices and wraps around, giving amortized O(1) for push_front, push_back, pop_front, and pop_back. This data structure dates back to Knuth (TAOCP Vol. 1) and is standard in every language: Python's collections.deque, Java's ArrayDeque, C++'s std::deque.

🎯 Learning Outcomes

• Use VecDeque::push_back and pop_front for queue (FIFO) operations in O(1)

• Use push_front and pop_back for stack (LIFO) operations from the other end

• Implement a sliding window using push_back / pop_front on a deque

• Use rotate_left / rotate_right for efficient in-place rotation

• Convert between VecDeque and Vec with .into_iter().collect() or VecDeque::from(vec)

• Recognize VecDeque as the canonical BFS queue in graph traversal

Code Example

#![allow(clippy::all)]
//! # VecDeque
//! Double-ended queue with O(1) push/pop on both ends.

use std::collections::VecDeque;

pub fn sliding_window(data: &[i32], window_size: usize) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut window: VecDeque<i32> = VecDeque::new();
    for &item in data {
        window.push_back(item);
        if window.len() > window_size {
            window.pop_front();
        }
        if window.len() == window_size {
            result.push(window.iter().cloned().collect());
        }
    }
    result
}

pub fn rotate_left<T: Clone>(items: &[T], n: usize) -> Vec<T> {
    let mut dq: VecDeque<_> = items.iter().cloned().collect();
    dq.rotate_left(n % items.len().max(1));
    dq.into_iter().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sliding_windows() {
        let windows = sliding_window(&[1, 2, 3, 4, 5], 3);
        assert_eq!(windows, vec![vec![1, 2, 3], vec![2, 3, 4], vec![3, 4, 5]]);
    }
    #[test]
    fn rotation() {
        assert_eq!(rotate_left(&[1, 2, 3, 4, 5], 2), vec![3, 4, 5, 1, 2]);
    }
    #[test]
    fn deque_both_ends() {
        let mut dq = VecDeque::new();
        dq.push_back(2);
        dq.push_front(1);
        dq.push_back(3);
        assert_eq!(dq.pop_front(), Some(1));
        assert_eq!(dq.pop_back(), Some(3));
    }
}

(* OCaml: deque via doubly-linked list simulation *)

type 'a deque = { mutable data: 'a list; mutable back: 'a list }

let empty () = { data=[]; back=[] }
let push_back d x = d.back <- x :: d.back
let push_front d x = d.data <- x :: d.data
let pop_front d =
  match d.data with
  | x::xs -> d.data <- xs; Some x
  | [] -> match List.rev d.back with
    | [] -> None
    | x::xs -> d.data <- xs; d.back <- []; Some x

let () =
  let d = empty () in
  push_back d 1; push_back d 2; push_back d 3;
  push_front d 0;
  let rec drain () = match pop_front d with
    | None -> ()
    | Some x -> Printf.printf "%d " x; drain ()
  in drain (); print_newline ()

Key Differences

Aspect	Rust `VecDeque`	OCaml two-list deque
Implementation	Ring buffer (array)	Two lists
Cache locality	Excellent (contiguous memory)	Poor (linked list pointers)
All operations	O(1) amortized	O(1) amortized
Rotation	`rotate_left`/`rotate_right` built in	Manual via list operations
Index access	`dq[i]` O(1)	O(n)

OCaml Approach

OCaml's standard library lacks a built-in deque; the deque package or a pair-of-lists functional deque (Hood-Melville, Okasaki) is used:

(* Functional deque using two lists: O(1) amortized *)
type 'a deque = { front: 'a list; back: 'a list }

let empty = { front = []; back = [] }
let push_back d x = { d with back = x :: d.back }
let pop_front d = match d.front with
  | [] -> (match List.rev d.back with
    | [] -> failwith "empty"
    | x :: rest -> (x, { front = rest; back = [] }))
  | x :: rest -> (x, { d with front = rest })

The two-list deque reverses the back list lazily when the front is exhausted — amortized O(1) per operation. For imperative code, Buffer or Array with manual index arithmetic mimics a ring buffer.

Full Source

#![allow(clippy::all)]
//! # VecDeque
//! Double-ended queue with O(1) push/pop on both ends.

use std::collections::VecDeque;

pub fn sliding_window(data: &[i32], window_size: usize) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut window: VecDeque<i32> = VecDeque::new();
    for &item in data {
        window.push_back(item);
        if window.len() > window_size {
            window.pop_front();
        }
        if window.len() == window_size {
            result.push(window.iter().cloned().collect());
        }
    }
    result
}

pub fn rotate_left<T: Clone>(items: &[T], n: usize) -> Vec<T> {
    let mut dq: VecDeque<_> = items.iter().cloned().collect();
    dq.rotate_left(n % items.len().max(1));
    dq.into_iter().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sliding_windows() {
        let windows = sliding_window(&[1, 2, 3, 4, 5], 3);
        assert_eq!(windows, vec![vec![1, 2, 3], vec![2, 3, 4], vec![3, 4, 5]]);
    }
    #[test]
    fn rotation() {
        assert_eq!(rotate_left(&[1, 2, 3, 4, 5], 2), vec![3, 4, 5, 1, 2]);
    }
    #[test]
    fn deque_both_ends() {
        let mut dq = VecDeque::new();
        dq.push_back(2);
        dq.push_front(1);
        dq.push_back(3);
        assert_eq!(dq.pop_front(), Some(1));
        assert_eq!(dq.pop_back(), Some(3));
    }
}

(* OCaml: deque via doubly-linked list simulation *)

type 'a deque = { mutable data: 'a list; mutable back: 'a list }

let empty () = { data=[]; back=[] }
let push_back d x = d.back <- x :: d.back
let push_front d x = d.data <- x :: d.data
let pop_front d =
  match d.data with
  | x::xs -> d.data <- xs; Some x
  | [] -> match List.rev d.back with
    | [] -> None
    | x::xs -> d.data <- xs; d.back <- []; Some x

let () =
  let d = empty () in
  push_back d 1; push_back d 2; push_back d 3;
  push_front d 0;
  let rec drain () = match pop_front d with
    | None -> ()
    | Some x -> Printf.printf "%d " x; drain ()
  in drain (); print_newline ()

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sliding_windows() {
        let windows = sliding_window(&[1, 2, 3, 4, 5], 3);
        assert_eq!(windows, vec![vec![1, 2, 3], vec![2, 3, 4], vec![3, 4, 5]]);
    }
    #[test]
    fn rotation() {
        assert_eq!(rotate_left(&[1, 2, 3, 4, 5], 2), vec![3, 4, 5, 1, 2]);
    }
    #[test]
    fn deque_both_ends() {
        let mut dq = VecDeque::new();
        dq.push_back(2);
        dq.push_front(1);
        dq.push_back(3);
        assert_eq!(dq.pop_front(), Some(1));
        assert_eq!(dq.pop_back(), Some(3));
    }
}

Deep Comparison

OCaml vs Rust: Vecdeque Deque

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

BFS with VecDeque: Implement breadth-first search on a graph represented as Vec<Vec<usize>> (adjacency list) using a VecDeque as the frontier queue; return the visited order.

Sliding window maximum: Given a VecDeque<(usize, i32)> (monotonic deque of index-value pairs), implement O(n) sliding window maximum without computing max over each window separately.

Ring buffer: Implement a fixed-capacity ring buffer using VecDeque::with_capacity(n) that overwrites the oldest entry when full; test with 5-element capacity and 10 insertions.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust