Una cola (queue), es una estructura de datos en donde las extracciones y inserciones se llevan por los extremos de esta, es un elemento que se rige bajo el siguiente principio: FIFO (First In, First Out), es decir, el primer elemento que se inserta en la cola es el primero en ser eliminado. Al igual que las pilas, algunas veces parecieran invisibles, sin embargo siempre están ahí, formando parte de un algoritmo mas grande quedando ocultas para los usuarios.
Como su nombre lo indica, una forma muy común de ver a esta estructura, es como la cola de un banco, una tienda, un concierto etc; en donde conforme llegan las personas se asigna un turno para ser atendidas.
Operaciones en una Queue:
Las principales operaciones de una queue son la creación, destrucción, inserción y extracción, así como indicar su capacidad si esta llena o vacía.
En las queue a las inserciones se les conoce generalmente como Equeue y a las extracciones como Dequeue, Encolar y Desencolar por su traducción al español.
En las queue las operaciones tienen nombres generalmente aceptados para las funciones.
- New (Crea una nueva cola)
- Destroy (Destruye la cola)
- Enqueue (Agrega un elemento al final de la cola)
- Dequeue (Saca el elemento a principio de la cola )
- Peek (Observa un elemento al principio de la cola, a diferencia de Dequeue solo observa el elemento pero no lo extrae )
- Len (Arroja la cantidad de elementos en la cola )
- Capacity (Arroja la capacidad de la cola)
- IsEmpty ( Indica True o False si la cola esta vacía )
- IsFull (Indica si la cola esta llena ).
- MakeEmpty (Vacía la cola )
Programación.
Las dos formas mas común de programa una cola es por medio de arreglos o listas, cada una tiene sus ventajas y desventajas.
Implementación con Arreglos:
Ventajas:
Acceso Aleatorio: Con los arreglos, se puede acceder directamente a cualquier elemento utilizando su índice, lo que permite un acceso rápido a los elementos.
Eficiencia en el Almacenamiento: Los arreglos pueden ser más eficientes en términos de uso de memoria en comparación con algunas implementaciones de listas, ya que no hay necesidad de almacenar referencias adicionales.
Desventajas:
Tamaño Fijo: Los arreglos tienen un tamaño fijo, lo que significa que necesitas conocer el tamaño máximo que necesitarás anticipadamente, lo que puede ser ineficiente si la cantidad de elementos varía mucho.
Inserción y Eliminación Costosas: Insertar o eliminar elementos en medio de un arreglo puede ser costoso en términos de rendimiento, ya que puede requerir el desplazamiento de otros elementos.
Implementación con Listas Enlazadas:
Ventajas:
Tamaño Dinámico: Las listas enlazadas no tienen un tamaño fijo y pueden crecer o contraerse según sea necesario, lo que las hace ideales para estructuras de datos que cambian de tamaño frecuentemente.
Inserción y Eliminación Eficientes: Insertar y eliminar elementos en una lista enlazada puede ser más eficiente que en un arreglo, especialmente si se trata de inserciones y eliminaciones en el medio de la estructura.
Desventajas:
Acceso Secuencial: En una lista enlazada, el acceso a los elementos se realiza de forma secuencial, lo que puede ser menos eficiente en comparación con el acceso aleatorio de los arreglos.
Uso de Memoria Adicional: Las listas enlazadas a menudo requieren más memoria que los arreglos, ya que cada nodo en la lista necesita almacenar una referencia al siguiente nodo.
¿Qué es mejor implementación con listas o arreglos ?
La respuesta a esta pregunta es compleja pues se debe buscar no solo que nuestro código funcione si no también que se lo mas eficiente posible, para ello se deben considerar factores como eficiencia en términos de inserción, eliminación y acceso a los elementos, así como los requisitos de memoria y la previsibilidad del tamaño de la cola. Si la cantidad de elementos es variable y desconocida, las listas enlazadas pueden ser más adecuadas, mientras que si se conoce el tamaño máximo de la cola y se requiere un acceso rápido a los elementos, los arreglos pueden ser preferibles.