1032 Intermediate

1032-vec-deque-rotation — VecDeque Rotation

Functional Programming

Tutorial

The Problem

A double-ended queue (deque) supports efficient insertion and removal at both ends. Ring buffers — fixed-size deques used for circular logs, producer-consumer queues, and audio sample buffers — are a classic application. Rotation (shifting all elements left or right by k positions) requires O(1) with a proper deque but O(n) with a plain Vec.

Rust's VecDeque is a ring-buffer backed deque providing O(1) amortized push and pop at both ends. Its rotate_left and rotate_right methods are O(min(k, n-k)), making rotation efficient.

🎯 Learning Outcomes

• Use VecDeque for O(1) push and pop at both ends

• Apply rotate_left and rotate_right for efficient rotation

• Implement a sliding window using VecDeque as a fixed-size buffer

• Use VecDeque as a BFS queue

• Convert between Vec and VecDeque

Code Example

#![allow(clippy::all)]
// 1032: VecDeque Rotation — Efficient Front/Back Operations
// VecDeque is a ring buffer: O(1) push/pop at both ends

use std::collections::VecDeque;

/// Basic front/back operations
fn basic_deque() {
    let mut dq = VecDeque::new();
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_front(0);

    assert_eq!(dq.pop_front(), Some(0));
    assert_eq!(dq.pop_front(), Some(1));
    assert_eq!(dq.pop_back(), Some(3));
    assert_eq!(dq.pop_back(), Some(2));
    assert!(dq.is_empty());
}

/// Rotation using VecDeque::rotate_left/rotate_right
fn rotation() {
    let mut dq: VecDeque<_> = [1, 2, 3, 4, 5].into_iter().collect();

    // Rotate left by 2: [3, 4, 5, 1, 2]
    dq.rotate_left(2);
    assert_eq!(dq, [3, 4, 5, 1, 2].into_iter().collect::<VecDeque<_>>());

    // Rotate right by 2: back to [1, 2, 3, 4, 5]
    dq.rotate_right(2);
    assert_eq!(dq, [1, 2, 3, 4, 5].into_iter().collect::<VecDeque<_>>());
}

/// Using VecDeque as a sliding window
fn sliding_window() {
    let data = vec![1, 2, 3, 4, 5, 6, 7];
    let window_size = 3;
    let mut window: VecDeque<i32> = VecDeque::with_capacity(window_size);
    let mut sums = Vec::new();

    for &val in &data {
        window.push_back(val);
        if window.len() > window_size {
            window.pop_front();
        }
        if window.len() == window_size {
            let sum: i32 = window.iter().sum();
            sums.push(sum);
        }
    }

    assert_eq!(sums, vec![6, 9, 12, 15, 18]); // 1+2+3, 2+3+4, ...
}

/// VecDeque to Vec and back
fn conversions() {
    let v = vec![1, 2, 3, 4, 5];
    let mut dq: VecDeque<_> = v.into_iter().collect();

    dq.push_front(0);
    // make_contiguous ensures internal buffer is contiguous
    dq.make_contiguous();

    let v: Vec<_> = dq.into_iter().collect();
    assert_eq!(v, vec![0, 1, 2, 3, 4, 5]);
}

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

    #[test]
    fn test_basic_deque() {
        basic_deque();
    }

    #[test]
    fn test_rotation() {
        rotation();
    }

    #[test]
    fn test_sliding_window() {
        sliding_window();
    }

    #[test]
    fn test_conversions() {
        conversions();
    }

    #[test]
    fn test_indexed_access() {
        let dq: VecDeque<_> = [10, 20, 30].into_iter().collect();
        assert_eq!(dq[0], 10);
        assert_eq!(dq[1], 20);
        assert_eq!(dq[2], 30);
    }
}

(* 1032: VecDeque Rotation — Efficient Front/Back Operations *)
(* OCaml uses lists (efficient at front) or Queue module *)

(* Approach 1: List as a deque — efficient front, O(n) back *)
let list_deque () =
  let q = [1; 2; 3; 4; 5] in
  (* Push front: O(1) *)
  let q = 0 :: q in
  assert (q = [0; 1; 2; 3; 4; 5]);
  (* Pop front: O(1) *)
  let (front, q) = (List.hd q, List.tl q) in
  assert (front = 0);
  assert (q = [1; 2; 3; 4; 5]);
  (* Push back: O(n) *)
  let q = q @ [6] in
  assert (q = [1; 2; 3; 4; 5; 6])

(* Approach 2: Two-list queue for amortized O(1) both ends *)
type 'a deque = { front: 'a list; back: 'a list }

let empty = { front = []; back = [] }
let push_front x d = { d with front = x :: d.front }
let push_back x d = { d with back = x :: d.back }

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

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

let two_list_deque () =
  let d = empty in
  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
  let (v, d) = Option.get (pop_front d) in
  assert (v = 0);
  let (v, d) = Option.get (pop_front d) in
  assert (v = 1);
  let (v, _d) = Option.get (pop_back d) in
  assert (v = 3)

(* Approach 3: Rotation *)
let rotate_left lst n =
  let len = List.length lst in
  let n = n mod len in
  let rec take_drop i = function
    | [] -> ([], [])
    | x :: xs when i > 0 ->
      let (taken, rest) = take_drop (i - 1) xs in
      (x :: taken, rest)
    | xs -> ([], xs)
  in
  let (front, back) = take_drop n lst in
  back @ front

let rotation_test () =
  let lst = [1; 2; 3; 4; 5] in
  assert (rotate_left lst 2 = [3; 4; 5; 1; 2]);
  assert (rotate_left lst 0 = [1; 2; 3; 4; 5])

let () =
  list_deque ();
  two_list_deque ();
  rotation_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Rotation: Rust's VecDeque::rotate_left is a built-in method; OCaml requires manual element movement or a custom implementation.

Ring buffer: VecDeque is backed by a ring buffer with a start offset; OCaml's Queue uses a linked list.

Index access: VecDeque supports O(1) index access via deque[i]; OCaml's Queue is sequential-access only.

Conversion: Rust provides VecDeque::from(vec) and vec.into() for zero-copy conversion; OCaml requires explicit iteration.

OCaml Approach

OCaml's standard library lacks a deque, but Queue provides a FIFO queue with O(1) add and take:

let sliding_window data window_size =
  let q = Queue.create () in
  List.map (fun x ->
    Queue.add x q;
    if Queue.length q > window_size then ignore (Queue.pop q);
    Queue.fold (+) 0 q  (* sum of window *)
  ) data

The Base.Deque module and containers library provide full double-ended queues with rotation.

Full Source

#![allow(clippy::all)]
// 1032: VecDeque Rotation — Efficient Front/Back Operations
// VecDeque is a ring buffer: O(1) push/pop at both ends

use std::collections::VecDeque;

/// Basic front/back operations
fn basic_deque() {
    let mut dq = VecDeque::new();
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_front(0);

    assert_eq!(dq.pop_front(), Some(0));
    assert_eq!(dq.pop_front(), Some(1));
    assert_eq!(dq.pop_back(), Some(3));
    assert_eq!(dq.pop_back(), Some(2));
    assert!(dq.is_empty());
}

/// Rotation using VecDeque::rotate_left/rotate_right
fn rotation() {
    let mut dq: VecDeque<_> = [1, 2, 3, 4, 5].into_iter().collect();

    // Rotate left by 2: [3, 4, 5, 1, 2]
    dq.rotate_left(2);
    assert_eq!(dq, [3, 4, 5, 1, 2].into_iter().collect::<VecDeque<_>>());

    // Rotate right by 2: back to [1, 2, 3, 4, 5]
    dq.rotate_right(2);
    assert_eq!(dq, [1, 2, 3, 4, 5].into_iter().collect::<VecDeque<_>>());
}

/// Using VecDeque as a sliding window
fn sliding_window() {
    let data = vec![1, 2, 3, 4, 5, 6, 7];
    let window_size = 3;
    let mut window: VecDeque<i32> = VecDeque::with_capacity(window_size);
    let mut sums = Vec::new();

    for &val in &data {
        window.push_back(val);
        if window.len() > window_size {
            window.pop_front();
        }
        if window.len() == window_size {
            let sum: i32 = window.iter().sum();
            sums.push(sum);
        }
    }

    assert_eq!(sums, vec![6, 9, 12, 15, 18]); // 1+2+3, 2+3+4, ...
}

/// VecDeque to Vec and back
fn conversions() {
    let v = vec![1, 2, 3, 4, 5];
    let mut dq: VecDeque<_> = v.into_iter().collect();

    dq.push_front(0);
    // make_contiguous ensures internal buffer is contiguous
    dq.make_contiguous();

    let v: Vec<_> = dq.into_iter().collect();
    assert_eq!(v, vec![0, 1, 2, 3, 4, 5]);
}

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

    #[test]
    fn test_basic_deque() {
        basic_deque();
    }

    #[test]
    fn test_rotation() {
        rotation();
    }

    #[test]
    fn test_sliding_window() {
        sliding_window();
    }

    #[test]
    fn test_conversions() {
        conversions();
    }

    #[test]
    fn test_indexed_access() {
        let dq: VecDeque<_> = [10, 20, 30].into_iter().collect();
        assert_eq!(dq[0], 10);
        assert_eq!(dq[1], 20);
        assert_eq!(dq[2], 30);
    }
}

(* 1032: VecDeque Rotation — Efficient Front/Back Operations *)
(* OCaml uses lists (efficient at front) or Queue module *)

(* Approach 1: List as a deque — efficient front, O(n) back *)
let list_deque () =
  let q = [1; 2; 3; 4; 5] in
  (* Push front: O(1) *)
  let q = 0 :: q in
  assert (q = [0; 1; 2; 3; 4; 5]);
  (* Pop front: O(1) *)
  let (front, q) = (List.hd q, List.tl q) in
  assert (front = 0);
  assert (q = [1; 2; 3; 4; 5]);
  (* Push back: O(n) *)
  let q = q @ [6] in
  assert (q = [1; 2; 3; 4; 5; 6])

(* Approach 2: Two-list queue for amortized O(1) both ends *)
type 'a deque = { front: 'a list; back: 'a list }

let empty = { front = []; back = [] }
let push_front x d = { d with front = x :: d.front }
let push_back x d = { d with back = x :: d.back }

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

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

let two_list_deque () =
  let d = empty in
  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
  let (v, d) = Option.get (pop_front d) in
  assert (v = 0);
  let (v, d) = Option.get (pop_front d) in
  assert (v = 1);
  let (v, _d) = Option.get (pop_back d) in
  assert (v = 3)

(* Approach 3: Rotation *)
let rotate_left lst n =
  let len = List.length lst in
  let n = n mod len in
  let rec take_drop i = function
    | [] -> ([], [])
    | x :: xs when i > 0 ->
      let (taken, rest) = take_drop (i - 1) xs in
      (x :: taken, rest)
    | xs -> ([], xs)
  in
  let (front, back) = take_drop n lst in
  back @ front

let rotation_test () =
  let lst = [1; 2; 3; 4; 5] in
  assert (rotate_left lst 2 = [3; 4; 5; 1; 2]);
  assert (rotate_left lst 0 = [1; 2; 3; 4; 5])

let () =
  list_deque ();
  two_list_deque ();
  rotation_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_basic_deque() {
        basic_deque();
    }

    #[test]
    fn test_rotation() {
        rotation();
    }

    #[test]
    fn test_sliding_window() {
        sliding_window();
    }

    #[test]
    fn test_conversions() {
        conversions();
    }

    #[test]
    fn test_indexed_access() {
        let dq: VecDeque<_> = [10, 20, 30].into_iter().collect();
        assert_eq!(dq[0], 10);
        assert_eq!(dq[1], 20);
        assert_eq!(dq[2], 30);
    }
}

Deep Comparison

VecDeque Rotation — Comparison

Core Insight

Rust provides a purpose-built ring buffer (VecDeque) with O(1) operations at both ends and built-in rotation. OCaml's standard library lacks this; the common workaround is a two-list queue (amortized O(1)) or a simple list (O(1) front, O(n) back).

OCaml Approach

• List: O(1) push/pop front, O(n) back operations

• Two-list deque: { front; back } with lazy reversal for amortized O(1)

• Manual rotation: split list at index, append halves

• Queue module exists but is mutable and not a deque

Rust Approach

• VecDeque<T>: ring buffer backed by contiguous array

• O(1) push_front, push_back, pop_front, pop_back

• rotate_left(n) / rotate_right(n): built-in rotation

• Indexed access via dq[i]

• make_contiguous() to linearize internal buffer

• Excellent for sliding windows

Comparison Table

Feature	OCaml (list/two-list)	Rust (`VecDeque`)
Push front	O(1)	O(1)
Push back	O(n) list / amortized O(1)	O(1)
Pop front	O(1)	O(1)
Pop back	O(n) list / amortized O(1)	O(1)
Rotation	Manual O(n)	Built-in O(n)
Random access	O(n)	O(1)
Memory layout	Linked nodes	Contiguous ring buffer
Cache friendly	No	Yes

Exercises

Implement a RateLimiter that tracks requests using a VecDeque<Instant>, sliding the window to count requests in the last N seconds.

Write rotate_string(s: &str, k: usize) -> String using VecDeque<char> to rotate a string's characters.

Implement a fixed-capacity circular log buffer CircularLog<T> backed by VecDeque<T> that keeps only the last N entries.

Open Source Repos

functional-rust

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

Rust