968 Intermediate

968 Deque

Functional Programming

Tutorial

The Problem

Implement a double-ended queue (deque) that supports O(1) amortized push and pop at both front and back. Present two approaches: wrapping Rust's standard VecDeque (ring buffer internally) and a functional two-stack deque that mirrors OCaml's approach — two lists where the front list and reversed back list together represent the queue contents.

🎯 Learning Outcomes

• Use VecDeque<T> from std::collections for a production-ready O(1) amortized deque

• Understand the two-stack functional deque: (front_list, back_list) where pop_front consumes front, and when front is empty it reverses back into front

• Implement the rebalancing step: when front is empty on pop_front, reverse back and swap lists

• Recognize that the two-stack deque is amortized O(1) per operation (each element is reversed at most once)

• Compare mutable ring buffer vs persistent functional deque

Code Example

#![allow(clippy::all)]
// 968: Double-Ended Queue (Deque)
// Approach 1: std VecDeque (built-in, O(1) amortized all operations)
// Approach 2: Functional two-stack deque (mirrors OCaml approach)

use std::collections::VecDeque;

// --- Approach 1: VecDeque (idiomatic Rust, ring buffer internally) ---
pub struct Deque<T> {
    inner: VecDeque<T>,
}

impl<T> Deque<T> {
    pub fn new() -> Self {
        Deque {
            inner: VecDeque::new(),
        }
    }

    pub fn push_front(&mut self, x: T) {
        self.inner.push_front(x);
    }
    pub fn push_back(&mut self, x: T) {
        self.inner.push_back(x);
    }
    pub fn pop_front(&mut self) -> Option<T> {
        self.inner.pop_front()
    }
    pub fn pop_back(&mut self) -> Option<T> {
        self.inner.pop_back()
    }
    pub fn peek_front(&self) -> Option<&T> {
        self.inner.front()
    }
    pub fn peek_back(&self) -> Option<&T> {
        self.inner.back()
    }
    pub fn size(&self) -> usize {
        self.inner.len()
    }
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
}

impl<T> Default for Deque<T> {
    fn default() -> Self {
        Self::new()
    }
}

// --- Approach 2: Functional two-stack deque (mirrors OCaml) ---
#[derive(Clone, Debug)]
pub struct FunctionalDeque<T: Clone> {
    front: Vec<T>, // front stack (top = front of deque)
    back: Vec<T>,  // back stack (top = back of deque)
}

impl<T: Clone + PartialEq> FunctionalDeque<T> {
    pub fn new() -> Self {
        FunctionalDeque {
            front: vec![],
            back: vec![],
        }
    }

    pub fn is_empty(&self) -> bool {
        self.front.is_empty() && self.back.is_empty()
    }

    pub fn size(&self) -> usize {
        self.front.len() + self.back.len()
    }

    fn balance(mut self) -> Self {
        if self.front.is_empty() {
            self.front = self.back.clone();
            self.front.reverse();
            self.back.clear();
        }
        self
    }

    pub fn push_front(mut self, x: T) -> Self {
        self.front.push(x);
        self.balance()
    }

    pub fn push_back(mut self, x: T) -> Self {
        self.back.push(x);
        self.balance()
    }

    pub fn pop_front(self) -> Option<(T, Self)> {
        let mut d = self.balance();
        if d.front.is_empty() {
            None
        } else {
            let x = d.front.pop().unwrap();
            Some((x, d.balance()))
        }
    }

    pub fn peek_front(&self) -> Option<&T> {
        self.front.last()
    }
}

impl<T: Clone + PartialEq> Default for FunctionalDeque<T> {
    fn default() -> Self {
        Self::new()
    }
}

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

    #[test]
    fn test_vecdeque_operations() {
        let mut d: Deque<i32> = Deque::new();
        assert!(d.is_empty());

        d.push_back(1);
        d.push_back(2);
        d.push_back(3);
        d.push_front(0);

        assert_eq!(d.size(), 4);
        assert_eq!(d.peek_front(), Some(&0));
        assert_eq!(d.peek_back(), Some(&3));

        assert_eq!(d.pop_front(), Some(0));
        assert_eq!(d.pop_back(), Some(3));
        assert_eq!(d.size(), 2);
    }

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

    #[test]
    fn test_functional_deque() {
        let d: FunctionalDeque<i32> = FunctionalDeque::new();
        assert!(d.is_empty());

        let d = d.push_back(1).push_back(2).push_back(3).push_front(0);
        assert_eq!(d.size(), 4);
        assert_eq!(d.peek_front(), Some(&0));

        let (v, d) = d.pop_front().unwrap();
        assert_eq!(v, 0);
        assert_eq!(d.peek_front(), Some(&1));
    }

    #[test]
    fn test_fifo_order() {
        let mut d: Deque<i32> = Deque::new();
        for i in 1..=5 {
            d.push_back(i);
        }
        let mut out = vec![];
        while let Some(v) = d.pop_front() {
            out.push(v);
        }
        assert_eq!(out, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_lifo_order() {
        let mut d: Deque<i32> = Deque::new();
        for i in 1..=5 {
            d.push_back(i);
        }
        let mut out = vec![];
        while let Some(v) = d.pop_back() {
            out.push(v);
        }
        assert_eq!(out, vec![5, 4, 3, 2, 1]);
    }
}

(* 968: Double-Ended Queue (Deque) *)
(* OCaml: pair of lists (front, back) for amortized O(1) operations *)
(* Classic functional deque using two stacks *)

type 'a deque = {
  front: 'a list;
  back: 'a list;
}

let empty = { front = []; back = [] }

let is_empty d = d.front = [] && d.back = []

let size d = List.length d.front + List.length d.back

(* Balance: if front is empty, reverse back into front *)
let balance d =
  match d.front with
  | [] -> { front = List.rev d.back; back = [] }
  | _ -> d

let push_front x d = balance { d with front = x :: d.front }

let push_back x d = balance { d with back = x :: d.back }

let pop_front d =
  let d = balance d in
  match d.front with
  | [] -> None
  | x :: rest -> Some (x, balance { d with front = rest })

let pop_back d =
  let d = balance { front = d.back; back = d.front } in
  match d.front with
  | [] -> None
  | x :: rest -> Some (x, { front = d.back; back = rest })

let peek_front d =
  let d = balance d in
  match d.front with
  | [] -> None
  | x :: _ -> Some x

let peek_back d =
  let d = balance { front = d.back; back = d.front } in
  match d.front with
  | [] -> None
  | x :: _ -> Some x

let () =
  let d = empty in
  assert (is_empty d);

  let d = push_back 1 d in
  let d = push_back 2 d in
  let d = push_back 3 d in
  let d = push_front 0 d in

  assert (size d = 4);
  assert (peek_front d = Some 0);
  assert (peek_back d = Some 3);

  let (v, d) = Option.get (pop_front d) in
  assert (v = 0);
  assert (peek_front d = Some 1);

  let (v, d) = Option.get (pop_back d) in
  assert (v = 3);
  assert (size d = 2);

  let d = push_front 10 d in
  let d = push_back 20 d in
  assert (size d = 4);

  let (v, _) = Option.get (pop_front d) in
  assert (v = 10);

  assert (pop_front empty = None);
  assert (pop_back empty = None);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Standard deque	`VecDeque` — ring buffer, O(1)	No stdlib deque; `Queue` is FIFO only
Functional variant	Two `Vec`s, mutable	Two lists, immutable
Reversal	`drain(..).rev().collect()`	`List.rev`
Persistence	Mutable — no history	Persistent — old versions accessible

VecDeque is the right default. The two-stack approach illuminates the functional deque structure but has higher constant factors due to occasional full-list reversal.

OCaml Approach

(* Functional two-list deque *)
type 'a deque = { front: 'a list; back: 'a list }

let empty = { front = []; back = [] }

let push_back x d = { d with back = x :: d.back }
let push_front x d = { d with front = x :: d.front }

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

let pop_back d = match d.back with
  | x :: rest -> Some (x, { d with back = rest })
  | [] -> match List.rev d.front with
    | [] -> None
    | x :: rest -> Some (x, { back = rest; front = [] })

OCaml's functional deque is persistent — pop_front returns a new deque value rather than mutating. Structural sharing means push_back O(1) allocation. List reversal still occurs O(n) occasionally but amortizes to O(1).

Full Source

#![allow(clippy::all)]
// 968: Double-Ended Queue (Deque)
// Approach 1: std VecDeque (built-in, O(1) amortized all operations)
// Approach 2: Functional two-stack deque (mirrors OCaml approach)

use std::collections::VecDeque;

// --- Approach 1: VecDeque (idiomatic Rust, ring buffer internally) ---
pub struct Deque<T> {
    inner: VecDeque<T>,
}

impl<T> Deque<T> {
    pub fn new() -> Self {
        Deque {
            inner: VecDeque::new(),
        }
    }

    pub fn push_front(&mut self, x: T) {
        self.inner.push_front(x);
    }
    pub fn push_back(&mut self, x: T) {
        self.inner.push_back(x);
    }
    pub fn pop_front(&mut self) -> Option<T> {
        self.inner.pop_front()
    }
    pub fn pop_back(&mut self) -> Option<T> {
        self.inner.pop_back()
    }
    pub fn peek_front(&self) -> Option<&T> {
        self.inner.front()
    }
    pub fn peek_back(&self) -> Option<&T> {
        self.inner.back()
    }
    pub fn size(&self) -> usize {
        self.inner.len()
    }
    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
}

impl<T> Default for Deque<T> {
    fn default() -> Self {
        Self::new()
    }
}

// --- Approach 2: Functional two-stack deque (mirrors OCaml) ---
#[derive(Clone, Debug)]
pub struct FunctionalDeque<T: Clone> {
    front: Vec<T>, // front stack (top = front of deque)
    back: Vec<T>,  // back stack (top = back of deque)
}

impl<T: Clone + PartialEq> FunctionalDeque<T> {
    pub fn new() -> Self {
        FunctionalDeque {
            front: vec![],
            back: vec![],
        }
    }

    pub fn is_empty(&self) -> bool {
        self.front.is_empty() && self.back.is_empty()
    }

    pub fn size(&self) -> usize {
        self.front.len() + self.back.len()
    }

    fn balance(mut self) -> Self {
        if self.front.is_empty() {
            self.front = self.back.clone();
            self.front.reverse();
            self.back.clear();
        }
        self
    }

    pub fn push_front(mut self, x: T) -> Self {
        self.front.push(x);
        self.balance()
    }

    pub fn push_back(mut self, x: T) -> Self {
        self.back.push(x);
        self.balance()
    }

    pub fn pop_front(self) -> Option<(T, Self)> {
        let mut d = self.balance();
        if d.front.is_empty() {
            None
        } else {
            let x = d.front.pop().unwrap();
            Some((x, d.balance()))
        }
    }

    pub fn peek_front(&self) -> Option<&T> {
        self.front.last()
    }
}

impl<T: Clone + PartialEq> Default for FunctionalDeque<T> {
    fn default() -> Self {
        Self::new()
    }
}

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

    #[test]
    fn test_vecdeque_operations() {
        let mut d: Deque<i32> = Deque::new();
        assert!(d.is_empty());

        d.push_back(1);
        d.push_back(2);
        d.push_back(3);
        d.push_front(0);

        assert_eq!(d.size(), 4);
        assert_eq!(d.peek_front(), Some(&0));
        assert_eq!(d.peek_back(), Some(&3));

        assert_eq!(d.pop_front(), Some(0));
        assert_eq!(d.pop_back(), Some(3));
        assert_eq!(d.size(), 2);
    }

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

    #[test]
    fn test_functional_deque() {
        let d: FunctionalDeque<i32> = FunctionalDeque::new();
        assert!(d.is_empty());

        let d = d.push_back(1).push_back(2).push_back(3).push_front(0);
        assert_eq!(d.size(), 4);
        assert_eq!(d.peek_front(), Some(&0));

        let (v, d) = d.pop_front().unwrap();
        assert_eq!(v, 0);
        assert_eq!(d.peek_front(), Some(&1));
    }

    #[test]
    fn test_fifo_order() {
        let mut d: Deque<i32> = Deque::new();
        for i in 1..=5 {
            d.push_back(i);
        }
        let mut out = vec![];
        while let Some(v) = d.pop_front() {
            out.push(v);
        }
        assert_eq!(out, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_lifo_order() {
        let mut d: Deque<i32> = Deque::new();
        for i in 1..=5 {
            d.push_back(i);
        }
        let mut out = vec![];
        while let Some(v) = d.pop_back() {
            out.push(v);
        }
        assert_eq!(out, vec![5, 4, 3, 2, 1]);
    }
}

(* 968: Double-Ended Queue (Deque) *)
(* OCaml: pair of lists (front, back) for amortized O(1) operations *)
(* Classic functional deque using two stacks *)

type 'a deque = {
  front: 'a list;
  back: 'a list;
}

let empty = { front = []; back = [] }

let is_empty d = d.front = [] && d.back = []

let size d = List.length d.front + List.length d.back

(* Balance: if front is empty, reverse back into front *)
let balance d =
  match d.front with
  | [] -> { front = List.rev d.back; back = [] }
  | _ -> d

let push_front x d = balance { d with front = x :: d.front }

let push_back x d = balance { d with back = x :: d.back }

let pop_front d =
  let d = balance d in
  match d.front with
  | [] -> None
  | x :: rest -> Some (x, balance { d with front = rest })

let pop_back d =
  let d = balance { front = d.back; back = d.front } in
  match d.front with
  | [] -> None
  | x :: rest -> Some (x, { front = d.back; back = rest })

let peek_front d =
  let d = balance d in
  match d.front with
  | [] -> None
  | x :: _ -> Some x

let peek_back d =
  let d = balance { front = d.back; back = d.front } in
  match d.front with
  | [] -> None
  | x :: _ -> Some x

let () =
  let d = empty in
  assert (is_empty d);

  let d = push_back 1 d in
  let d = push_back 2 d in
  let d = push_back 3 d in
  let d = push_front 0 d in

  assert (size d = 4);
  assert (peek_front d = Some 0);
  assert (peek_back d = Some 3);

  let (v, d) = Option.get (pop_front d) in
  assert (v = 0);
  assert (peek_front d = Some 1);

  let (v, d) = Option.get (pop_back d) in
  assert (v = 3);
  assert (size d = 2);

  let d = push_front 10 d in
  let d = push_back 20 d in
  assert (size d = 4);

  let (v, _) = Option.get (pop_front d) in
  assert (v = 10);

  assert (pop_front empty = None);
  assert (pop_back empty = None);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_vecdeque_operations() {
        let mut d: Deque<i32> = Deque::new();
        assert!(d.is_empty());

        d.push_back(1);
        d.push_back(2);
        d.push_back(3);
        d.push_front(0);

        assert_eq!(d.size(), 4);
        assert_eq!(d.peek_front(), Some(&0));
        assert_eq!(d.peek_back(), Some(&3));

        assert_eq!(d.pop_front(), Some(0));
        assert_eq!(d.pop_back(), Some(3));
        assert_eq!(d.size(), 2);
    }

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

    #[test]
    fn test_functional_deque() {
        let d: FunctionalDeque<i32> = FunctionalDeque::new();
        assert!(d.is_empty());

        let d = d.push_back(1).push_back(2).push_back(3).push_front(0);
        assert_eq!(d.size(), 4);
        assert_eq!(d.peek_front(), Some(&0));

        let (v, d) = d.pop_front().unwrap();
        assert_eq!(v, 0);
        assert_eq!(d.peek_front(), Some(&1));
    }

    #[test]
    fn test_fifo_order() {
        let mut d: Deque<i32> = Deque::new();
        for i in 1..=5 {
            d.push_back(i);
        }
        let mut out = vec![];
        while let Some(v) = d.pop_front() {
            out.push(v);
        }
        assert_eq!(out, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_lifo_order() {
        let mut d: Deque<i32> = Deque::new();
        for i in 1..=5 {
            d.push_back(i);
        }
        let mut out = vec![];
        while let Some(v) = d.pop_back() {
            out.push(v);
        }
        assert_eq!(out, vec![5, 4, 3, 2, 1]);
    }
}

Deep Comparison

Deque — Comparison

Core Insight

The functional two-list deque (front, back) achieves amortized O(1) by reversing the back list into the front when the front empties. OCaml's immutable lists make this pattern natural; Rust can implement it with Vec but idiomatic Rust uses the built-in VecDeque (circular buffer, true O(1) at both ends).

OCaml Approach

• { front: 'a list; back: 'a list } — pure functional record

• List.rev to rebalance when front is empty

• All operations return new deques (immutable, persistent)

• Pattern matching: match d.front with [] -> ...

• { d with front = x :: d.front } — record update syntax

Rust Approach (two approaches)

• VecDeque<T> — std ring buffer, O(1) push/pop both ends, preferred

• push_front, push_back, pop_front, pop_back — direct methods

• Functional version: Vec<T> as stack (.push = push to top, .pop = pop from top)

• Functional version: mut self — consume and return new (value semantics mimicking immutability)

• self.front.reverse() for rebalancing

Comparison Table

Aspect	OCaml	Rust
Idiomatic impl	Two-list `{ front; back }`	`VecDeque<T>` (ring buffer)
Push front	`x :: d.front` (O(1))	`push_front(x)` (O(1))
Push back	`x :: d.back` (O(1))	`push_back(x)` (O(1))
Pop front	Pattern match on list	`pop_front()` → `Option<T>`
Rebalance	`List.rev d.back`	`front.reverse()`
Mutability	Immutable (persistent)	`&mut self` (mutable)
Value type	Record (immutable)	`VecDeque<T>` (mutable) or owned struct
Memory	GC'd list nodes	Contiguous ring buffer

Exercises

Implement to_vec(&self) -> Vec<T> for FuncDeque — collect elements front-to-back.

Implement a sliding window maximum using VecDeque as a monotone deque.

Implement the two-stack deque with Rc<Vec<T>> for structural sharing (persistent Rust version).

Benchmark VecDeque vs FuncDeque for 1,000,000 alternating push_back/pop_front operations.

Implement rotate_left(n) on VecDeque — move the first n elements to the back.

Open Source Repos

functional-rust

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

Rust