Stacks en JavaScript
Contenido del curso
Stacks en 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
Israel Blas
Elias Rayas Gonzalez
Carina Payleman
Nicolás Felipe Pinto Vega
Joan Alexander Valerio Rodríguez
En la condicional del push:
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; }
Si no me equivoco es innecesarias estas 3 líneas
// y luego hacemos que top apunte al nuevo nodo const holdingPointer = this.top; this.top = newNode; this.top.next = holdingPointer;
Parece ser como una referencia circular, porque this.top apunta a newNode, holdingPointer apunta a this.top, pero ya apunta a newNode. Luego this.top apunta nuevamente a newNode y newNode.next apunta asi mismo, porque holdingPointer apunta a this.top, que a su vez apunta a newNode...
Hola! SÍ son necesarias esas líneas, y no se debe a una razón de código en sí sino a una cuestión técnica del lenguaje. . No se pueden dejar elementos sin pointer (igual que en las linked list), hay que guardar la referencia porque sino el garbage collector de JavaScript va a borrarlo de la memoria. Así lo evitas:
//1. Almacenas el nodo actual que está en el top. const holdingPointer = this.top; //2. Estableces que el top pasará a ser el nodo nuevo. this.top = newNode; //3. El nodo después del nuevo top, será el nodo almacenado en holdingPointer (ex top). this.top.next = holdingPointer;
Si no lo guardas, para el paso 2 el viejo top se habrá borrado para hacerle espacio al nuevo ya que carece de poiner y JS interpreta como que hay que borrarlo.
Creo que el método pop le faltaron lineas de código y en vez de devolver el stack completo, según lo que dice el comentario inicial, deberia devolver el valor del nodo que estaba en la parte superior del stack.
// 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; }
Les comparto un ejemplo un poco mas sencillo:
