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

Introducción: Por qué Rust es ideal para algoritmos y estructuras de datos

Rust combina el rendimiento de C/C++ con la seguridad de la memoria, lo que lo convierte en una excelente opción para implementar algoritmos y estructuras de datos. Gracias al sistema de propiedad (ownership) y préstamo (borrowing), puede crear estructuras eficientes y seguras sin un recolector de basura. En este artículo, analizaremos la implementación práctica de estructuras de datos y algoritmos clave en Rust, desde una pila hasta un árbol binario y el recorrido de grafos.

Usaremos solo la biblioteca estándar de Rust para que pueda aplicar el código inmediatamente en sus proyectos. Todos los ejemplos se compilan y funcionan con Rust 2021 edition.

1. Pila y cola: estructuras clásicas en Rust

Pila (Stack)

La pila funciona bajo el principio LIFO (Last In, First Out). En Rust, la forma más sencilla de implementar una pila es 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 superior: {:?}", stack.peek()); // Some(30)\n    println!("Extrayendo: {:?}", stack.pop()); // Some(30)\n    println!("¿La pila está vacía? {}", stack.is_empty()); // false\n}

Ventaja: Vec ya proporciona O(1) amortizado para push/pop, y Rust garantiza que la memoria se liberará al salir del ámbito.

Cola (Queue)

La cola funciona bajo FIFO (First In, First Out). Para una implementación eficiente, usamos VecDeque de la biblioteca estándar:

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("primero");\n    queue.enqueue("segundo");\n    queue.enqueue("tercero");\n\n    println!("Primero en la cola: {:?}", queue.front()); // Some("primero")\n    println!("Atendiendo: {:?}", queue.dequeue()); // Some("primero")\n    println!("Longitud de la cola: {}", queue.len()); // 2\n}

Importante: VecDeque usa un búfer circular, lo que proporciona O(1) para inserción y eliminación en ambos extremos. Esto es significativamente más rápido que usar Vec para una cola.

2. Árbol binario de búsqueda (BST) en Rust

El árbol binario de búsqueda es una de las estructuras de datos fundamentales. Lo implementamos 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