Queues en JavaScript
Clase 91 de 99 • 30 días de JavaScript
Contenido del curso
¿Qué es un Queue?
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
Situaciones en las que NO es muy conveniente usarlos
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 queue class Node { constructor(value) { // Cada nodo tiene dos propiedades // value que guarda el valor del nodo this.value = value; // next que guarda el siguiente nodo de la lista. this.next = null; } } // La clase Queue representa una cola class Queue { // El constructor tiene tres propiedades constructor() { // first que apunta al primer nodo de la cola this.first = null; // last que apunta al último nodo de la cola this.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 cola enqueue(value) { // Crea un nuevo nodo con el valor pasado como parámetro // y lo agrega al final de la cola const newNode = new Node(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 valor dequeue() { if (this.length === 0) { // Si la cola estaba vacía, el método lanza una excepción throw new Error("La queue está vacía"); } // Guardamos la referencia al valor que será removido const 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 valores this.first = this.first.next; // y reducimos la longitud this.length--; // Se retorna el valor del nodo removido return removedNode.value; } // El método isEmpty devuelve true si la cola está vacía // false en caso contrario. isEmpty() { return this.length === 0; } // El método size devuelve la cantidad de nodos en la cola. size() { return this.length; } }
Todo esto y más lo puedes aprender en el Curso de Estructuras de Datos con JavaScript
