Stacks en JavaScript

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:

• Cuando se requiere mantener un historial de acciones o estados anteriores y se desea navegar hacia atrás en ese historial en orden inverso a como se agregaron las acciones o estados.
• Cuando se desea realizar un seguimiento de la posición de la ejecución de un programa, por ejemplo, para implementar una función de "deshacer" (undo).
• Cuando se necesita implementar una estructura de datos temporal para almacenar datos mientras se resuelve un problema, por ejemplo, en la implementación de un algoritmo de búsqueda o recorrido de árboles.

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:

• Cuando se requiere acceder a elementos en posiciones arbitrarias de la estructura de datos, ya que esto no es posible con un stack.
• Cuando se necesita acceder a elementos específicos de la estructura de datos de manera eficiente, ya que la complejidad de acceso a un elemento en una posición específica es O(n) si se utiliza un objeto como implementación.
• Cuando se requiere realizar búsquedas o filtrados complejos en los datos almacenados en la estructura, ya que no hay una manera eficiente de hacerlo en un stack. En estos casos, es mejor utilizar otras estructuras de datos.

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