I Stopped Reaching for Stack and Queue in Rust. Here Is What I Use Instead

Part of the Data Structures in Rust series.

After the linked list article, where the borrow checker fought every design decision, and the binary tree article, where ownership turned out to fit the structure naturally, I expected the stack and queue to land somewhere in the middle. They did not. The stack was almost insultingly easy. The queue started easy and then revealed a performance trap that the standard library quietly solves for you.

The real lesson from both data structures is not about ownership or lifetimes. It is about what Rust’s ownership model implicitly encourages through performance characteristics, and why Vec ends up being the right answer for both unless you have a very specific reason to do otherwise.

The stack
A stack is LIFO: last in, first out. Push something on, pop it off, peek at the top without removing it. The whole thing in Rust:

pub struct Stack<T> {
    elements: Vec<T>,
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { elements: Vec::new() }
    }
    pub fn push(&mut self, item: T) {
        self.elements.push(item);
    }
    pub fn pop(&mut self) -> Option<T> {
        self.elements.pop()
    }
    pub fn peek(&self) -> Option<&T> {
        self.elements.last()
    }
    pub fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
    pub fn size(&self) -> usize {
        self.elements.len()
    }
}

That is the entire implementation. Push appends to the end of the Vec. Pop removes from the end. Both are O(1) amortised. Peek borrows the last element immutably. There is no interesting ownership story here because Vec already owns its elements, and adding or removing from the end never requires touching anything else in the allocation.

The test suite to verify it behaves correctly:

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


#[test]
    fn push_and_pop() {
        let mut stack = Stack::new();
        stack.push(1);
        stack.push(2);
        stack.push(3);

Continue reading on Systems Engineering Notes »