Implementación de Queues (Colas) en JavaScript

5 minuto(s)

En esta página:

Cuando escuchas la palabra Cola, si no estas familiarizado con la programación se te viene a la mente una cola en el supermercado o en el hospital. Pero si eres programador, lo puedes asociar en un 99% con estructura de datos y algoritmos, en este Post te explicaré como implementar Queues (Colas) en JavaScript y al final te explicare para que sirven las Queues y en que se diferencian con los Array.

Una Queue (Cola) funciona según el principio FIFO (First In First Out) que traducido al español significa Primero en entrar, primero en salir. Es como una cola real de personas en un supermercado.

Las personas en la Queue (Cola) son Nodos y principalmente necesitamos crear cada nodo en el código JavaScript.

Utilizaremos clases que son la parte principal de POO, si no estas familiarizado con POO, te recomiendo leer el artículo Que es la Programación Orientada a Objetos POO y otros detalles.

Crearé una clase llamada Nodo a continuación:


class Nodo {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Nodo {

constructor(value) {

this.value = value;

this.next = null;

}

La anterior clase Nodo tiene 2 parámetros:

this.value: Es el valor que almacena la clase Nodo.
this.next: Es el enlace al siguiente nodo en la cola (inicialmente nulo, ya que no hay nodos en la cola).

Bueno, ya he creado el Nodo, pero también necesitamos crear una clase que almacene estos nodos y realice algunas acciones en ellos.


class Cola {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}

class Cola {

constructor() {

this.head = null;

this.tail = null;

this.length = 0;

}

La anterior clase Cola tiene 3 parámetros:

this.head: Es el enlace al primer nodo en la cola.
this.tail: Es el enlace al último nodo en la cola.
this.length: Es la cantidad de nodos en la cola.

Ahora veremos los métodos necesarios para gestionar las Queues (Colas).

Métodos Claves

Bien ahora vamos a escribir métodos de Estructura de datos de cola, el primer método que consideraremos es ponerenCola(value)

ponerenCola(value)

Este método nos sirve para agregar la clase Nodo a la cola final de la clase Cola. (En el código he colocado comentarios para explicar que hace cada parte del código)


ponerenCola(value) {
    const node = new Nodo(value); // Crea el nodo usando la clase Nodo 

    if (this.head) { // Si sale el primer nodo
        this.tail.next = node; // Inserta el nodo creado después de la cola  
        this.tail = node; // Ahora el nodo creado es el último nodo 
    } else { // Si no hay nodos en la cola 
        this.head = node; // El nodo creado lo llamaré 'head'  
        this.tail = node // También el nodo creado es una cola en la cola porque es único 
    }

    this.length++; // Aumenta la longitud de la cola en 1 
}

ponerenCola(value) {

const node = new Nodo(value); // Crea el nodo usando la clase Nodo

if (this.head) { // Si sale el primer nodo

this.tail.next = node; // Inserta el nodo creado después de la cola

this.tail = node; // Ahora el nodo creado es el último nodo

} else { // Si no hay nodos en la cola

this.head = node; // El nodo creado lo llamaré 'head'

this.tail = node // También el nodo creado es una cola en la cola porque es único

}

this.length++; // Aumenta la longitud de la cola en 1

}

Ahora agregaremos nodos a la cola, pero no tiene que ser interminable (pero a veces en las cosas de hospitales y supermercados es así), veamos como eliminar nodos de la cola.

eliminarCola()

Con este método eliminamos una cola, en el código he colocado comentarios para explicar que hace cada línea del código.


eliminarCola() {
    const current = this.head; // Guarda el enlace en el 'head' que debemos eliminar
    this.head = this.head.next; // Mueve el enlace 'head' al segundo nodo en la cola 
    this.length--; // Decrementamos la longitud de la cola 

    return current.value; // Devuelve el valor del nodo eliminado 
}

eliminarCola() {

const current = this.head; // Guarda el enlace en el 'head' que debemos eliminar

this.head = this.head.next; // Mueve el enlace 'head' al segundo nodo en la cola

this.length--; // Decrementamos la longitud de la cola

return current.value; // Devuelve el valor del nodo eliminado

}

En el código anterior puede ser complicado entender la siguiente parte del código:


this.head = this.head.next; // Mueve el enlace 'head' al segundo nodo en la cola

this.head = this.head.next; // Mueve el enlace 'head' al segundo nodo en la cola

Recuerda que en el mundo real, si el cajero del supermercado finalizó el cobro por los productos a un cliente (persona), este cliente deja la cola y luego se va.

En el código this.head es el cliente que deja la cola y ha comprado productos, entonces this.head.next es el siguiente cliente que pasa al cajero para hacer el pago de sus productos .

Hasta ahora podemos agregar y eliminar nodos de la cola, pero solo conocemos información sobre el primer y último nodo o personas en una cola del supermercado (en comparación con el mundo real). Si queremos saber que sucede en medio de la cola crearé un método llamado mostrar() que me muestra todos los valores de los nodos en la cola.

mostrar()

Con este método podré ver los valores de los nodos en la cola, en el código he colocado comentarios para explicar que hace cada línea del código.


mostrar() {
    let actual = this.head; // Guarda un enlace en el 'head' de la cola 

    while(actual) { // Pasa por cada nodo de la cola 
        console.log(actual.value); // Imprime el valor del nodo en la consola 
        actual = actual.next; // Mueve el enlace al siguiente nodo después del 'head' 
    }
}

mostrar() {

let actual = this.head; // Guarda un enlace en el 'head' de la cola

while(actual) { // Pasa por cada nodo de la cola

console.log(actual.value); // Imprime el valor del nodo en la consola

actual = actual.next; // Mueve el enlace al siguiente nodo después del 'head'

}

Para entenderlo mejor, pongamos de ejemplo la cola de un supermercado en donde esta pagando por sus productos el usuario this.head el cual se llama current.value o la actual persona en la cola.

Imaginemos que en la cola el usuario this.head le pregunta el nombre al segundo usuario de la cola, luego el segundo le pregunta su nombre al tercer usuario y así sucesivamente hasta el fina de la cola. El método mostrar() funciona de la misma manera.

En la consola mostraría los valores de cada usuario de la cola:


console.log('Usuario Actual en el cajero, Usuario 1');
console.log('Usuario 2');
console.log('Usuario 3');
console.log('Usuario 4'); 
console.log('Usuario 5');

console.log('Usuario Actual en el cajero, Usuario 1');

console.log('Usuario 2');

console.log('Usuario 3');

console.log('Usuario 4');

console.log('Usuario 5');

Bien ahora veremos métodos auxiliares para gestionar las Colas (Queues).

Métodos Auxiliares

Para extraer información adicional de la cola, crearemos 3 métodos auxiliares. El prime método es siEstaVacio()

siEstaVacio()

Este método sencillamente verifica si hay nodos en la cola o no. Devuelve true si hay al menos un nodo en la cola o devuelve false si no hay nodos.


siEstaVacio() {
    return this.length === 0;
}

siEstaVacio() {

return this.length === 0;

}

obtenerPrimerNodo()

Este método devuelve el valor del primer nodo que hay en la cola.


obtenerPrimerNodo() {
    return this.head.value;
}

obtenerPrimerNodo() {

return this.head.value;

}

obtenerCantidadNodos()

Con este método obtenemos el número de nodos en la cola.


obtenerCantidadNodos() {
    return this.length;
}

obtenerCantidadNodos() {

return this.length;

}

Para que sirve las Queues (Colas) y que diferencias tienen con los Arrays ?

La respuesta es la complejidad del tiempo, a continuación comparemos la cola (queue) y el Array usando el símbolo O, en la siguiente tabla:

	Acceso	Buscar	Inserción (al final)	Eliminación (desde el principio)
*Cola (Queue)*	O(n)	O(n)	O(1)	O(1)
*Array*	O(1)	O(n)	O(1)	O(n)

Puedes ver que si queremos eliminar un elemento desde el principio del array, necesitamos hacer n operaciones donde n es el número de elementos en el array, mientras que la Cola (Queue) solo necesita 1 operación para hacer lo mismo.

El problema con un Array es que tiene que mover cada elemento, decrementando cada indice en 1. El código que usa la Cola (Queue), simplemente mueve el enlace del head.

Conclusión

Ya sabes como utilizar los Queues o Colas en JavaScript, tu puedes usarlas cuando creas que sean necesarias, asimismo puedes usar los Arrays cuando los requieras, ambas nos brindan solucione para determinados problemas.

Nota(s)

Los códigos expuestos en este Post pueden quedar obsoletos, ser modificados o continuar en el futuro, esto no depende de mi, si no de los Desarrolladores que dan soporte a JavaScript.
No olvides que debemos usar la Tecnología para hacer cosas Buenas por el Mundo.

Síguenos en nuestras Redes Sociales para que no te pierdas nuestros próximos contenidos.