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

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

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

Rust сочетает производительность C/C++ с безопасностью памяти, что делает его отличным выбором для реализации алгоритмов и структур данных. Благодаря системе владения (ownership) и заимствования (borrowing), вы можете создавать эффективные и безопасные структуры без сборщика мусора. В этой статье мы разберем практическую реализацию ключевых структур данных и алгоритмов на Rust — от стека до бинарного дерева и обхода графа.

Мы будем использовать только стандартную библиотеку Rust, чтобы вы могли сразу применить код в своих проектах. Все примеры компилируются и работают с Rust 2021 edition.

1. Стек и очередь: классические структуры на Rust

Стек (Stack)

Стек работает по принципу LIFO (Last In, First Out). В Rust проще всего реализовать стек на базе Vec:

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

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

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

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

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

    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.is_empty()); // false
}

Преимущество: Vec уже предоставляет амортизированное O(1) для push/pop, а Rust гарантирует, что память будет освобождена при выходе из области видимости.

Очередь (Queue)

Очередь работает по FIFO (First In, First Out). Для эффективной реализации используем VecDeque из стандартной библиотеки:

use std::collections::VecDeque;

struct Queue<T> {
    elements: VecDeque<T>,
}

impl<T> Queue<T> {
    fn new() -> Self {
        Queue { elements: VecDeque::new() }
    }

    fn enqueue(&mut self, value: T) {
        self.elements.push_back(value);
    }

    fn dequeue(&mut self) -> Option<T> {
        self.elements.pop_front()
    }

    fn front(&self) -> Option<&T> {
        self.elements.front()
    }

    fn len(&self) -> usize {
        self.elements.len()
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue("первый");
    queue.enqueue("второй");
    queue.enqueue("третий");

    println!("Первый в очереди: {:?}", queue.front()); // Some("первый")
    println!("Обслуживаем: {:?}", queue.dequeue()); // Some("первый")
    println!("Длина очереди: {}", queue.len()); // 2
}

Важно: VecDeque использует кольцевой буфер, что дает O(1) для вставки и удаления с обоих концов. Это значительно быстрее, чем использование Vec для очереди.

2. Бинарное дерево поиска (BST) на Rust

Бинарное дерево поиска — одна из фундаментальных структур данных. Реализуем его с использованием Box для рекурсивных типов:

use std::cmp::Ordering;

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

#[derive(Debug)]
struct BinarySearchTree<T: Ord> {
    root: Option<Box<Node<T>>>,
}

impl<T: Ord> BinarySearchTree<T> {
    fn new() -> Self {
        BinarySearchTree { root: None }
    }

    fn insert(&mut self, value: T) {
        let mut current = &mut self.root;
        while let Some(node) = current {
            match value.cmp(&node.value) {
                Ordering::Less => current = &mut node.left,
                Ordering::Greater => current = &mut node.right,
                Ordering::Equal => return, // дубликаты не добавляем
            }
        }
        *current = Some(Box::new(Node {
            value,
            left: None,
            right: None,
        }));
    }

    fn search(&self, value: &T) -> bool {
        let mut current = &self.root;
        while let Some(node) = current {
            match value.cmp(&node.value) {
                Ordering::Less => current = &node.left,
                Ordering::Greater => current = &node.right,
                Ordering::Equal => return true,
            }
        }
        false
    }

    // Обход в порядке (in-order) — возвращает отсортированный вектор
    fn in_order_traversal(&self) -> Vec<&T> {
        let mut result = Vec::new();
        Self::in_order_helper(&self.root, &mut result);
        result
    }

    fn in_order_helper(node: &Option<Box<Node<T>>>, result: &mut Vec<&T>) {
        if let Some(ref n) = node {
            Self::in_order_helper(&n.left, result);
            result.push(&n.value);
            Self::in_order_helper(&n.right, result);
        }
    }
}

fn main() {
    let mut bst = BinarySearchTree::new();
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(2);
    bst.insert(4);

    println!("Содержит 4? {}", bst.search(&4)); // true
    println!("Содержит 6? {}", bst.search(&6)); // false
    println!("Отсортированный обход: {:?}", bst.in_order_traversal()); // [2, 3, 4, 5, 7]
}

Ключевые моменты: