Algoritmos y estructuras de datos en Rust: guía práctica

Algoritmos y estructuras de datos en Rust: por qué es importante

Rust es un lenguaje de programación de sistemas moderno que combina el rendimiento de C++ con la seguridad de memoria proporcionada por el sistema de ownership (propiedad). Estudiar algoritmos y estructuras de datos en Rust permite no solo dominar conceptos clásicos de Computer Science, sino también comprender más profundamente las características únicas del lenguaje: borrowing (préstamo), lifetimes (tiempos de vida) y zero-cost abstractions (abstracciones de costo cero).

En este artículo analizaremos tres estructuras de datos fundamentales (pila, cola y árbol binario de búsqueda) y un algoritmo clásico (ordenamiento rápido), implementados en Rust. Cada ejemplo incluye código y explicaciones que te ayudarán a pasar de la teoría a la práctica.

1. Pila en Rust: implementación con Vec

La pila es una estructura de datos que funciona bajo el principio LIFO (Last In, First Out). En Rust, la forma más sencilla de implementar una pila es usando el Vec estándar, que proporciona todos los métodos necesarios: push para agregar y pop para extraer.

Sin embargo, para demostrar la seguridad de Rust, crearemos un envoltorio con manejo explícito de errores:

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 superior: {:?}", stack.peek()); // Some(30)    println!("Extrayendo: {:?}", stack.pop());         // Some(30)    println!("Extrayendo: {:?}", stack.pop());         // Some(20)    println!("¿La pila está vacía? {}", stack.is_empty());      // false}

La ventaja clave de Rust aquí es el sistema de tipos. Si intentas extraer un elemento de una pila vacía, el compilador te obligará a manejar el Option, lo que elimina los errores de desreferencia de puntero nulo típicos de C/C++.

2. Cola: implementación manual con buffer circular

La cola (FIFO) es más compleja que la pila porque requiere una eliminación eficiente desde el inicio. Rust no proporciona una cola bidireccional lista con rendimiento garantizado, por lo que implementaremos un buffer circular (circular buffer) de tamaño fijo.

Este es un excelente ejemplo para demostrar código unsafe y punteros crudos, pero nos mantendremos en la 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("Cola llena");        }        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()