Stacks en JavaScript
Clase 89 de 99 • 30 días de JavaScript
Contenido del curso
Clase 89 de 99 • 30 días de JavaScript
Contenido del curso
Un stack (o pila) es una estructura de datos lineal que utiliza el principio "último en entrar, primero en salir" (Last In, First Out, LIFO). Esto significa que el último elemento agregado al stack será el primer elemento en ser eliminado.
En JavaScript, un stack puede ser implementado utilizando un array, un objeto o creándola desde 0. Cuando se utiliza un array, se agregan y eliminan elementos utilizando los métodos push() y pop(), respectivamente. Cuando se utiliza un objeto, se agregan y eliminan propiedades utilizando los métodos Object.keys() y delete. En esta clase aprenderás a como sería un stack creado por ti.
Un ejemplo de uso de un stack en JavaScript podría ser para implementar el sistema de navegación hacia atrás en un navegador web. Cada vez que el usuario navega a una nueva página, se agrega la URL de la página actual al stack. Cuando el usuario presiona el botón de "atrás", se elimina la última URL agregada del stack y se navega hacia esa página.
Complejidad algorítmica
La complejidad de los métodos de un stack en JavaScript depende de la implementación utilizada. Si se utiliza un array, la complejidad es la siguiente:
| Algoritmo | Big O notation |
|---|---|
| Agregar un elemento (push) | O(1) |
| Eliminar un elemento (pop) | O(1) |
| Acceder al último elemento | O(1) |
| Acceder a un elemento en una posición específica | O(1) |
Si se utiliza un objeto, la complejidad es la siguiente:
| Algoritmo | Big O notation |
|---|---|
| Agregar un elemento | O(1) |
| Eliminar un elemento | O(1) |
| Acceder al último elemento | O(n) |
| Acceder a un elemento en una posición específica | O(n) |
En general, se recomienda utilizar un array para implementar un stack en JavaScript, ya que tiene mejor rendimiento para todas las operaciones.
Oportunidades donde puedes usar un stack
Algunas situaciones en las que puede ser útil utilizar un stack en JavaScript son:
Situaciones en las que NO es muy conveniente usar un stack
Algunas situaciones en las que no es recomendable utilizar un stack en JavaScript son:
Construyamos un stack
Para implementar un stack en JavaScript, podemos usar un array y sus métodos push y pop para agregar y eliminar elementos. Sin embargo, si queremos implementar un stack de una manera más “nativa”, podemos hacer lo siguiente.
// Creamos una clase Node que representa un nodo en el stack class Node { constructor(value) { this.value = value; this.next = null; } } class Stack { constructor() { // Definimos dentro del constructor lo que va primero // y lo que va al final this.top = null; this.bottom = null; this.length = 0; } // El método push agrega un nuevo nodo en la parte superior del stack push(value) { const newNode = new Node(value); // Si el stack está vacío, simplemente asignamos el nuevo nodo a top // y al nodo bottom if (this.length === 0) { this.top = newNode; this.bottom = newNode; } else { // Si el stack no está vacío // hacemos que el nuevo nodo apunte al nodo que estaba en la parte superior // del stack newNode.next = this.top; this.top = newNode; // y luego hacemos que top apunte al nuevo nodo const holdingPointer = this.top; this.top = newNode; this.top.next = holdingPointer; } this.length++; return this } // El método pop elimina y devuelve el valor del nodo // en la parte superior del stack pop() { // Si el stack está vacío, devolvemos null if (!this.top) { return null; } if (this.top === this.bottom) { this.bottom = null; } // Si el stack no está vacío, guardamos el valor del nodo en la parte // superior en una variable // hacemos que top apunte al siguiente nodo en el stack // y luego devolvemos el stack. this.top = this.top.next; this.length--; return this; } // El método peek devuelve el valor del nodo en la parte superior del stack // sin eliminarlo. Si el stack está vacío, devuelve null. peek() { return this.top ? this.top.value : null; } // El método isEmpty devuelve true si el stack está vacío // y false en caso contrario. isEmpty() { return this.length === 0; } }
Todo esto y más lo puedes aprender en el Curso de Estructuras de Datos con JavaScript
