1039 Intermediate

1039-stack-via-vec — Stack Using Vec

Functional Programming

Tutorial

The Problem

A stack (LIFO — last in, first out) is one of the most fundamental data structures: it underlies function call frames, expression evaluation, undo history, and DFS traversal. Implementing a stack efficiently requires O(1) push and pop at one end.

Rust's Vec<T> provides exactly this: push appends to the end (O(1) amortized) and pop removes from the end (O(1)). The back of a Vec is the top of the stack. No additional data structure is needed — Vec IS a stack.

🎯 Learning Outcomes

• Understand that Vec::push and Vec::pop implement a LIFO stack

• Wrap Vec in a newtype to provide a cleaner stack API

• Implement stack-based algorithms: balanced parentheses, expression evaluation

• Understand O(1) amortized push and O(1) pop complexity

• Compare Vec-based stacks to linked-list stacks

Code Example

#![allow(clippy::all)]
// 1039: Stack Using Vec
// Vec's push/pop operate at the end — perfect LIFO stack

/// A simple stack wrapper around Vec
struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, value: T) {
        self.items.push(value);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    fn size(&self) -> usize {
        self.items.len()
    }
}

fn basic_stack() {
    let mut s = Stack::new();
    assert!(s.is_empty());

    s.push(10);
    s.push(20);
    s.push(30);

    assert_eq!(s.size(), 3);
    assert_eq!(s.peek(), Some(&30));
    assert_eq!(s.pop(), Some(30));
    assert_eq!(s.pop(), Some(20));
    assert_eq!(s.pop(), Some(10));
    assert_eq!(s.pop(), None);
}

/// Vec directly as a stack (no wrapper needed)
fn vec_as_stack() {
    let mut stack: Vec<i32> = Vec::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);

    assert_eq!(stack.last(), Some(&3));
    assert_eq!(stack.pop(), Some(3));
    assert_eq!(stack.len(), 2);
}

/// RPN (Reverse Polish Notation) calculator using a stack
fn eval_rpn(tokens: &[&str]) -> i32 {
    let mut stack: Vec<i32> = Vec::new();

    for &token in tokens {
        match token {
            "+" | "-" | "*" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                let result = match token {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    _ => unreachable!(),
                };
                stack.push(result);
            }
            n => stack.push(n.parse().unwrap()),
        }
    }

    stack.pop().unwrap()
}

fn eval_test() {
    // 3 4 + 2 * = (3 + 4) * 2 = 14
    assert_eq!(eval_rpn(&["3", "4", "+", "2", "*"]), 14);
    // 5 1 2 + 4 * + 3 - = 5 + (1+2)*4 - 3 = 14
    assert_eq!(eval_rpn(&["5", "1", "2", "+", "4", "*", "+", "3", "-"]), 14);
}

/// Balanced parentheses checker
fn is_balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    for ch in s.chars() {
        match ch {
            '(' | '[' | '{' => stack.push(ch),
            ')' => {
                if stack.pop() != Some('(') {
                    return false;
                }
            }
            ']' => {
                if stack.pop() != Some('[') {
                    return false;
                }
            }
            '}' => {
                if stack.pop() != Some('{') {
                    return false;
                }
            }
            _ => {}
        }
    }
    stack.is_empty()
}

fn balance_test() {
    assert!(is_balanced("({[]})"));
    assert!(is_balanced(""));
    assert!(!is_balanced("({[})"));
    assert!(!is_balanced("(("));
}

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

    #[test]
    fn test_basic() {
        basic_stack();
    }

    #[test]
    fn test_vec_stack() {
        vec_as_stack();
    }

    #[test]
    fn test_rpn() {
        eval_test();
    }

    #[test]
    fn test_balanced() {
        balance_test();
    }
}

(* 1039: Stack Using List *)
(* OCaml's list IS a stack — cons and pattern match are push and pop *)

(* Approach 1: List as a stack (idiomatic OCaml) *)
let list_stack () =
  let stack = [] in
  let stack = 1 :: stack in
  let stack = 2 :: stack in
  let stack = 3 :: stack in
  assert (List.hd stack = 3);  (* top *)
  let (top, stack) = (List.hd stack, List.tl stack) in
  assert (top = 3);
  assert (List.hd stack = 2)

(* Approach 2: Module-based stack *)
module Stack : sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> ('a * 'a t) option
  val peek : 'a t -> 'a option
  val is_empty : 'a t -> bool
  val size : 'a t -> int
  val to_list : 'a t -> 'a list
end = struct
  type 'a t = { items: 'a list; size: int }

  let empty = { items = []; size = 0 }
  let push x s = { items = x :: s.items; size = s.size + 1 }
  let pop s = match s.items with
    | [] -> None
    | x :: xs -> Some (x, { items = xs; size = s.size - 1 })
  let peek s = match s.items with
    | [] -> None
    | x :: _ -> Some x
  let is_empty s = s.items = []
  let size s = s.size
  let to_list s = s.items
end

let module_stack () =
  let s = Stack.empty in
  let s = Stack.push 10 s in
  let s = Stack.push 20 s in
  let s = Stack.push 30 s in
  assert (Stack.size s = 3);
  assert (Stack.peek s = Some 30);
  let (v, s) = Option.get (Stack.pop s) in
  assert (v = 30);
  assert (Stack.peek s = Some 20)

(* Approach 3: Stack-based expression evaluator *)
let eval_rpn tokens =
  let stack = List.fold_left (fun stack token ->
    match token with
    | "+" | "-" | "*" ->
      let b = List.hd stack in
      let a = List.hd (List.tl stack) in
      let rest = List.tl (List.tl stack) in
      let result = match token with
        | "+" -> a + b
        | "-" -> a - b
        | "*" -> a * b
        | _ -> failwith "impossible"
      in
      result :: rest
    | n -> int_of_string n :: stack
  ) [] tokens in
  List.hd stack

let eval_test () =
  (* 3 4 + 2 * = (3 + 4) * 2 = 14 *)
  let result = eval_rpn ["3"; "4"; "+"; "2"; "*"] in
  assert (result = 14)

let () =
  list_stack ();
  module_stack ();
  eval_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Underlying structure: Rust uses Vec (contiguous memory, O(1) amortized push); OCaml's Stack uses a linked list (O(1) push, but pointer-chasing).

Functional vs imperative: OCaml's list-as-stack is immutable and functional; Rust's Vec-as-stack is mutable and imperative.

Peek without pop: Rust's Vec::last() peeks without popping; OCaml's list head is accessible without modification.

Memory: Rust's Vec grows in chunks (amortized O(1)); OCaml's linked list allocates one cons cell per push.

OCaml Approach

OCaml's Stack module provides a mutable stack backed by a linked list. The functional alternative is just a list:

(* Functional stack: list is a stack *)
let push value stack = value :: stack
let pop = function [] -> None | x :: rest -> Some (x, rest)
let peek = function [] -> None | x :: _ -> Some x

OCaml's built-in Stack module uses a linked list, so each push allocates a new cons cell. Rust's Vec uses amortized-O(1) heap reallocation, which is cache-friendlier.

Full Source

#![allow(clippy::all)]
// 1039: Stack Using Vec
// Vec's push/pop operate at the end — perfect LIFO stack

/// A simple stack wrapper around Vec
struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, value: T) {
        self.items.push(value);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    fn size(&self) -> usize {
        self.items.len()
    }
}

fn basic_stack() {
    let mut s = Stack::new();
    assert!(s.is_empty());

    s.push(10);
    s.push(20);
    s.push(30);

    assert_eq!(s.size(), 3);
    assert_eq!(s.peek(), Some(&30));
    assert_eq!(s.pop(), Some(30));
    assert_eq!(s.pop(), Some(20));
    assert_eq!(s.pop(), Some(10));
    assert_eq!(s.pop(), None);
}

/// Vec directly as a stack (no wrapper needed)
fn vec_as_stack() {
    let mut stack: Vec<i32> = Vec::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);

    assert_eq!(stack.last(), Some(&3));
    assert_eq!(stack.pop(), Some(3));
    assert_eq!(stack.len(), 2);
}

/// RPN (Reverse Polish Notation) calculator using a stack
fn eval_rpn(tokens: &[&str]) -> i32 {
    let mut stack: Vec<i32> = Vec::new();

    for &token in tokens {
        match token {
            "+" | "-" | "*" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                let result = match token {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    _ => unreachable!(),
                };
                stack.push(result);
            }
            n => stack.push(n.parse().unwrap()),
        }
    }

    stack.pop().unwrap()
}

fn eval_test() {
    // 3 4 + 2 * = (3 + 4) * 2 = 14
    assert_eq!(eval_rpn(&["3", "4", "+", "2", "*"]), 14);
    // 5 1 2 + 4 * + 3 - = 5 + (1+2)*4 - 3 = 14
    assert_eq!(eval_rpn(&["5", "1", "2", "+", "4", "*", "+", "3", "-"]), 14);
}

/// Balanced parentheses checker
fn is_balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    for ch in s.chars() {
        match ch {
            '(' | '[' | '{' => stack.push(ch),
            ')' => {
                if stack.pop() != Some('(') {
                    return false;
                }
            }
            ']' => {
                if stack.pop() != Some('[') {
                    return false;
                }
            }
            '}' => {
                if stack.pop() != Some('{') {
                    return false;
                }
            }
            _ => {}
        }
    }
    stack.is_empty()
}

fn balance_test() {
    assert!(is_balanced("({[]})"));
    assert!(is_balanced(""));
    assert!(!is_balanced("({[})"));
    assert!(!is_balanced("(("));
}

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

    #[test]
    fn test_basic() {
        basic_stack();
    }

    #[test]
    fn test_vec_stack() {
        vec_as_stack();
    }

    #[test]
    fn test_rpn() {
        eval_test();
    }

    #[test]
    fn test_balanced() {
        balance_test();
    }
}

(* 1039: Stack Using List *)
(* OCaml's list IS a stack — cons and pattern match are push and pop *)

(* Approach 1: List as a stack (idiomatic OCaml) *)
let list_stack () =
  let stack = [] in
  let stack = 1 :: stack in
  let stack = 2 :: stack in
  let stack = 3 :: stack in
  assert (List.hd stack = 3);  (* top *)
  let (top, stack) = (List.hd stack, List.tl stack) in
  assert (top = 3);
  assert (List.hd stack = 2)

(* Approach 2: Module-based stack *)
module Stack : sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> ('a * 'a t) option
  val peek : 'a t -> 'a option
  val is_empty : 'a t -> bool
  val size : 'a t -> int
  val to_list : 'a t -> 'a list
end = struct
  type 'a t = { items: 'a list; size: int }

  let empty = { items = []; size = 0 }
  let push x s = { items = x :: s.items; size = s.size + 1 }
  let pop s = match s.items with
    | [] -> None
    | x :: xs -> Some (x, { items = xs; size = s.size - 1 })
  let peek s = match s.items with
    | [] -> None
    | x :: _ -> Some x
  let is_empty s = s.items = []
  let size s = s.size
  let to_list s = s.items
end

let module_stack () =
  let s = Stack.empty in
  let s = Stack.push 10 s in
  let s = Stack.push 20 s in
  let s = Stack.push 30 s in
  assert (Stack.size s = 3);
  assert (Stack.peek s = Some 30);
  let (v, s) = Option.get (Stack.pop s) in
  assert (v = 30);
  assert (Stack.peek s = Some 20)

(* Approach 3: Stack-based expression evaluator *)
let eval_rpn tokens =
  let stack = List.fold_left (fun stack token ->
    match token with
    | "+" | "-" | "*" ->
      let b = List.hd stack in
      let a = List.hd (List.tl stack) in
      let rest = List.tl (List.tl stack) in
      let result = match token with
        | "+" -> a + b
        | "-" -> a - b
        | "*" -> a * b
        | _ -> failwith "impossible"
      in
      result :: rest
    | n -> int_of_string n :: stack
  ) [] tokens in
  List.hd stack

let eval_test () =
  (* 3 4 + 2 * = (3 + 4) * 2 = 14 *)
  let result = eval_rpn ["3"; "4"; "+"; "2"; "*"] in
  assert (result = 14)

let () =
  list_stack ();
  module_stack ();
  eval_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_basic() {
        basic_stack();
    }

    #[test]
    fn test_vec_stack() {
        vec_as_stack();
    }

    #[test]
    fn test_rpn() {
        eval_test();
    }

    #[test]
    fn test_balanced() {
        balance_test();
    }
}

Deep Comparison

Stack Using Vec — Comparison

Core Insight

A stack is the simplest data structure, and both languages have a natural fit. OCaml's list is literally a stack (cons cells). Rust's Vec has push/pop at the end, which is amortized O(1) and contiguous in memory.

OCaml Approach

• List IS a stack: x :: xs = push, List.hd = peek, List.tl = pop

• Immutable — each push creates a new cons cell

• Module-based wrapper for cleaner API

• Pattern matching for safe pop/peek

Rust Approach

• Vec<T> with push/pop/last — no wrapper needed

• Mutable, amortized O(1) operations

• pop() returns Option<T> for safe empty handling

• Wrapper struct adds type safety if desired

Comparison Table

Feature	OCaml (list)	Rust (`Vec`)
Push	`x :: xs` O(1)	`push(x)` amortized O(1)
Pop	Pattern match O(1)	`pop()` → `Option<T>` O(1)
Peek	`List.hd` / pattern match	`last()` → `Option<&T>`
Memory	Linked cons cells	Contiguous array
Mutability	Immutable	Mutable
Cache friendly	No	Yes
Wrapper needed	Optional	Optional

Exercises

Implement a min_stack that tracks the current minimum in O(1) by maintaining a parallel stack of minimums.

Write a evaluate_rpn(tokens: &[&str]) -> Result<i64, String> function that evaluates a Reverse Polish Notation expression using a Stack<i64>.

Implement is_balanced_parens(s: &str) -> bool that handles (), [], and {} using the stack.

Open Source Repos

functional-rust

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

Rust