造轮子：手写 `Stack<T>`

本章目标

这一章开始真正造数据结构轮子。你会实现一个泛型栈 Stack<T>，理解后进先出、泛型、方法、所有权转移，以及为什么标准库的 Vec<T> 可以作为栈的底层存储。

它是什么

栈是一种后进先出结构：最后放进去的元素，最先被取出来。英文叫 Last In First Out，常缩写为 LIFO。

典型操作：

push：压入一个元素。
pop：弹出栈顶元素。
peek：查看栈顶但不取走。
is_empty：判断是否为空。

为什么需要

栈是理解数据结构 API 的好起点。它足够简单，又能覆盖很多 Rust 关键点：

T 表示泛型元素。
push 获取元素所有权。
pop 返回 Option<T>，因为空栈没有元素。
peek 返回 Option<&T>，因为只看不拿走。

这些设计背后都和所有权有关。

怎么使用

let mut stack = Stack::new();
stack.push(10);
stack.push(20);

assert_eq!(stack.peek(), Some(&20));
assert_eq!(stack.pop(), Some(20));
assert_eq!(stack.pop(), Some(10));
assert_eq!(stack.pop(), None);

pop 返回 None，不是 panic，因为空栈是正常情况。

逐行解释

struct Stack<T> {
    items: Vec<T>,
}

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

    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }
}

struct Stack<T> 定义一个泛型结构体，T 可以是任何类型。
items: Vec<T> 用动态数组保存元素。
impl<T> Stack<T> 给所有 T 的栈实现方法。
fn new() -> Self 创建空栈，Self 表示当前类型 Stack<T>。
&mut self 表示方法需要修改栈。
push(&mut self, item: T) 接收元素所有权并存入 Vec。
pop(&mut self) -> Option<T> 修改栈并可能返回一个元素。
self.items.pop() 直接复用标准库 Vec 的弹出能力。

常见坑

peek 不应该返回 Option<T>，否则查看一次就把元素拿走了。
push 不应该接收 &T，否则栈只保存引用，会引入生命周期问题。
空栈 pop 是正常状态，适合用 Option。
用 Vec 实现栈不是偷懒，而是复用可靠底层结构，重点放在 API 语义上。

练习

为 Stack<T> 添加 len(&self) -> usize。
添加 is_empty(&self) -> bool。
添加 peek(&self) -> Option<&T>。
写测试覆盖空栈、一个元素、多个元素。

造轮子任务

实现完整 Stack<T>，并用它检查括号是否匹配：输入 "([])" 返回 true，输入 "([)]" 返回 false。这个任务会让你看到栈在解析器里的真实用途。

小结

Stack<T> 小而完整：泛型表达元素类型，Vec<T> 提供存储，Option 表达空状态，方法签名表达所有权。学会它，你就开始从“会写语法”走向“会设计类型”。

造轮子：手写 Stack<T>