Estructura de DatosDEFINICIÓN
Una estructura de datos es una manera de organizar y almacenar datos para que puedan ser utilizados de manera eficiente. Incluye las operaciones que se pueden realizar sobre esos datos, así como las relaciones entre los diferentes tipos de datos.
Estructuras LinealesLINEALES
Las estructuras lineales almacenan elementos en secuencia, donde cada elemento tiene un único predecesor y sucesor. Se implementan en Rust utilizando Vec<T>, Box<T> y punteros inteligentes para gestionar la memoria de forma segura.
Es una estructura de datos que sigue el principio de LIFO (Last In, First Out). Esto significa que el último elemento añadido es el primero en ser eliminado.
Operaciones Principales:
- Push: Añadir un elemento a la parte superior de la pila.
- Pop: Eliminar y devolver el elemento de la parte superior.
- Peek: Ver el elemento en la parte superior sin eliminarlo.
- IsEmpty: Comprobar si la pila está vacía.
Uso Común:
- Manejo de la recursión.
- Implementación de deshacer/rehacer en aplicaciones.
- Evaluación de expresiones y conversión de notación.
Implementación en Rust:
¿Qué hace este código?
Implementa un Linter que valida paréntesis balanceados en código fuente. Escanea cada carácter y, al encontrar un símbolo de apertura, lo apila; al encontrar uno de cierre, verifica que coincida con el último apilado y lo desapila.
¿Por qué Pila?
La pila (LIFO) es ideal porque el último paréntesis abierto debe ser el primero en cerrarse. Vec<char> en Rust funciona como pila dinámica con push() y pop() en O(1).
// La pila se implementa con Vec<char> como almacenamiento subyacente.
// Vec funciona como una pila dinámica: push() añade al tope, pop() remueve del tope.
// Option<String> almacena el último error encontrado (None si no hay error).
pub struct Linter {
error: Option<String>,
stack: Vec<char>, // Almacena los paréntesis de apertura: '(', '[', '{'
}
impl Linter {
pub fn new() -> Self {
Self {
error: None,
stack: Vec::new(), // Pila vacía al inicio
}
}
// Evalúa si el texto tiene paréntesis balanceados.
// Recorre cada carácter y aplica la lógica LIFO:
pub fn lint(&mut self, text: &str) -> Result<(), String> {
self.stack.clear();
self.error = None;
for (_, char) in text.chars().enumerate() {
if self.is_opening_brace(char) {
// PUSH: Si es de apertura, lo apilamos (guardamos para después)
self.stack.push(char);
} else if self.is_closing_brace(char) {
// POP: Si es de cierre, verificamos que coincida con el tope
if self.stack.is_empty() {
// No hay nada en la pila → error: no tiene par de apertura
self.error = Some(format!(
"{} does not have a corresponding opening brace", char
));
return Err(self.error.clone().unwrap());
}
if !self.closes_most_recent_opening_brace(char) {
// El tope no coincide → error de correspondencia
self.error = Some(format!(
"{} has no corresponding opening brace", char
));
return Err(self.error.clone().unwrap());
}
// Coincide → desapilamos (el par está balanceado)
self.stack.pop();
}
}
// Si la pila no está vacía, quedaron paréntesis sin cerrar
if !self.stack.is_empty() {
let last_opening = self.stack.last().unwrap();
self.error = Some(format!(
"{} does not have a closing brace", last_opening
));
return Err(self.error.clone().unwrap());
}
Ok(()) // Todos los paréntesis están balanceados
}
pub fn get_error(&self) -> Option<&String> {
self.error.as_ref()
}
// Verifica si un carácter es de apertura: ( o [ o {
fn is_opening_brace(&self, char: char) -> bool {
matches!(char, '(' | '[' | '{')
}
// Verifica si un carácter es de cierre: ) o ] o }
fn is_closing_brace(&self, char: char) -> bool {
matches!(char, ')' | ']' | '}')
}
// Devuelve el par de apertura correspondiente a un carácter de cierre
fn opening_brace_of(&self, char: char) -> Option<char> {
match char {
')' => Some('('),
']' => Some('['),
'}' => Some('{'),
_ => None,
}
}
// Consulta el tope de la pila sin modificarla
fn most_recent_opening_brace(&self) -> Option<char> {
self.stack.last().copied()
}
// Verifica si un carácter de cierre corresponde al paréntesis más reciente
fn closes_most_recent_opening_brace(&self, char: char) -> bool {
if let Some(opening_brace) = self.opening_brace_of(char) {
if let Some(most_recent) = self.most_recent_opening_brace() {
return opening_brace == most_recent;
}
}
false
}
}Es una estructura de datos que sigue el principio de FIFO (First In, First Out). Esto significa que el primer elemento añadido es el primero en ser eliminado.
Operaciones Principales:
- Enqueue: Añadir un elemento al final de la cola.
- Dequeue: Eliminar y devolver el elemento del frente.
- Peek: Ver el elemento en el frente sin eliminarlo.
- IsEmpty: Comprobar si la cola está vacía.
Uso Común:
- Manejo de tareas en sistemas operativos.
- Implementación de algoritmos de búsqueda en grafos.
- Gestión de eventos en sistemas de tiempo real.
Implementación en Rust:
¿Qué hace este código?
Simula un gestor de impresión: los documentos se añaden a una cola y se procesan en el mismo orden en que llegaron (primero en entrar, primero en salir).
¿Por qué Cola?
La cola (FIFO) garantiza equidad: cada documento se imprime en su turno. push() añade al final, remove(0) saca del frente.
// La cola se implementa con Vec<String>.
// push() añade al final (enqueue), remove(0) remueve del frente (dequeue).
// En Rust, remove(0) es O(n) porque desplaza todos los elementos.
struct PrintManager {
queue: Vec<String>, // Cola FIFO de documentos a imprimir
}
impl PrintManager {
fn new() -> Self {
PrintManager { queue: Vec::new() } // Cola vacía
}
// ENQUEUE: Añade un documento al final de la cola
fn queue_print_job(&mut self, document: String) {
self.queue.push(document);
}
// Procesa todos los documentos en orden FIFO (primero en entrar, primero en salir)
fn run(&mut self) {
while !self.queue.is_empty() {
// DEQUEUE: Remueve el primer documento de la cola
let document = self.queue.remove(0);
self.print(document);
}
}
fn print(&self, document: String) {
println!("{}", document);
}
}
fn main() {
let mut pm = PrintManager::new();
pm.queue_print_job(String::from("Documento 1")); // Enqueue
pm.queue_print_job(String::from("Documento 2")); // Enqueue
pm.queue_print_job(String::from("Documento 3")); // Enqueue
pm.run(); // Imprime en orden: 1, 2, 3 (FIFO)
}Es una estructura de datos que permite la inserción y eliminación de elementos desde ambos extremos, es decir, tanto desde el frente como desde la parte trasera.
Operaciones Principales:
- Append: Añadir un elemento al final del deque.
- Appendleft: Añadir un elemento al comienzo del deque.
- Pop: Eliminar y devolver el elemento del final.
- Popleft: Eliminar y devolver el elemento del frente.
- IsEmpty: Comprobar si el deque está vacío.
Uso Común:
- Algoritmos que requieren acceso eficiente a ambos lados.
- Manejo de tareas procesadas de manera flexible.
Implementación en Rust:
¿Qué hace este código?
Implementa un deque (cola de doble extremo) con una lista doblemente enlazada. Permite insertar y eliminar elementos tanto por el frente como por el final en O(1).
¿Por qué Deque con lista doblemente enlazada?
Cada nodo apunta al siguiente y al anterior, lo que permite traversal en ambas direcciones. Rc<RefCell<T>> permite que múltiples nodos compartan referencia con mutabilidad interior.
// El deque (double-ended queue) permite inserción y eliminación en ambos extremos.
// Se implementa con una lista doblemente enlazada usando Rc<RefCell<Node>>.
// Rc permite múltiples propietarios, RefCell permite mutabilidad interior.
use std::cell::RefCell;
use std::rc::Rc;
type NodePtr = Rc<RefCell<Node>>; // Puntero compartido a un nodo
struct Node {
data: String,
next: Option<NodePtr>, // Enlace al siguiente nodo
previous: Option<NodePtr>, // Enlace al nodo anterior (doble enlace)
}
impl Node {
fn new(data: &str) -> NodePtr {
Rc::new(RefCell::new(Node {
data: data.to_string(),
next: None,
previous: None,
}))
}
}
struct DoublyLinkedList {
first_node: Option<NodePtr>, // Extremo frontal
last_node: Option<NodePtr>, // Extremo trasero
}
impl DoublyLinkedList {
fn new() -> Self {
DoublyLinkedList {
first_node: None,
last_node: None,
}
}
// APPEND: Inserta al final del deque — O(1)
fn insert_at_end(&mut self, value: &str) {
let new_node = Node::new(value);
match self.last_node.take() {
Some(old_last) => {
// Enlazamos el nuevo nodo al anterior último
new_node.borrow_mut().previous = Some(old_last.clone());
old_last.borrow_mut().next = Some(new_node.clone());
self.last_node = Some(new_node); // El nuevo es el último
}
None => {
// Lista vacía: el nuevo nodo es primero y último
self.first_node = Some(new_node.clone());
self.last_node = Some(new_node);
}
}
}
// POPLEFT: Elimina y devuelve el elemento del frente — O(1)
fn remove_from_front(&mut self) -> Option<String> {
let old_first = self.first_node.take();
if let Some(node) = old_first {
let data_to_return = node.borrow().data.clone();
// El siguiente se convierte en el nuevo primero
self.first_node = node.borrow_mut().next.take();
match &self.first_node {
Some(new_first) => {
new_first.borrow_mut().previous = None; // Sin predecessor
}
None => {
self.last_node = None; // La lista quedó vacía
}
}
return Some(data_to_return);
}
None
}
}
// Queue wrapper que usa DoublyLinkedList como implementación subyacente
struct Queue {
queue: DoublyLinkedList,
}
impl Queue {
fn new() -> Self {
Queue { queue: DoublyLinkedList::new() }
}
fn enque(&mut self, value: &str) {
self.queue.insert_at_end(value); // Append
}
fn deque(&mut self) -> Option<String> {
self.queue.remove_from_front() // PopLeft
}
}
fn main() {
let mut fila_supermercado = Queue::new();
fila_supermercado.enque("Ana"); // Append: [Ana]
fila_supermercado.enque("Carlos"); // Append: [Ana, Carlos]
fila_supermercado.enque("Beatriz"); // Append: [Ana, Carlos, Beatriz]
if let Some(atendido) = fila_supermercado.deque() {
println!("Se atendió a: {}", atendido); // PopLeft: "Ana"
}
}Siguiente artículo
Estructuras No Lineales
Listas enlazadas, árboles binarios de búsqueda y grafos con Rust
Comentarios
0Sin comentarios
Sé el primero en compartir tu opinión.
También te puede interesar
Descubre más contenido relacionado que podría ser de tu interés
Un Solo Esqueleto, Múltiples Cerebros: La Arquitectura Paramétrica al Descubierto
Regresión Lineal, Logística y SVM comparten el mismo esqueleto matemático. Lo que cambia es cómo cada uno define y castiga el error.
Convirtiendo datos categóricos a númericos con OrdinalEncoder
El OrdinalEncoder se utiliza para convertir datos categóricos ordinales en valores numéricos
