Stacks in Rust

Think of a pile of plates in the canteen. You put a clean plate on top, and when someone needs one, they take the top plate. Nobody pulls from the middle, because the whole pile would wobble.

That is a stack. It is a collection where you can only add to the top and only take from the top. The item you added most recently is the first one you get back. This rule is called LIFO, short for "last in, first out".

Reach for a stack whenever the most recent thing is the one you need next, or whenever you need to remember what to come back to. Everyday examples are the undo button in an editor, the back button in a browser, and checking that brackets in code are closed in the right order. Your own program uses one too: the call stack, which remembers where each running function should return to.

A stack has three moves, and all of them work on the top.

• Push puts a new value on top.
• Pop takes the top value off and gives it to you.
• Peek shows you the top value without taking it.

If a stack is empty, there is nothing to pop or peek at. In Rust the honest way to say that is to return None instead of crashing, so pop and peek give back an Option.

Because every move happens at one end, each is one step, however many items are in the stack. That is what makes a stack so cheap to use.

Remember: a stack only lets you touch the top. That limit is what keeps it simple and quick.

A Vec already stores items in a row and grows at the end. A stack only needs that end, so the simplest stack is a Vec wrapped in a new type that exposes only the stack moves.

/// A stack of values: the last one in is the first one out.
/// It wraps a `Vec` and only lets you touch the end.
pub struct Stack<T> {
    items: Vec<T>,
}

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

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

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

    /// Puts a value on top.
    pub fn push(&mut self, value: T) {
        self.items.push(value);
    }

    /// Takes the top value off, or gives `None` if the stack is empty.
    pub fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    /// Looks at the top value without taking it.
    pub fn peek(&self) -> Option<&T> {
        self.items.last()
    }
}

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

Go through it in order.

• Stack<T> is generic. The T is a placeholder for any type, so one definition gives you a stack of numbers, of strings, or of anything else. The type is filled in when you use it, as in Stack<i32>.
• The field items is private, because there is no pub on it. Code outside can't reach in and change the middle, so the stack rule can't be broken from the outside.
• push adds to the end of the Vec. The end of the Vec is the top of the stack.
• pop returns Option<T>, which is Some(value) or None when empty. It hands the value over, so the caller now owns it.
• peek returns Option<&T>, a borrowed look at the top. The stack keeps ownership, and the caller can read the value without taking it.

Try it in the Playground. The block above has a main ready.

Rust has no separate stack type, because Vec does the job. Its end is the top.

let mut stack = Vec::new();
stack.push(1);
stack.push(2);
stack.push(3);

assert_eq!(stack.last(), Some(&3)); // peek
assert_eq!(stack.pop(), Some(3)); // pop
assert_eq!(stack, [1, 2]);
assert_eq!(stack.len(), 2);

push and pop are the same names. last() is peek: it returns an Option<&T>. Wrapping the Vec, as we did above, is worth doing when you want the type itself to enforce the rule, so nobody can insert in the middle. For a quick tool inside one function, a plain Vec is the usual choice.

Because a stack gives back the newest item first, it reverses things:

let word = "stack";
let mut stack: Vec<char> = word.chars().collect();

let mut reversed = String::new();
while let Some(c) = stack.pop() {
    reversed.push(c);
}

println!("{reversed}");
assert_eq!(reversed, "kcats");

while let Some(c) = stack.pop() is the standard way to empty a stack. It runs for as long as pop returns Some, and stops when the stack is empty.

Sometimes you want to change the top item without removing it. last_mut() gives a mutable borrow of it:

let mut stack = vec![10, 20, 30];
if let Some(top) = stack.last_mut() {
    *top += 1; // change the top in place, without popping it
}
assert_eq!(stack, [10, 20, 31]);

The *top += 1 writes through the reference to change the value in place.

Every move that a stack allows is cheap. The price of that is what you give up: a stack has no quick way to find something in the middle.

In all three, the stack holds things that are still waiting: an opener waiting for its closer, a number waiting for its operator, a day waiting for a warmer day. When something arrives that settles the newest waiting item, you pop it.

pub fn is_balanced(text: &str) -> bool {
    todo!("every closing bracket must match the latest unclosed opener")
}

pub fn is_balanced(text: &str) -> bool {
    let mut expected = Vec::new(); // the closers we are still waiting for
    for c in text.chars() {
        match c {
            '(' => expected.push(')'),
            '[' => expected.push(']'),
            '{' => expected.push('}'),
            ')' | ']' | '}' => {
                if expected.pop() != Some(c) {
                    return false;
                }
            }
            _ => {} // any other character is ignored
        }
    }
    expected.is_empty()
}

pub fn eval_rpn(tokens: &[&str]) -> Option<i64> {
    todo!("numbers go on a stack; an operator combines the top two")
}

pub fn eval_rpn(tokens: &[&str]) -> Option<i64> {
    let mut stack: Vec<i64> = Vec::new();
    for &token in tokens {
        match token {
            "+" | "-" | "*" | "/" => {
                let right = stack.pop()?; // the second operand was pushed last
                let left = stack.pop()?;
                let result = match token {
                    "+" => left.checked_add(right)?,
                    "-" => left.checked_sub(right)?,
                    "*" => left.checked_mul(right)?,
                    _ => left.checked_div(right)?, // None for division by zero
                };
                stack.push(result);
            }
            number => stack.push(number.parse().ok()?),
        }
    }
    // A valid expression leaves exactly one value behind.
    match stack.as_slice() {
        [answer] => Some(*answer),
        _ => None,
    }
}

pub fn days_until_warmer(temps: &[i32]) -> Vec<usize> {
    todo!("for each day, how many days until a warmer one (0 if never)")
}

pub fn days_until_warmer(temps: &[i32]) -> Vec<usize> {
    let mut answer = vec![0; temps.len()];
    let mut waiting: Vec<usize> = Vec::new(); // days still waiting for a warmer one
    for (today, &temp) in temps.iter().enumerate() {
        while let Some(&earlier) = waiting.last() {
            if temps[earlier] >= temp {
                break;
            }
            waiting.pop();
            answer[earlier] = today - earlier;
        }
        waiting.push(today);
    }
    answer
}

A stack is often the answer when a problem has things that nest or things that wait. A few habits help.

• Spot the signals. Matching pairs (brackets, tags), undoing the latest step, evaluating expressions, and "the next larger element to the right" all point to a stack.
• Know the monotonic stack. Problem 3 is the pattern behind a whole family of questions about the next bigger or smaller value. The surprise is that it is O(n): each item goes in once and comes out once.
• Decide what an empty pop means. Is it an error, or just "no answer"? Asking shows care, and in Rust it decides whether you return Option, Result, or panic.
• Think about recursion too. A recursive function uses the call stack. Many recursive solutions can be rewritten with your own stack, which avoids very deep calls. You will use this idea again for tree and graph traversal.
• Say the cost. "One pass, each item pushed and popped once, so O(n) time, and O(n) space for the stack in the worst case" is a complete answer.
• In Rust, say why Vec. Explaining that a Vec already gives O(1) push and pop at the end, so a separate stack type isn't needed, is the kind of answer that shows you know the standard library.

Made by VeraStack Labs