Estructuras de datos con JavaScript — Parte 2: Colas (Queues)

Continuando con esta (no tan) mágica aventura sobre estructuras de datos en JavaScript, ¡hoy ha llegado el momento de hablar de Colas!.

Que son, para que sirven y como implementarlas, después de la imagen.

Photo by Levi Jones on Unsplash

Este artículo es parte de una serie que estamos haciendo sobre estructuras de datos en JavaScript. Puedes ver el anterior en este enlace:

Estructuras de datos con JavaScript — Parte 1: Pilas (Stacks)

¿Qué es una cola?

Una cola es una estructura de datos muy similar a una Pila, es decir, también opera de forma lineal y unidireccional (se agregan elementos de inicio a fin). La gran diferencia radica en la forma en que estos elementos son sacados después. Cuando usamos una Pila, ésta opera con una modalidad LIFO (Last In First Out), mientras que con una Cola es FIFO (First In First Out), es decir, siempre el primer elemento que agreguemos, será el primero que saquemos de ella.

La analogía más usada para entender el funcionamiento de una cola es, precisamente, la cola del supermercado o del banco, en la cual la persona que está al inicio de la cola, es la primera en ser atendida.

Representación (casi) gráfica de una cola

Cuándo usar una cola

Dos de los usos más comunes de colas hoy en día están presentes en herramientas y procesos que vemos a diario: colas de tareas o trabajos (jobs), como por ejemplo Resque, Sidekiq o Kue, y colas de mensajería. En ambos casos, es necesario que los primeros datos que ingresen sean los primeros en salir y estén ordenados de forma cronológica y por orden de llegada.

Complejidad de una cola

Las complejidades de una cola son prácticamente las mismas que una implementación de pilas:

Complejidad de Tiempo

  • Acceso: O(n)
  • Búsqueda: O(n)
  • Inserción: O(1)
  • Borrado: O(1)

Complejidad de Espacio (en memoria): O(n).

Métodos de una cola

Para poder operar correctamente sobre una cola, es necesario contar con métodos que permitan: agregar elementos, sacar elementos, mostrar elementos (el siguiente o la cola completa) y retornar el tamaño. Al igual que con las pilas, si bien al hacer una implementación propia podemos llamar estos métodos de cualquier manera, por lo general se opta por la siguiente convención:

  • enqueue: Agrega un nuevo elemento a la cola, situándolo al final de ésta.
  • dequeue: Retorna el primer elemento de la cola, quitándolo de ésta.
  • peek: Retorna el primer elemento de la cola, sin quitarlo de ésta.
  • size: Retorna el número de elementos que contiene la cola.
  • print: Muestra el contenido de la cola.

Opcionalmente, algunas implementaciones incluyen un método llamado isEmpty, que retorna true/false dependiendo si la cola está vacía. De no existir, esto se puede inferir al llamar a size.

¿Cómo implementar una cola?

La forma más rápida y directa de implementar una cola en JavaScript es usando un Array. La mayoría de los métodos que necesitamos utilizar ya vienen incluidos en su prototipo, por lo que solo es necesario llamarlos y retornar el valor correspondiente.

El único método que es necesario implementar manualmente es peek, para lo cual ubicaremos el primer elemento del array (de índice 0) y lo retornaremos cuando sea llamado.

Código Fuente

El código fuente de este ejemplo pueden encontrarlo acá: https://github.com/Xabadu/js-data-structures

Noders es la comunidad más electrizante de Node.js y JavaScript de Latinoamérica. Generamos iniciativas de aprendizaje e integración de comunidades de desarrollo en diferentes países y a lo largo y ancho de esta cosita llamada la Internet.

Si quieres saber más de nosotros y/o participar de lo que hacemos, únete a nuestro Slack.

Gracias a Cristofer y Maximiliano Castro por las revisiones de este artículo.

NodersJS

¿Por qué? Porque nos gusta.

Fernando Larrañaga

Written by

The stylin’, profilin’, UI buildin’, Web codin’, community leadin’, son of a gun! Developer Evangelist 🥑 at Twilio ☎️ — Organizer NodeSchool San Francisco.

NodersJS

NodersJS

¿Por qué? Porque nos gusta.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade