Colecciones de colas y pilas en Rust

1. Colección de óxido
2. Cola de óxido
3. Pila en óxido

Este artículo trata sobre la presencia de colecciones de colas y pilas en Rust.

Colección de óxido

La biblioteca de colección estándar de Rust incluye implementaciones eficientes de las estructuras de datos más utilizadas en la programación de propósito general. Como resultado, dos bibliotecas deberían poder comunicarse sin requerir mucha conversión de datos si usan las implementaciones estándar.

Para empezar, probablemente deberíamos usar Vec. Estas dos colecciones cubren la mayoría de los escenarios de almacenamiento y procesamiento de datos genéricos.

Sobresalen en lo que hacen. Todas las demás colecciones de la biblioteca estándar tienen casos de uso específicos para los que son la opción óptima, pero estos casos de uso son, en cambio, de nicho.

Incluso si Vec y HashMap son técnicamente deficientes, probablemente sean un punto de partida suficiente.

Las colecciones disponibles en Rust se pueden agrupar en cuatro categorías principales, como se muestra a continuación.

1. Secuencias: Vec, VecDeque, LinkedList
2. Mapas: HashMap, BTreeMap
3. Conjuntos: HashSet, BTreeSet
4. Misc: BinaryHeap

Cola de óxido

La estructura de datos de la cola en Rust se usa para almacenar los elementos. La cola en Rust funciona de forma FIO, lo que implica primero en entrar, primero en salir.

Esta es una cola estándar que se incluye con la biblioteca de la colección Rust. Es una estructura de datos lineal.

Queue nos ofrece varias operaciones que pueden usarse para manipularlo. Puede contener cualquier número de elementos; toda la implementación se basa en la estructura de datos vectoriales de Rust.

Sintaxis:

let mut variable_name : Queue<queue_size> = queue![];

Pila en óxido

Una pila es una colección de elementos que se pueden agregar y quitar, pero solo en el siguiente orden: último en entrar, primero en salir (LIFO). Por ejemplo, si aborda un tren abarrotado, será el primero en tener que salir para que otros pasajeros también lo hagan.

La adición de objetos generalmente se denomina push, mientras que la eliminación de bienes se denomina pop porque estas funciones se implementan en Rust utilizando la estructura de datos Vec (vector).

Para crear una nueva pila, podemos usar la siguiente sintaxis.

let s = Stack { stack: Vec::new() };

Rust’ no proporciona ninguna biblioteca con latencia garantizada para agregar elementos a la biblioteca estándar. Al agregar elementos adicionales a las colecciones de Rust, se puede asignar memoria.

En el peor de los casos, la asignación de memoria puede llevar un tiempo infinito.

Hay dos posibles candidatos en cada caso.

1. Se puede implementar una pila encima de una Vec o una LinkedList, ya que ambas admiten pop back y push back.
2. Se puede implementar una cola sobre un VecDeque o un LinkedList, ya que ambos admiten pop front y push back.

Hay alguna diferencia entre Vec y LinkedList. Este último es más simplista: se asigna memoria para cada llamada a retroceso.

Por un lado, esto es favorable porque el costo de push back es independiente de la cantidad de objetos que ya están en la colección. Aún así, por otro lado, la asignación de memoria puede llevar mucho tiempo.

El primero es un poco más complicado porque:

1. tiene un mayor rendimiento debido a su naturaleza compatible con caché
2. tiene capacidad adicional, asegurando que no se asigna push back mientras exista exceso de capacidad; aún mantiene amortizado O(1) push back aun cuando no se reserve con anticipación el exceso de capacidad

Sería mejor usar Vec para pilas y VecDeque para colas.