Jun 15, 2018
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).
¿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 🤕).
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(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?
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.
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.
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.
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.
this.count-1 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.
