Algoritmos e estruturas de dados em Rust: um guia prático

Algoritmos e estruturas de dados em Rust: por que isso é importante

Rust é uma linguagem de programação de sistemas moderna que combina o desempenho do C++ com a segurança de memória fornecida pelo sistema de ownership (propriedade). Estudar algoritmos e estruturas de dados em Rust permite não apenas dominar conceitos clássicos da Computer Science, mas também compreender mais profundamente as características únicas da linguagem: borrowing (empréstimo), lifetimes (tempos de vida) e zero-cost abstractions (abstrações de custo zero).

Neste artigo, abordaremos três estruturas de dados fundamentais (pilha, fila e árvore binária de busca) e um algoritmo clássico (quick sort), implementados em Rust. Cada exemplo é acompanhado de código e explicações que ajudarão você a passar da teoria à prática.

1. Pilha em Rust: implementação com Vec

Uma pilha é uma estrutura de dados que opera pelo princípio LIFO (Last In, First Out). Em Rust, a maneira mais simples de implementar uma pilha é usando o Vec padrão, que fornece todos os métodos necessários: push para adicionar e pop para remover.

No entanto, para demonstrar a segurança do Rust, criaremos um wrapper com tratamento explícito de erros:

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!("Elemento do topo: {:?}", stack.peek()); // Some(30)    println!("Removendo: {:?}", stack.pop());         // Some(30)    println!("Removendo: {:?}", stack.pop());         // Some(20)    println!("A pilha está vazia? {}", stack.is_empty());      // false}

A principal vantagem do Rust aqui é o sistema de tipos. Se você tentar remover um elemento de uma pilha vazia, o compilador forçará você a tratar o Option, o que elimina erros de desreferenciamento de ponteiro nulo, comuns em C/C++.

2. Fila: implementação manual com buffer circular

Uma fila (FIFO) é mais complexa que uma pilha porque requer remoção eficiente do início. O Rust não fornece uma fila bidirecional pronta com desempenho garantido, então implementaremos um buffer circular (circular buffer) de tamanho fixo.

Este é um excelente exemplo para demonstrar código unsafe e ponteiros brutos, mas permaneceremos na zona segura usando Vec e índices:

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("Fila cheia");        }        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()