Custom Stack and Queue

Building a custom MinStack<T> and a custom circular-buffer RingQueue<T> from scratch demonstrates how to maintain auxiliary $O(1)$ aggregate invariants alongside LIFO/FIFO operations and how to manage uninitialized circular buffer slots safely with MaybeUninit<T>.

1. `MinStack<T>` (O(1) `push`, `pop`, `top`, AND `min`!):
   Each entry stores `(value, current_stack_minimum)`:
   Push 30 -> [ (30, min: 30) ]
   Push 10 -> [ (30, min: 30), (10, min: 10) ]
   Push 20 -> [ (30, min: 30), (10, min: 10), (20, min: 10) ]

2. `RingQueue<T, CAP>` (Fixed-Capacity Circular Queue with `head`, `tail`, `len`):
   Index:   0      1      2      3
          +------+------+------+------+
          |  B   |  C   |  .   |  A   |   `head = 3`, `len = 3`
          +------+------+------+------+   `tail = (head + len) % CAP = 2`

1. $O(1)$ Minimum-Tracking Stack (MinStack<T>)

A standard stack finds its minimum element in $O(n)$ time by scanning all elements. By storing each element alongside the minimum value at or below that stack depth, MinStack<T> answers .min() in $O(1)$ time even as elements are pushed and popped!

2. Fixed-Capacity Circular Queue (RingQueue<T, CAP>)

Using modular index arithmetic (self.head + self.len) % CAP inside a fixed-capacity array [Option<T>; CAP] implements a zero-heap-allocation FIFO queue with $O(1)$ enqueue and dequeue:

/// 1. LIFO Stack that answers `.min()` in O(1) worst-case time!
#[derive(Debug, Default)]
pub struct MinStack<T> {
    // Stores `(element, min_up_to_this_depth)`
    entries: Vec<(T, T)>,
}

impl<T: Ord + Clone> MinStack<T> {
    pub const fn new() -> Self {
        Self {
            entries: Vec::new(),
        }
    }

    pub fn push(&mut self, value: T) {
        let new_min = match self.entries.last() {
            Some((_, cur_min)) if *cur_min < value => cur_min.clone(),
            _ => value.clone(),
        };
        self.entries.push((value, new_min));
    }

    pub fn pop(&mut self) -> Option<T> {
        self.entries.pop().map(|(val, _)| val)
    }

    pub fn top(&self) -> Option<&T> {
        self.entries.last().map(|(val, _)| val)
    }

    /// Returns the smallest element currently in the stack in O(1) time!
    pub fn min(&self) -> Option<&T> {
        self.entries.last().map(|(_, cur_min)| cur_min)
    }
}

/// 2. Fixed-capacity circular FIFO Queue backed by an inline array (`0` heap allocations!).
pub struct RingQueue<T, const CAP: usize> {
    slots: [Option<T>; CAP],
    head: usize,
    len: usize,
}

impl<T, const CAP: usize> RingQueue<T, CAP> {
    pub const fn new() -> Self {
        const {
            assert!(CAP > 0, "RingQueue capacity must be > 0");
        }
        Self {
            slots: [const { None }; CAP],
            head: 0,
            len: 0,
        }
    }

    pub fn enqueue(&mut self, item: T) -> Result<(), T> {
        if self.len == CAP {
            return Err(item); // Queue is full; return ownership of `item` to caller
        }
        let tail = (self.head + self.len) % CAP;
        self.slots[tail] = Some(item);
        self.len += 1;
        Ok(())
    }

    pub fn dequeue(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }
        let item = self.slots[self.head].take();
        self.head = (self.head + 1) % CAP;
        self.len -= 1;
        item
    }

    pub fn peek(&self) -> Option<&T> {
        if self.len == 0 {
            None
        } else {
            self.slots[self.head].as_ref()
        }
    }

    pub const fn len(&self) -> usize {
        self.len
    }

    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }
}

fn main() {
    // 1. Verify O(1) MinStack:
    let mut stack = MinStack::new();
    stack.push(30);
    stack.push(10);
    stack.push(20);
    stack.push(5);

    assert_eq!(stack.min(), Some(&5));
    assert_eq!(stack.pop(), Some(5));
    assert_eq!(stack.min(), Some(&10));
    println!("MinStack after popping 5: top={:?}, min={:?}", stack.top(), stack.min());

    // 2. Verify wrap-around in RingQueue<_, 3>:
    let mut queue = RingQueue::<&str, 3>::new();
    queue.enqueue("job_1").unwrap();
    queue.enqueue("job_2").unwrap();
    queue.enqueue("job_3").unwrap();
    assert_eq!(queue.enqueue("overflow"), Err("overflow"));

    assert_eq!(queue.dequeue(), Some("job_1"));
    // Enqueueing "job_4" wraps around to physical slot 0!
    queue.enqueue("job_4").unwrap();

    let drained = [queue.dequeue(), queue.dequeue(), queue.dequeue()];
    assert_eq!(drained, [Some("job_2"), Some("job_3"), Some("job_4")]);
    println!("RingQueue wrapped and drained in FIFO order: {drained:?}");
}

MinStack after popping 5: top=Some(20), min=Some(10)
RingQueue wrapped and drained in FIFO order: [Some("job_2"), Some("job_3"), Some("job_4")]