Un Queue (también conocido como cola) es una estructura de datos lineal en la que los elementos se insertan en un extremo (rear) y se eliminan por el otro extremo (front). Se sigue una regla de "primero en entrar, primero en salir" (FIFO, por sus siglas en inglés - First In, First Out).
Un ejemplo cotidiano de un queue puede ser una fila de personas esperando para ser atendidas en un establecimiento.
En JavaScript, podemos implementar un queue usando un array y utilizando dos punteros para hacer referencia al front y rear del queue. O al igual que en las clases anteriores podemos crear nuestra propia queue desde 0.
Complejidad algorítmica
La complejidad de los métodos de un queue también se puede medir con Big O notation, y en este caso, son bastante buenos.
Algoritmo
Big O Notation
Acceder a elementos
O(n)
Insertar
O(1)
Eliminar
O(1)
Verificar si el Queue está vacío
O(1)
Verificar la cantidad de elementos en el Queue
O(1)
Como podemos ver, la complejidad de los algoritmos es constante, lo que hace que los queues sean muy eficientes para trabajar con ellos.
Oportunidades donde puedes usar un Queue
Cuando necesites procesar datos en el mismo orden en que se recibieron, como mensajes de correo electrónico, solicitudes de clientes, etc.
Cuando necesites mantener un registro de los últimos elementos agregados o modificados, como los registros de transacciones de un sistema de base de datos.
Cuando necesites realizar un recorrido en amplitud (BFS, por sus siglas en inglés - Breadth First Search) de un grafo o un árbol. En este caso, el queue se utiliza para almacenar los nodos adyacentes que aún no se han visitado.
Situaciones en las que NO es muy conveniente usarlos
Cuando necesites acceso aleatorio a los elementos. En este caso, sería más eficiente utilizar otra estructura de datos como un array o un árbol binario de búsqueda.
Cuando necesites buscar elementos específicos en el queue. En este caso, también sería más eficiente utilizar una estructura de datos como un hash table.
Construyamos un Queue
En JavaScript, un queue se puede implementar utilizando un array y utilizando los métodos push y shift para insertar y eliminar elementos, respectivamente. Veamos un ejemplo de cómo se puede construir un queue en JavaScript:
// Node define un nodo de la queueclassNode{constructor(value){// Cada nodo tiene dos propiedades // value que guarda el valor del nodothis.value= value;// next que guarda el siguiente nodo de la lista.this.next=null;}}// La clase Queue representa una colaclassQueue{// El constructor tiene tres propiedadesconstructor(){// first que apunta al primer nodo de la colathis.first=null;// last que apunta al último nodo de la colathis.last=null;// length que representa la cantidad de nodos en la cola.this.length=0;}// El método enqueue agrega un nuevo nodo a la colaenqueue(value){// Crea un nuevo nodo con el valor pasado como parámetro// y lo agrega al final de la colaconst newNode =newNode(value);if(this.length===0){// Si la cola estaba vacía antes de agregar el nuevo nodo // tanto first como last apuntan al nuevo nodo.this.first= newNode;this.last= newNode;}else{this.last.next= newNode;this.last= newNode;}this.length++;}// El método dequeue remueve el primer nodo de la cola y devuelve su valordequeue(){if(this.length===0){// Si la cola estaba vacía, el método lanza una excepciónthrownewError("La queue está vacía");}// Guardamos la referencia al valor que será removidoconst removedNode =this.first;// Si la cola solo tenía un nodo antes de remover el primer nodo // tanto first como last apuntan a null.if(this.first===this.last){this.last=null;}// Reasignamos los valoresthis.first=this.first.next;// y reducimos la longitudthis.length--;// Se retorna el valor del nodo removidoreturn removedNode.value;}// El método isEmpty devuelve true si la cola está vacía// false en caso contrario.isEmpty(){returnthis.length===0;}// El método size devuelve la cantidad de nodos en la cola.size(){returnthis.length;}}
lock
lock