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

//! A double-ended queue built from two stacks, mirroring the OCaml example.
//!
//! The deque stores a `front` vector (top of the stack is the logical
//! front of the queue) and a `back` vector (top of the stack is the
//! logical back). When `pop_front` finds `front` empty, the whole `back`
//! is reversed into `front`, giving amortized `O(1)` on every operation.

/// A double-ended queue with amortized `O(1)` push/pop on both ends.
#[derive(Debug, Clone, Default)]
pub struct Deque<T> {
    front: Vec<T>,
    back: Vec<T>,
}

impl<T> Deque<T> {
    /// Creates an empty deque.
    pub fn new() -> Self {
        Self {
            front: Vec::new(),
            back: Vec::new(),
        }
    }

    /// Returns the total number of elements in the deque.
    pub fn len(&self) -> usize {
        self.front.len() + self.back.len()
    }

    /// Returns `true` if the deque contains no elements.
    pub fn is_empty(&self) -> bool {
        self.front.is_empty() && self.back.is_empty()
    }

    /// Pushes `x` onto the back of the deque.
    pub fn push_back(&mut self, x: T) {
        self.back.push(x);
    }

    /// Pushes `x` onto the front of the deque.
    pub fn push_front(&mut self, x: T) {
        self.front.push(x);
    }

    /// Removes and returns the front element, or `None` if empty.
    pub fn pop_front(&mut self) -> Option<T> {
        if let Some(x) = self.front.pop() {
            return Some(x);
        }
        if self.back.is_empty() {
            return None;
        }
        // Move `back` into `front` reversed, so the oldest back-pushed
        // item lands at the top of the `front` stack.
        self.front = std::mem::take(&mut self.back);
        self.front.reverse();
        self.front.pop()
    }

    /// Removes and returns the back element, or `None` if empty.
    pub fn pop_back(&mut self) -> Option<T> {
        if let Some(x) = self.back.pop() {
            return Some(x);
        }
        if self.front.is_empty() {
            return None;
        }
        self.back = std::mem::take(&mut self.front);
        self.back.reverse();
        self.back.pop()
    }
}

impl<T> FromIterator<T> for Deque<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut d = Deque::new();
        for x in iter {
            d.push_back(x);
        }
        d
    }
}

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

    #[test]
    fn new_is_empty() {
        let d: Deque<i32> = Deque::new();
        assert!(d.is_empty());
        assert_eq!(d.len(), 0);
    }

    #[test]
    fn pop_on_empty_returns_none() {
        let mut d: Deque<i32> = Deque::new();
        assert_eq!(d.pop_front(), None);
        assert_eq!(d.pop_back(), None);
    }

    #[test]
    fn ocaml_example_order() {
        let mut d = Deque::new();
        d.push_back(1);
        d.push_back(2);
        d.push_back(3);
        d.push_front(0);
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![0, 1, 2, 3]);
    }

    #[test]
    fn push_back_then_pop_front_is_fifo() {
        let mut d = Deque::new();
        for i in 0..5 {
            d.push_back(i);
        }
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn push_front_then_pop_front_is_lifo() {
        let mut d = Deque::new();
        for i in 0..5 {
            d.push_front(i);
        }
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![4, 3, 2, 1, 0]);
    }

    #[test]
    fn pop_back_mirrors_pop_front() {
        let mut d: Deque<i32> = (1..=4).collect();
        assert_eq!(d.pop_back(), Some(4));
        assert_eq!(d.pop_back(), Some(3));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), Some(2));
        assert!(d.is_empty());
    }

    #[test]
    fn interleaved_ops() {
        let mut d = Deque::new();
        d.push_back(1);
        d.push_front(0);
        d.push_back(2);
        assert_eq!(d.pop_front(), Some(0));
        d.push_front(-1);
        assert_eq!(d.pop_back(), Some(2));
        assert_eq!(d.len(), 2);
        assert_eq!(d.pop_front(), Some(-1));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), None);
    }

    #[test]
    fn from_iter_preserves_order() {
        let mut d: Deque<i32> = (0..3).collect();
        assert_eq!(d.pop_front(), Some(0));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), Some(2));
    }
}

(* 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

//! A double-ended queue built from two stacks, mirroring the OCaml example.
//!
//! The deque stores a `front` vector (top of the stack is the logical
//! front of the queue) and a `back` vector (top of the stack is the
//! logical back). When `pop_front` finds `front` empty, the whole `back`
//! is reversed into `front`, giving amortized `O(1)` on every operation.

/// A double-ended queue with amortized `O(1)` push/pop on both ends.
#[derive(Debug, Clone, Default)]
pub struct Deque<T> {
    front: Vec<T>,
    back: Vec<T>,
}

impl<T> Deque<T> {
    /// Creates an empty deque.
    pub fn new() -> Self {
        Self {
            front: Vec::new(),
            back: Vec::new(),
        }
    }

    /// Returns the total number of elements in the deque.
    pub fn len(&self) -> usize {
        self.front.len() + self.back.len()
    }

    /// Returns `true` if the deque contains no elements.
    pub fn is_empty(&self) -> bool {
        self.front.is_empty() && self.back.is_empty()
    }

    /// Pushes `x` onto the back of the deque.
    pub fn push_back(&mut self, x: T) {
        self.back.push(x);
    }

    /// Pushes `x` onto the front of the deque.
    pub fn push_front(&mut self, x: T) {
        self.front.push(x);
    }

    /// Removes and returns the front element, or `None` if empty.
    pub fn pop_front(&mut self) -> Option<T> {
        if let Some(x) = self.front.pop() {
            return Some(x);
        }
        if self.back.is_empty() {
            return None;
        }
        // Move `back` into `front` reversed, so the oldest back-pushed
        // item lands at the top of the `front` stack.
        self.front = std::mem::take(&mut self.back);
        self.front.reverse();
        self.front.pop()
    }

    /// Removes and returns the back element, or `None` if empty.
    pub fn pop_back(&mut self) -> Option<T> {
        if let Some(x) = self.back.pop() {
            return Some(x);
        }
        if self.front.is_empty() {
            return None;
        }
        self.back = std::mem::take(&mut self.front);
        self.back.reverse();
        self.back.pop()
    }
}

impl<T> FromIterator<T> for Deque<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut d = Deque::new();
        for x in iter {
            d.push_back(x);
        }
        d
    }
}

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

    #[test]
    fn new_is_empty() {
        let d: Deque<i32> = Deque::new();
        assert!(d.is_empty());
        assert_eq!(d.len(), 0);
    }

    #[test]
    fn pop_on_empty_returns_none() {
        let mut d: Deque<i32> = Deque::new();
        assert_eq!(d.pop_front(), None);
        assert_eq!(d.pop_back(), None);
    }

    #[test]
    fn ocaml_example_order() {
        let mut d = Deque::new();
        d.push_back(1);
        d.push_back(2);
        d.push_back(3);
        d.push_front(0);
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![0, 1, 2, 3]);
    }

    #[test]
    fn push_back_then_pop_front_is_fifo() {
        let mut d = Deque::new();
        for i in 0..5 {
            d.push_back(i);
        }
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn push_front_then_pop_front_is_lifo() {
        let mut d = Deque::new();
        for i in 0..5 {
            d.push_front(i);
        }
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![4, 3, 2, 1, 0]);
    }

    #[test]
    fn pop_back_mirrors_pop_front() {
        let mut d: Deque<i32> = (1..=4).collect();
        assert_eq!(d.pop_back(), Some(4));
        assert_eq!(d.pop_back(), Some(3));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), Some(2));
        assert!(d.is_empty());
    }

    #[test]
    fn interleaved_ops() {
        let mut d = Deque::new();
        d.push_back(1);
        d.push_front(0);
        d.push_back(2);
        assert_eq!(d.pop_front(), Some(0));
        d.push_front(-1);
        assert_eq!(d.pop_back(), Some(2));
        assert_eq!(d.len(), 2);
        assert_eq!(d.pop_front(), Some(-1));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), None);
    }

    #[test]
    fn from_iter_preserves_order() {
        let mut d: Deque<i32> = (0..3).collect();
        assert_eq!(d.pop_front(), Some(0));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), Some(2));
    }
}

(* 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 new_is_empty() {
        let d: Deque<i32> = Deque::new();
        assert!(d.is_empty());
        assert_eq!(d.len(), 0);
    }

    #[test]
    fn pop_on_empty_returns_none() {
        let mut d: Deque<i32> = Deque::new();
        assert_eq!(d.pop_front(), None);
        assert_eq!(d.pop_back(), None);
    }

    #[test]
    fn ocaml_example_order() {
        let mut d = Deque::new();
        d.push_back(1);
        d.push_back(2);
        d.push_back(3);
        d.push_front(0);
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![0, 1, 2, 3]);
    }

    #[test]
    fn push_back_then_pop_front_is_fifo() {
        let mut d = Deque::new();
        for i in 0..5 {
            d.push_back(i);
        }
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn push_front_then_pop_front_is_lifo() {
        let mut d = Deque::new();
        for i in 0..5 {
            d.push_front(i);
        }
        let drained: Vec<_> = std::iter::from_fn(|| d.pop_front()).collect();
        assert_eq!(drained, vec![4, 3, 2, 1, 0]);
    }

    #[test]
    fn pop_back_mirrors_pop_front() {
        let mut d: Deque<i32> = (1..=4).collect();
        assert_eq!(d.pop_back(), Some(4));
        assert_eq!(d.pop_back(), Some(3));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), Some(2));
        assert!(d.is_empty());
    }

    #[test]
    fn interleaved_ops() {
        let mut d = Deque::new();
        d.push_back(1);
        d.push_front(0);
        d.push_back(2);
        assert_eq!(d.pop_front(), Some(0));
        d.push_front(-1);
        assert_eq!(d.pop_back(), Some(2));
        assert_eq!(d.len(), 2);
        assert_eq!(d.pop_front(), Some(-1));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), None);
    }

    #[test]
    fn from_iter_preserves_order() {
        let mut d: Deque<i32> = (0..3).collect();
        assert_eq!(d.pop_front(), Some(0));
        assert_eq!(d.pop_front(), Some(1));
        assert_eq!(d.pop_front(), Some(2));
    }
}

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