Алгоритмы и структуры данных на Rust: практическое руководство

Алгоритмы и структуры данных на Rust: почему это важно

Rust — это современный системный язык программирования, который сочетает производительность C++ с безопасностью памяти, обеспечиваемой системой владения (ownership). Изучение алгоритмов и структур данных на Rust позволяет не только освоить классические концепции Computer Science, но и глубже понять уникальные особенности языка: заимствование, времена жизни и нулевые затраты на абстракции.

В этой статье мы разберём три фундаментальные структуры данных (стек, очередь и бинарное дерево поиска) и один классический алгоритм (быстрая сортировка), реализованные на Rust. Каждый пример сопровождается кодом и пояснениями, которые помогут вам перейти от теории к практике.

1. Стек на Rust: реализация через Vec

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out). В 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() {
    let mut queue = Queue::new(5);
    queue.enqueue(1).unwrap();
    queue.enqueue(2).unwrap();
    queue.enqueue(3).unwrap();

    println!("Извлекаем: {:?}", queue.dequeue()); // Some(1)
    println!("Извлекаем: {:?}", queue.dequeue()); // Some(2)
    println!("Очередь пуста? {}", queue.is_empty()); // false
}

Обратите внимание на использование Option<T> в буфере. Это позволяет безопасно "забирать" элемент из ячейки через .take(), не нарушая владение. Rust гарантирует, что мы не получим висячую ссылку.

3. Бинарное дерево поиска: рекурсия и владение

Бинарное дерево — классический пример для демонстрации рекурсивных структур. В Rust мы сталкиваемся с вызовом: как смоделировать рекурсивный тип данных, не нарушая правила владения?

Решение — использовать Box (умный указатель на кучу) и Option для представления отсутствующих узлов:

use std::cmp::Ordering;

#[derive(Debug)]
pub struct TreeNode<T> {
    value: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

impl<T: Ord> TreeNode<T> {
    pub fn new(value: T) -> Self {
        TreeNode {
            value,
            left: None,
            right: None,
        }
    }

    pub fn insert(&mut self, new_value: T) {
        match new_value.cmp(&self.value) {
            Ordering::Less => {
                match self.left {
                    Some(ref mut left) => left.insert(new_value),
                    None => self.left = Some(Box::new(TreeNode::new(new_value))),
                }
            }
            Ordering::Greater => {
                match self.right {
                    Some(ref mut right) => right.insert(new_value),
                    None => self.right = Some(Box::new(TreeNode::new(new_value))),
                }
            }
            Ordering::Equal => { /* дубликаты игнорируем */ }
        }
    }

    pub fn search(&self, target: &T) -> bool {
        match target.cmp(&self.value) {
            Ordering::Equal => true,
            Ordering::Less => self.left.as_ref().map_or(false, |l| l.search(target)),
            Ordering::Greater => self.right.as_ref().map_or(false, |r| r.search(target)),
        }
    }
}

fn main() {
    let mut root = TreeNode::new(10);
    root.insert(5);
    root.insert(15);
    root.insert(3);
    root.insert(7);

    println!("По