Chapter 28

Home

Stacks: Undo and Backtracking

A stack is like a stack of plates: you put plates on top, and you take plates off the top. Last In, First Out — LIFO. Stacks power undo, backtracking, and parsing throughout competitive programming.

The Stack Mentality

Three operations define a stack:

push(3) → top = 3 push(7) → top = 7 pop() → removes 7, top = 3 LIFO: Last In, First Out

C++ — std::stack

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;

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

    cout << st.top() << "\n";  // 30
    st.pop();                    // remove 30
    cout << st.top() << "\n";  // 20
    cout << st.size() << "\n"; // 2
    cout << st.empty() << "\n";// 0 (false)

    return 0;
}

pop() removes the top but doesn't return it. Check top() first.

Rust — Vec as stack

fn main() {
    let mut st: Vec<i32> = Vec::new();

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

    println!("{}", st.last().unwrap());      // 30
    st.pop();                                 // remove 30
    println!("{}", st.last().unwrap());       // 20
    println!("{}", st.len());                 // 2
    println!("{}", st.is_empty());            // false
}

Rust has no dedicated Stack type — Vec works perfectly as one.

Undo with a Stack

Every undo system is just a stack of previous states. When the user acts, push the current state. When they undo, pop the last state and restore it. 

// C++ — simple undo for a text buffer
string buffer;
stack<string> history;  // previous states

void type_char(char c) {
    history.push(buffer);  // save current
    buffer += c;
}

void undo() {
    if (!history.empty()) {
        buffer = history.top();
        history.pop();
    }
}

Checking Balanced Parentheses

A classic stack problem: given a string of ( ) [ ] { }, is it balanced? Push open brackets, pop on close brackets, check they match.

C++

bool is_balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return false;
            st.pop();
        }
    }
    return st.empty();
}

Rust

fn is_balanced(s: &str) -> bool {
    let mut st: Vec<char> = Vec::new();
    for c in s.chars() {
        match c {
            '(' | '[' | '{' => st.push(c),
            ')' => if st.pop() != Some('(') { return false; }
            ']' => if st.pop() != Some('[') { return false; }
            '}' => if st.pop() != Some('{') { return false; }
            _ => {}
        }
    }
    st.is_empty()
}

💡 Empty check matters

If you see a closing bracket but the stack is empty, there's nothing to match — the string is unbalanced. Always check st.empty() / st.is_empty() before popping.

🚨 Never pop from an empty stack in C++

Calling st.pop() on an empty stack in C++ is undefined behaviour. In Rust, st.pop() returns None safely — but you still need to handle it.

Key Takeaways

Practice