Algoritmos e Estruturas de Dados em Rust: Guia Prático

Introdução: Por que Rust é ideal para algoritmos e estruturas de dados

Rust combina o desempenho de C/C++ com a segurança de memória, tornando-o uma excelente escolha para implementar algoritmos e estruturas de dados. Graças ao sistema de ownership e borrowing, você pode criar estruturas eficientes e seguras sem um coletor de lixo. Neste artigo, abordaremos a implementação prática de estruturas de dados e algoritmos chave em Rust — desde pilha até árvore binária e travessia de grafos.

Usaremos apenas a biblioteca padrão do Rust para que você possa aplicar o código imediatamente em seus projetos. Todos os exemplos compilam e funcionam com Rust 2021 edition.

1. Pilha e Fila: Estruturas clássicas em Rust

Pilha (Stack)

A pilha funciona pelo princípio LIFO (Last In, First Out). Em Rust, a maneira mais simples de implementar uma pilha é usando 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!("Elemento do topo: {:?}", stack.peek()); // Some(30)\n    println!("Removendo: {:?}", stack.pop()); // Some(30)\n    println!("A pilha está vazia? {}", stack.is_empty()); // false\n}

Vantagem: Vec já fornece O(1) amortizado para push/pop, e o Rust garante que a memória será liberada ao sair do escopo.

Fila (Queue)

A fila funciona pelo princípio FIFO (First In, First Out). Para uma implementação eficiente, usamos VecDeque da biblioteca padrão:

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("primeiro");\n    queue.enqueue("segundo");\n    queue.enqueue("terceiro");\n\n    println!("Primeiro da fila: {:?}", queue.front()); // Some("primeiro")\n    println!("Atendendo: {:?}", queue.dequeue()); // Some("primeiro")\n    println!("Tamanho da fila: {}", queue.len()); // 2\n}

Importante: VecDeque usa um buffer circular, o que fornece O(1) para inserção e remoção em ambas as extremidades. Isso é significativamente mais rápido do que usar Vec para uma fila.

2. Árvore Binária de Busca (BST) em Rust

A árvore binária de busca é uma das estruturas de dados fundamentais. Vamos implementá-la usando Box para tipos recursivos:

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