Rust顺序栈实现（从零开始掌握Rust栈数据结构）

什么是顺序栈？

顺序栈是使用连续内存空间（如数组或 Vec）实现的栈。与链式栈不同，顺序栈的元素在内存中是连续存储的，访问效率高，但容量通常需要预先设定（不过 Rust 的 Vec 可以动态扩容，因此我们能兼顾灵活性和性能）。

Rust 中实现顺序栈的关键点

• 使用 Vec<T> 作为底层存储
• 提供 push（入栈）、pop（出栈）、peek（查看栈顶）、is_empty（判空）等方法
• 利用 Rust 的所有权和借用机制保证内存安全

完整代码实现

下面是一个完整的 Rust顺序栈实现 示例：

// 定义顺序栈结构体struct SequentialStack<T> {    data: Vec<T>,}// 为 SequentialStack 实现方法impl<T> SequentialStack<T> {    // 创建一个新的空栈    fn new() -> Self {        SequentialStack { data: Vec::new() }    }    // 入栈操作    fn push(&mut self, item: T) {        self.data.push(item);    }    // 出栈操作，返回 Option<T>    fn pop(&mut self) -> Option<T> {        self.data.pop()    }    // 查看栈顶元素，不移除    fn peek(&self) -> Option<&T> {        self.data.last()    }    // 判断栈是否为空    fn is_empty(&self) -> bool {        self.data.is_empty()    }    // 获取栈的大小    fn size(&self) -> usize {        self.data.len()    }}// 使用示例fn main() {    let mut stack = SequentialStack::new();    // 入栈    stack.push(10);    stack.push(20);    stack.push(30);    println!("栈顶元素: {:?}", stack.peek()); // Some(30)    println!("栈大小: {}", stack.size());      // 3    // 出栈    println!("出栈: {:?}", stack.pop());       // Some(30)    println!("出栈: {:?}", stack.pop());       // Some(20)    println!("是否为空: {}", stack.is_empty()); // false}

代码详解

让我们逐部分解析这段 Rust编程教程 中的核心代码：

• SequentialStack<T>：这是一个泛型结构体，可以存储任意类型 T 的数据。
• new()：构造函数，返回一个空栈。
• push(&mut self, item: T)：将元素压入栈顶。注意这里需要可变引用 &mut self，因为要修改内部数据。
• pop()：弹出栈顶元素。Rust 的 Vec::pop() 返回 Option<T>，避免空栈崩溃，符合 Rust 的安全哲学。
• peek()：只读取栈顶元素，不修改栈，因此使用不可变引用 &self。

为什么选择 Vec 而不是数组？

在 Rust 中，固定大小的数组（如 [i32; 5]）虽然内存连续，但大小不可变。而 Vec<T> 是堆分配的动态数组，既能保证顺序存储，又能自动扩容，非常适合实现灵活的顺序栈代码示例。

小结

通过本教程，你已经学会了如何用 Rust 实现一个功能完整的顺序栈。这个实现充分利用了 Rust 的内存安全特性和泛型系统，既安全又高效。无论你是准备面试，还是深入学习 Rust栈数据结构，这个例子都是一个很好的起点。

提示：你可以尝试扩展这个栈，比如添加最大容量限制、实现迭代器，或者用于解决括号匹配、表达式求值等经典问题！