Step 1 of 6

Stacks with Vec

A stack is a collection where the last item you put in is the first one you take out: LIFO (last in, first out). Think of a pile of plates, the undo history of an editor, or the back button of a browser. Rust has no separate Stack type because Vec already is one:

All of these are O(1): they take the same time whether the stack holds ten items or ten million. (You'll meet this Big-O notation properly in the next module. For now: O(1) means "constant time", O(n) means "time grows in step with the number of items n".) They're fast because they only touch the end of the Vec; nothing else has to move.

fn main() {
    let mut undo: Vec<String> = Vec::new();
    undo.push(String::from("type 'Hello'"));
    undo.push(String::from("make bold"));
    undo.push(String::from("delete line 3"));

    println!("top: {:?}", undo.last());
    while let Some(action) = undo.pop() {
        println!("undo {action}");
    }
    println!("empty: {}", undo.is_empty());
    println!("{:?}", undo.pop());
}

top: Some("delete line 3")
undo delete line 3
undo make bold
undo type 'Hello'
empty: true
None

• pop returns an Option because the stack might be empty. while let Some(x) = stack.pop() is the idiomatic "take everything off" loop: it stops by itself at None.
• last() peeks without removing and gives a reference (Option<&String>); pop() hands you ownership of the value.

When a stack is the right tool

Whenever the most recent unfinished thing must be finished first: matching brackets, undo, evaluating expressions, walking a tree or a maze depth-first (the graphs module), and "what was the last thing bigger than this?" questions.

Brackets are the classic. Counting open brackets works for one kind: (() has an unclosed (. With several kinds, a counter is fooled by ([)]: two opened, two closed, yet the ) closes a [. A stack remembers which bracket is open most recently: push every opener, and every closer must match the opener on top.

Common mistakes

• Using the front of a Vec as the top. v.insert(0, x) and v.remove(0) shift every other element by one place: O(n) each time. The top of a Vec stack is always its end.
• stack.pop().unwrap() on a stack that can be empty. It panics with called `Option::unwrap()` on a `None` value. Handle None: for brackets, a closer with nothing open means the text is unbalanced.
• Forgetting what's left at the end. (( never fails a check while you scan it; the leftovers on the stack are what make it unbalanced.

Your task

Write fn is_balanced(code: &str) -> bool that returns true when every (, [ and { in code is closed by the matching ), ] or } in the right order. Ignore every other character. Use a Vec<char> as a stack. The tests include a text of 300,000 nested brackets, so the solution must be O(n): one pass over the characters.

Challenge 2

Write a calculator for Reverse Polish Notation (RPN), where the operator comes after its two operands: 3 4 + is 7, and 5 1 2 + 4 * + 3 - is 5 + (1 + 2) * 4 - 3 = 14. Old HP calculators and many stack-based virtual machines work this way.

Write fn eval_rpn(expr: &str) -> Option<i64>. Tokens are separated by spaces. A number is pushed; an operator +, -, * or / pops the top value b, then the next a, and pushes a op b (so 10 3 - is 7). Return None when the expression is malformed: an operator without two values, a token that isn't a number or operator, division by zero, or not exactly one value left at the end. Negative numbers like -3 are numbers, not operators.

Challenge 3

A weather service wants to know, for each day, how many days you have to wait for a warmer day. Write fn days_until_warmer(temps: &[i32]) -> Vec<usize>: result[i] is the number of days after day i until a strictly warmer temperature, or 0 if no warmer day comes.

For [73, 74, 75, 71, 69, 72, 76, 73] the answer is [1, 1, 4, 2, 1, 1, 0, 0].

Checking every later day for every day is O(n²), and the tests include 100,000 days. Use a monotonic stack instead: a Vec<usize> of the days still waiting for a warmer day. For each new day, pop every waiting day that is colder than today (today is their answer), then push today. Each day is pushed and popped at most once, so the whole thing is O(n).

Next: Queues with VecDeque