Rust 算法与数据结构：实用指南

引言：为什么 Rust 是算法和数据结构的理想选择

Rust 结合了 C/C++ 的性能与内存安全性，使其成为实现算法和数据结构的绝佳选择。得益于所有权（ownership）和借用（borrowing）系统，您可以在没有垃圾回收器的情况下创建高效且安全的结构。在本文中，我们将探讨在 Rust 中从栈到二叉树和图遍历的关键数据结构与算法的实际实现。

我们将仅使用 Rust 标准库，以便您可以立即在项目中使用这些代码。所有示例均可在 Rust 2021 edition 下编译和运行。

1. 栈和队列：Rust 中的经典数据结构

栈（Stack）

栈遵循后进先出（LIFO）原则。在 Rust 中，最简单的栈实现是基于 Vec：

struct Stack<T> {\n    elements: Vec<T>,\n}\n\nimpl<T> Stack<T> {\n    fn new() -> Self {\n        Stack { elements: Vec::new() }\n    }\n\n    fn push(&mut self, value: T) {\n        self.elements.push(value);\n    }\n\n    fn pop(&mut self) -> Option<T> {\n        self.elements.pop()\n    }\n\n    fn peek(&self) -> Option<&T> {\n        self.elements.last()\n    }\n\n    fn is_empty(&self) -> bool {\n        self.elements.is_empty()\n    }\n}\n\nfn main() {\n    let mut stack = Stack::new();\n    stack.push(10);\n    stack.push(20);\n    stack.push(30);\n    \n    println!("栈顶元素: {:?}", stack.peek()); // Some(30)\n    println!("弹出: {:?}", stack.pop()); // Some(30)\n    println!("栈为空? {}", stack.is_empty()); // false\n}

优势： Vec 已提供均摊 O(1) 的 push/pop 操作，而 Rust 保证内存在离开作用域时被释放。

队列（Queue）

队列遵循先进先出（FIFO）原则。为实现高效队列，我们使用标准库中的 VecDeque：

use std::collections::VecDeque;\n\nstruct Queue<T> {\n    elements: VecDeque<T>,\n}\n\nimpl<T> Queue<T> {\n    fn new() -> Self {\n        Queue { elements: VecDeque::new() }\n    }\n\n    fn enqueue(&mut self, value: T) {\n        self.elements.push_back(value);\n    }\n\n    fn dequeue(&mut self) -> Option<T> {\n        self.elements.pop_front()\n    }\n\n    fn front(&self) -> Option<&T> {\n        self.elements.front()\n    }\n\n    fn len(&self) -> usize {\n        self.elements.len()\n    }\n}\n\nfn main() {\n    let mut queue = Queue::new();\n    queue.enqueue("第一个");\n    queue.enqueue("第二个");\n    queue.enqueue("第三个");\n\n    println!("队首元素: {:?}", queue.front()); // Some("第一个")\n    println!("出队: {:?}", queue.dequeue()); // Some("第一个")\n    println!("队列长度: {}", queue.len()); // 2\n}

重要提示： VecDeque 使用环形缓冲区，因此在两端进行插入和删除操作的时间复杂度均为 O(1)。这比使用 Vec 实现队列要快得多。

2. Rust 中的二叉搜索树（BST）

二叉搜索树是基础数据结构之一。我们使用 Box 来实现递归类型：

use std::cmp::Ordering;\n\n#[derive(Debug)]\nstruct Node<T: Ord> {\n    value: T,\n    left: Option<Box<Node<T>>>,\n    right: Option<Box<Node<T>>>,\n}\n\n#[derive(Debug)]\nstruct BinarySearchTree<T: Ord> {\n    root: Option<Box<Node<T>>>,\n}\n\nimpl<T: Ord> BinarySearchTree<T> {\n    fn new() -> Self {\n        BinarySearchTree { root: None }\n    }\n\n    fn insert(&mut self, value: T) {\n        let mut current = &mut se