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).

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 🤕).

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

Cuando usar 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).

Complejidad de espacio

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

Complejidad de tiempo

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(n)
  • 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?

Alternativa 1: Usando un array

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).

Alternativa 2: Usando un objeto

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.

Constructor de una pila implementada con un objeto

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

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 en vez de para ubicar la posición del elemento a mostrar o devolver el largo de la pila, respectivamente.

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.

Podemos disminuir this.count al inicio, o ubicar el elemento con y reducirlo al final.

La implementación completa queda de esta forma:

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.

Thanks to Cristofer

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