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

¡Estructuras de datos! — Antes de que panda el cúnico y empecemos a correr en círculos, acompáñennos en esta (no tan) mágica aventura para descifrar los más ocultos misterios de las estructuras de datos en JavaScript: Que son, para que sirven, y lo más importante, como implementarlas.

El detalle, como siempre, después del salto (o en este caso, la imagen).

Image for post
Image for post
The Rock, y amigos.

¿Qué es una pila?

Una pila es una estructura para almacenar datos que opera de forma lineal y unidireccional. Esto significa que solo hay una forma para agregar elementos y estos se incorporan en un orden determinado en una sola dirección (de inicio a fin).

Las pilas operan bajo una modalidad llamada LIFO (Last In First Out). Esto quiere decir, que siempre el último elemento agregado va a ser el primero que saquemos.

Una analogía similar, y bastante usada para describir pilas, es pensar en una torre de platos (o piedras, como la imagen de arriba). Siempre el plato que ponemos más arriba (el último), es el primero que sacamos. (Podemos sacar uno de al medio también, pero ahí es donde se caen, se rompen, y viene la chancla voladora 🤕).

Image for post
Image for post
Representación (casi) gráfica de una pila

Hay varios ejemplos prácticos en donde hoy se utilizan pilas, y que probablemente usamos a diario. De hecho, para llegar a este artículo, hacemos uso de una de las pilas más usadas: el historial de nuestro navegador Web. Cada nueva página que visitamos se monta encima de la anterior y van generando una pila de registros, sobre los que podemos ir retrocediendo uno a uno (con el botón back del navegador).

Adicionalmente, las pilas son útiles cuando necesitamos una estructura de dato que terminaremos desplegando de forma cronológica de más a menos recientes (como por ejemplo una lista de últimos tweets o artículos). En este caso, el dato ingresado más recientemente es el primero que sacaremos y mostraremos.

Complejidad de una pila

Dependiendo el tipo de implementación de la pila (con un array o un objeto), hay distintos niveles de complejidad asociados, tanto para espacio (espacio en memoria que usará la pila), como en tiempo (tiempo que tomará ejecutar acciones sobre ella: acceso, búsqueda, inserción y borrado).

(Nota: Consideramos n = número de elementos en la estructura, 1 = acceso directo).

  • Array: O(n).
  • Objeto: O(n).

Para ambos casos la complejidad de espacio será O(n), o sea, será lineal y equivalente al número de elementos que esta contenga.

Para una implementación usando arrays:

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

Por otro lado, usando objetos:

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

Métodos de una pila

Tradicionalmente, una pila debe contar con métodos que permitan: agregar nuevos elementos, sacarlos y revisarlos (uno o más). Si bien al hacer una implementación propia, podemos llamar a estos métodos de cualquier forma, existe una convención acordada de usar las siguientes definiciones:

  • push: Agrega un nuevo valor a la pila, ubicándolo al final de ésta.
  • pop: Retorna el último valor ingresado a la pila, sacándolo de ésta.
  • peek: Retorna el último valor ingresado a la pila, sin sacarlo de ésta.
  • size: Retorna el número de elementos que contiene la pila.
  • print: Muestra el contenido de la pila.

¿Cómo implementar una Pila?

Implementar una pila usando un array en JavaScript es relativamente rápido, ya que la mayoría de los métodos necesarios vienen incluidos en el prototipo de Array, por lo que podemos hacer una implementación que solo se encargue de llamarlos y retornar el valor.

El único método que habría que implementar manualmente es peek, para lo cual retornamos el último valor del array. Y este valor podemos sacarlo usando el largo del array (Array.length) menos uno como índice para buscarlo (considerando que el array es indexado desde 0 y el largo empieza a contar desde 1).

Image for post
Image for post

La implementación de una pila mediante un objeto requiere un poco más de trabajo, ya que todos los métodos que vienen incluidos para los arrays en JS no los tenemos acá, así que es necesario implementarlos de forma manual.

Una de las formas de hacer esto es, al momento de crear la pila, declarar un contador que podemos usar para seguir la posición actual y número de elementos que hemos ido agregando. Como el comportamiento por defecto de una pila no implica saber nada más que el siguiente elemento a sacar/último que agregamos, mientras vayamos corriendo el contador para igualar el total de elementos que tenemos, podemos revisarlos, sacarlos y saber cuantos tenemos en cualquier momento.

Image for post
Image for post
Constructor de una pila implementada con un objeto

Para agregar elementos, usamos this.count como referencia de la posición actual y la notación de corchetes de objetos en JavaScript para hacer una asignación directa.

Image for post
Image for post
Agregando un elemento

En el caso de peek, print y size, la implementación es prácticamente la misma que en el caso anterior. La única diferencia notable es usar this.count en vez de Array.length para ubicar la posición del elemento a mostrar o devolver el largo de la pila, respectivamente.

Image for post
Image for post
peek, size y print

Finalmente, para el caso de pop, si es necesario modificar un poco la implementación. La gran diferencia radica en que, después de devolver el elemento, debemos borrarlo del objeto. De esta forma, reducimos el tamaño en memoria que usa, y por ende, su complejidad de espacio.

Image for post
Image for post
Podemos disminuir this.count al inicio, o ubicar el elemento con this.count-1 y reducirlo al final.

La implementación completa queda de esta forma:

Image for post
Image for post

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.

NodersJS

¿Por qué? Porque nos gusta.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store