277 Intermediate

Circular Buffer — Functional Queue

Data Structures

Tutorial Video

Text description (accessibility)

This video demonstrates the "Circular Buffer — Functional Queue" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Data Structures. Implement a functional queue with amortized O(1) enqueue and dequeue operations, using two lists (or vectors). Key difference from OCaml: 1. **Ownership model:** OCaml returns new immutable records; Rust consumes `self` and returns the modified queue — same semantics, but Rust reuses the allocation

Tutorial

The Problem

Implement a functional queue with amortized O(1) enqueue and dequeue operations, using two lists (or vectors). This is the classic "banker's queue" from purely functional data structures.

🎯 Learning Outcomes

• Implementing persistent-style data structures in Rust using ownership transfer

• Amortized analysis: reversing the back list into the front list

• Translating OCaml's immutable record updates ({ q with ... }) to Rust's mut self pattern

• Using Option<(T, Self)> to return both a value and the updated structure

🦀 The Rust Way

Rust uses Vec<T> instead of linked lists. The queue takes ownership of self in enqueue/dequeue (consuming the old queue), which mirrors OCaml's functional semantics while allowing in-place mutation. The remove(0) on front is O(n) but happens rarely due to the amortized reversal strategy.

Code Example

#[derive(Debug, Clone)]
pub struct Queue<T> {
    front: Vec<T>,
    back: Vec<T>,
}

impl<T> Queue<T> {
    pub fn new() -> Self { Queue { front: Vec::new(), back: Vec::new() } }
    pub fn is_empty(&self) -> bool { self.front.is_empty() && self.back.is_empty() }
    pub fn enqueue(mut self, x: T) -> Self { self.back.push(x); self }

    pub fn dequeue(mut self) -> Option<(T, Self)> {
        if self.front.is_empty() {
            if self.back.is_empty() { return None; }
            self.back.reverse();
            std::mem::swap(&mut self.front, &mut self.back);
        }
        let head = self.front.remove(0);
        Some((head, self))
    }
}

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

let empty = { front = []; back = [] }
let is_empty q = q.front = [] && q.back = []
let enqueue x q = { q with back = x :: q.back }

let dequeue q = match q.front with
  | h :: t -> Some (h, { q with front = t })
  | [] -> match List.rev q.back with
    | [] -> None
    | h :: t -> Some (h, { front = t; back = [] })

let to_list q = q.front @ List.rev q.back

Key Differences

Ownership model: OCaml returns new immutable records; Rust consumes self and returns the modified queue — same semantics, but Rust reuses the allocation

List vs Vec: OCaml's linked lists have O(1) prepend; Rust's Vec has O(1) push but O(n) remove-from-front — a VecDeque would be more efficient but less pedagogical

Pattern matching: OCaml matches on list constructors (h :: t); Rust checks is_empty() and uses remove(0)

Record update: OCaml's { q with back = x :: q.back } creates a new record; Rust's mut self modifies in place

OCaml Approach

OCaml uses an immutable record with two lists. enqueue creates a new record with the element prepended to back. dequeue pattern-matches on front; when empty, reverses back into front. All operations return new values — the original queue is unchanged.

Full Source

#![allow(clippy::all)]
/// A functional queue with amortized O(1) operations using two `Vec`s.
///
/// Elements are enqueued onto `back` and dequeued from `front`.
/// When `front` is empty, `back` is reversed into `front` — this gives
/// amortized O(1) per operation, matching OCaml's classic two-list queue.
#[derive(Debug, Clone)]
pub struct Queue<T> {
    front: Vec<T>,
    back: Vec<T>,
}

impl<T> Queue<T> {
    /// Create an empty queue.
    pub fn new() -> Self {
        Queue {
            front: Vec::new(),
            back: Vec::new(),
        }
    }

    /// Check if the queue is empty.
    pub fn is_empty(&self) -> bool {
        self.front.is_empty() && self.back.is_empty()
    }

    /// Enqueue an element at the back — returns a new queue (functional style).
    pub fn enqueue(mut self, x: T) -> Self {
        self.back.push(x);
        self
    }

    /// Dequeue an element from the front — returns the element and the remaining queue.
    /// Returns `None` if the queue is empty.
    ///
    /// When `front` is empty, reverses `back` into `front` (amortized O(1)).
    pub fn dequeue(mut self) -> Option<(T, Self)> {
        if self.front.is_empty() {
            if self.back.is_empty() {
                return None;
            }
            self.back.reverse();
            std::mem::swap(&mut self.front, &mut self.back);
        }
        // front is non-empty — pop from the end (which is the oldest element
        // after reversal). This is O(1) and maintains FIFO order.
        let head = self.front.pop().unwrap();
        Some((head, self))
    }

    /// Convert the queue to a `Vec` in FIFO order.
    /// `front` is stored reversed (oldest at end), so we iterate it in reverse.
    /// `back` is stored in push order (oldest first).
    pub fn to_vec(&self) -> Vec<&T> {
        self.front.iter().rev().chain(self.back.iter()).collect()
    }

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

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

/// Recursive drain — collects all elements from the queue in FIFO order.
/// Mirrors the OCaml recursive `drain` function.
pub fn drain_recursive<T>(queue: Queue<T>) -> Vec<T> {
    match queue.dequeue() {
        None => Vec::new(),
        Some((x, rest)) => {
            let mut result = vec![x];
            result.extend(drain_recursive(rest));
            result
        }
    }
}

/// Iterative drain — more idiomatic Rust, avoids stack depth issues.
pub fn drain_iterative<T>(mut queue: Queue<T>) -> Vec<T> {
    let mut result = Vec::new();
    while let Some((x, rest)) = queue.dequeue() {
        result.push(x);
        queue = rest;
    }
    result
}

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

    #[test]
    fn test_empty_queue() {
        let q: Queue<i32> = Queue::new();
        assert!(q.is_empty());
        assert_eq!(q.len(), 0);
        assert!(q.dequeue().is_none());
    }

    #[test]
    fn test_single_element() {
        let q = Queue::new().enqueue(42);
        assert!(!q.is_empty());
        assert_eq!(q.len(), 1);
        let (val, q2) = q.dequeue().unwrap();
        assert_eq!(val, 42);
        assert!(q2.is_empty());
    }

    #[test]
    fn test_fifo_order() {
        let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
        let drained = drain_iterative(q);
        assert_eq!(drained, vec![1, 2, 3]);
    }

    #[test]
    fn test_recursive_drain() {
        let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
        let drained = drain_recursive(q);
        assert_eq!(drained, vec![1, 2, 3]);
    }

    #[test]
    fn test_to_vec() {
        let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
        let v = q.to_vec();
        assert_eq!(v, vec![&1, &2, &3]);
    }

    #[test]
    fn test_interleaved_operations() {
        let q = Queue::new().enqueue(1).enqueue(2);
        let (val, q) = q.dequeue().unwrap();
        assert_eq!(val, 1);
        let q = q.enqueue(3);
        let drained = drain_iterative(q);
        assert_eq!(drained, vec![2, 3]);
    }

    #[test]
    fn test_many_elements() {
        let mut q = Queue::new();
        for i in 0..100 {
            q = q.enqueue(i);
        }
        let drained = drain_iterative(q);
        let expected: Vec<i32> = (0..100).collect();
        assert_eq!(drained, expected);
    }
}

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

let empty = { front = []; back = [] }
let is_empty q = q.front = [] && q.back = []

let enqueue x q = { q with back = x :: q.back }

let dequeue q = match q.front with
  | h :: t -> Some (h, { q with front = t })
  | [] -> match List.rev q.back with
    | [] -> None
    | h :: t -> Some (h, { front = t; back = [] })

let to_list q = q.front @ List.rev q.back

let () =
  let q = empty |> enqueue 1 |> enqueue 2 |> enqueue 3 in
  assert (to_list q = [1; 2; 3]);
  let rec drain q = match dequeue q with
    | None -> []
    | Some (x, q') -> x :: drain q'
  in
  assert (drain q = [1; 2; 3]);
  (* Test interleaved operations *)
  let q2 = empty |> enqueue 1 |> enqueue 2 in
  let (v, q2) = match dequeue q2 with Some p -> p | None -> assert false in
  assert (v = 1);
  let q2 = enqueue 3 q2 in
  assert (drain q2 = [2; 3]);
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_empty_queue() {
        let q: Queue<i32> = Queue::new();
        assert!(q.is_empty());
        assert_eq!(q.len(), 0);
        assert!(q.dequeue().is_none());
    }

    #[test]
    fn test_single_element() {
        let q = Queue::new().enqueue(42);
        assert!(!q.is_empty());
        assert_eq!(q.len(), 1);
        let (val, q2) = q.dequeue().unwrap();
        assert_eq!(val, 42);
        assert!(q2.is_empty());
    }

    #[test]
    fn test_fifo_order() {
        let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
        let drained = drain_iterative(q);
        assert_eq!(drained, vec![1, 2, 3]);
    }

    #[test]
    fn test_recursive_drain() {
        let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
        let drained = drain_recursive(q);
        assert_eq!(drained, vec![1, 2, 3]);
    }

    #[test]
    fn test_to_vec() {
        let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
        let v = q.to_vec();
        assert_eq!(v, vec![&1, &2, &3]);
    }

    #[test]
    fn test_interleaved_operations() {
        let q = Queue::new().enqueue(1).enqueue(2);
        let (val, q) = q.dequeue().unwrap();
        assert_eq!(val, 1);
        let q = q.enqueue(3);
        let drained = drain_iterative(q);
        assert_eq!(drained, vec![2, 3]);
    }

    #[test]
    fn test_many_elements() {
        let mut q = Queue::new();
        for i in 0..100 {
            q = q.enqueue(i);
        }
        let drained = drain_iterative(q);
        let expected: Vec<i32> = (0..100).collect();
        assert_eq!(drained, expected);
    }
}

Deep Comparison

OCaml vs Rust: Circular Buffer — Functional Queue

Side-by-Side Code

OCaml

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

let empty = { front = []; back = [] }
let is_empty q = q.front = [] && q.back = []
let enqueue x q = { q with back = x :: q.back }

let dequeue q = match q.front with
  | h :: t -> Some (h, { q with front = t })
  | [] -> match List.rev q.back with
    | [] -> None
    | h :: t -> Some (h, { front = t; back = [] })

let to_list q = q.front @ List.rev q.back

Rust (idiomatic)

#[derive(Debug, Clone)]
pub struct Queue<T> {
    front: Vec<T>,
    back: Vec<T>,
}

impl<T> Queue<T> {
    pub fn new() -> Self { Queue { front: Vec::new(), back: Vec::new() } }
    pub fn is_empty(&self) -> bool { self.front.is_empty() && self.back.is_empty() }
    pub fn enqueue(mut self, x: T) -> Self { self.back.push(x); self }

    pub fn dequeue(mut self) -> Option<(T, Self)> {
        if self.front.is_empty() {
            if self.back.is_empty() { return None; }
            self.back.reverse();
            std::mem::swap(&mut self.front, &mut self.back);
        }
        let head = self.front.remove(0);
        Some((head, self))
    }
}

Rust (functional/recursive drain)

pub fn drain_recursive<T>(queue: Queue<T>) -> Vec<T> {
    match queue.dequeue() {
        None => Vec::new(),
        Some((x, rest)) => {
            let mut result = vec![x];
            result.extend(drain_recursive(rest));
            result
        }
    }
}

Type Signatures

Concept	OCaml	Rust
Queue type	`'a queue` (record with two lists)	`Queue<T>` (struct with two Vecs)
Empty check	`val is_empty : 'a queue -> bool`	`fn is_empty(&self) -> bool`
Enqueue	`val enqueue : 'a -> 'a queue -> 'a queue`	`fn enqueue(self, x: T) -> Self`
Dequeue	`val dequeue : 'a queue -> ('a * 'a queue) option`	`fn dequeue(self) -> Option<(T, Self)>`
To list	`val to_list : 'a queue -> 'a list`	`fn to_vec(&self) -> Vec<&T>`

Key Insights

Consuming self mirrors immutability: Rust's fn dequeue(self) takes ownership, preventing use of the old queue — this enforces the same "one version at a time" discipline as OCaml's immutable approach, but through the type system rather than runtime copying

**std::mem::swap for efficient reversal:** Instead of OCaml's List.rev which allocates a new list, Rust reverses back in place and swaps it into front with zero allocation

Tuple return pattern: Both languages return Option<(T, Queue)> — the element and the remaining queue. This is natural in OCaml; in Rust it works because Self is moved, not copied

Record update vs mutation: OCaml's { q with back = x :: q.back } creates a new record sharing most fields; Rust's mut self modifies the existing struct in place — same semantics from the caller's perspective

Amortized cost: Both implementations achieve amortized O(1) per operation — each element is reversed at most once. The Rust version additionally benefits from cache-friendly Vec layout

When to Use Each Style

Use idiomatic Rust when: You need a production queue — use VecDeque from std which provides O(1) push/pop on both ends with a ring buffer. The two-Vec approach is primarily pedagogical.

Use recursive Rust when: Teaching functional data structure concepts — the recursive drain mirrors OCaml's recursive traversal pattern and makes the "peel one element at a time" structure explicit.

Exercises

Add a peek method that returns a reference to the front element without removing it, and an is_full predicate.

Implement a thread-safe circular buffer using Arc<Mutex<CircularBuffer<T>>> that can be shared between a producer thread and a consumer thread.

Extend the circular buffer to support batch operations: push_slice that enqueues an entire &[T] atomically (wrapping around if needed) and drain that removes all current elements into a Vec.

Open Source Repos

functional-rust

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

Rust