Queues en JavaScript

¿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

• 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 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