Colas (queues) en JavaScript
Una cola (queue en inglés) es una estructura de datos compuesta por una serie de elementos donde insertamos data al final de la serie, y retiramos data por el frente.
Es lo que llamamos una estructura FIFO (First In, First Out). Usamos colas para varias cosas, ordenar operaciones, la cola de impresión, y el clásico ejemplo de una cola en la ventanilla de un banco.
Nota: Cómo se pronuncia Queue
Por si tienes la duda, te dejo una grabación de cómo lo pronuncia google search:
Métodos
En principio las colas o queues tienen dos métodos importantes:
enqueue: Traducido como “encolar”, es el método que debe agregar un elemento a la cola.dequeue: Traducido como “desencolar” (Nota: suena mal, no lo digas así, no, no lo pienses). Este método retira el primer elemento de la cola.
Aunque hay otros métodos auxiliares que te pueden ser de mucha utilidad:
isEmpty: indica si la cola esta vacía.front: nos permite conocer el primer elemento agregado, es decir, el primer elemento de la cola. En algunos casos, nos permite obtener el valor del primer elemento, pero siempre, sin retirar el elemento de la cola.back: nos permite conocer el último elemento de la cola, es decir, el último en ser agregado. En algunos casos, nos permite obtener el valor, pero siempre, sin retirar el elemento de la cola.
Puedes ver una cola en acción en la siguiente demo:
En la demo, se implementa y usa una cola. Para este caso se implementan otros métodos como print, que no son propios de las colas en general, sino un detalle de implementación de este ejemplo en particular.
El código tiene una implementación como la que sigue:
Nota: arguments
Notarás que en la demo, la primera línea dentro del constructor Queue es como sigue:
this.dataStore = Array.prototype.slice.call(arguments, 0);
Espero que te estés preguntando ¿De dónde salió ese arguments? ¿Qué es eso del Array.prototype.slice.call ?
arguments: Es un objeto que viene construido en JavaScript, o también llamados built-in objects. El objeto arguments es un objeto iterable (se comporta como un array pero no es un array) que corresponde a los argumentos pasados a una función. Puedes leer más de arguments en la documentación. Por lo general se usa para funciones que pueden recibir varios valores como parámetros. En sí, no es un array, pero podemos convertirlo en un array, ahí es donde entra la parte de Array.prototype.slice.call, que es una de las formas en que podemos convertirlo.
Priority Queue
Si investigas un poco más de teoría de colas, encontrarás algo llamado Priority Queue o Cola de Prioridad. Estas colas se implementan igual que las colas que vimos anteriormente, pero con algunas diferencias importantes.
enqueue: se agrega un elemento y su prioridad. Esta operación tiene una complejidad asintótica de O(1).dequeue: se retira el primer elemento de mayor prioridad. Esta operación tiene una complejidad asintótica de O(n) ya que se debe buscar el elemento de mayor prioridad.
Si quieres conocer más de complejidad asintótica puede revisar el post de Algoritmos y notación asintótica de Lupo Montero.
En la siguiente demo puedes ver como funciona la cola de prioridad en una cola de pacientes, en donde la mayor prioridad esta dada por el menor número, en este caso 1, luego en prioridad siguen 2, 3, 4 y 5 respectivamente:
Puedes ver la implementación del PriorityQueue aquí:
En el caso de esta implementación, pueden ver la parte del dequeue:
Como puedes leer en el código, se busca en el dataStore el primer elemento de menor índice en prioridad. Ese es el elemento que se devuelve. Y el queue se queda con los elementos restantes.
PD: mi primer post, se acepa feedback :)
