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

Rust中的算法与数据结构：为何重要

Rust是一种现代系统编程语言，它结合了C++的性能与所有权系统（ownership）提供的内存安全性。在Rust中学习算法和数据结构，不仅能掌握经典的计算机科学概念，还能更深入地理解该语言的独特特性：借用（borrowing）、生命周期（lifetimes）和零成本抽象（zero-cost abstractions）。

本文将用Rust实现三种基础数据结构（栈、队列和二叉搜索树）以及一个经典算法（快速排序）。每个示例都附有代码和解释，帮助您从理论过渡到实践。

1. Rust中的栈：通过Vec实现

栈是一种遵循LIFO（后进先出）原则的数据结构。在Rust中，最简单的实现方式是基于标准库的Vec，它提供了所有必要的方法：push用于添加元素，pop用于取出元素。

不过，为了展示Rust的安全性，我们将创建一个带有显式错误处理的封装：

pub struct Stack<T> {    elements: Vec<T>,}

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

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

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

    pub fn peek(&self) -> Option<&T> {        self.elements.last()    }

    pub fn is_empty(&self) -> bool {        self.elements.is_empty()    }}

fn main() {    let mut stack = Stack::new();    stack.push(10);    stack.push(20);    stack.push(30);

    println!("栈顶元素: {:?}", stack.peek()); // Some(30)    println!("弹出: {:?}", stack.pop());         // Some(30)    println!("弹出: {:?}", stack.pop());         // Some(20)    println!("栈为空? {}", stack.is_empty());      // false}

这里Rust的关键优势在于其类型系统。如果您尝试从空栈中取出元素，编译器会强制您处理Option，从而避免了C/C++中常见的空指针解引用错误。

2. 队列：使用环形缓冲区的手动实现

队列（FIFO）比栈更复杂，因为它需要高效地从头部删除元素。Rust没有提供现成的具有性能保证的双端队列，因此我们将实现一个固定大小的环形缓冲区（circular buffer）。

这是一个展示unsafe代码和原始指针的绝佳示例，但我们将保持在安全范围内，使用Vec和索引：

pub struct Queue<T> {    buffer: Vec<Option<T>>,    head: usize,    tail: usize,    capacity: usize,}

impl<T> Queue<T> {    pub fn new(capacity: usize) -> Self {        let mut buffer = Vec::with_capacity(capacity);        buffer.resize_with(capacity, || None);        Queue {            buffer,            head: 0,            tail: 0,            capacity,        }    }

    pub fn enqueue(&mut self, item: T) -> Result<(), &str> {        if (self.tail + 1) % self.capacity == self.head {            return Err("队列已满");        }        self.buffer[self.tail] = Some(item);        self.tail = (self.tail + 1) % self.capacity;        Ok(())    }

    pub fn dequeue(&mut self) -> Option<T> {        if self.head == self.tail {            return None;        }        let item = self.buffer[self.head].take();        self.head = (self.head + 1) % self.capacity;        item    }

    pub fn is_empty(&self) -> bool {        self.head == self.tail    }}

fn main()