栈 Stack（LIFO）+ Rust

宝贝～栈是考研 DS 的“顶流考点”之一：括号匹配、表达式求值、DFS/回溯、单调栈，全靠它。

1. 栈的考点

• 特性：后进先出（LIFO）
• 基本操作：push / pop / top
• 复杂度：都应为 O(1)

2. Rust 用 Vec 做栈（最常用）

#[derive(Default)]
struct Stack<T> {
    a: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self { Self { a: Vec::new() } }
    fn push(&mut self, x: T) { self.a.push(x) }
    fn pop(&mut self) -> Option<T> { self.a.pop() }
    fn top(&self) -> Option<&T> { self.a.last() }
    fn is_empty(&self) -> bool { self.a.is_empty() }
}

3. 经典题：括号匹配

pub fn is_valid(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()
}

4. 单调栈（考研/408 都常见）

用途：

• 下一个更大元素
• 柱状图最大矩形

模板（存下标）：

// 维护一个“单调递减”栈：栈顶最小
let mut st: Vec<usize> = Vec::new();
for i in 0..n {
    while let Some(&j) = st.last() {
        if a[j] <= a[i] { break; }
        st.pop();
    }
    st.push(i);
}

宝贝把“括号匹配”这题自己手写一遍发我～老师给你挑小细节（比如 char/bytes 的效率写法）。