JavaScript

La Guía Definitiva de Estructuras de Datos en JavaScript: Stacks & Queues

Leira Sánchez
Leira Sánchez

Este es el tercer artículo en la serie sobre entrevistas para ingenieros de Frontend. Si te perdiste los primeros artículos, puedes accederlos aquí:

Pre-requisitos

Cómo correr los ejemplos

Durante este artículo estaré utilizando repl.it para demostrar los ejemplos. Cada ejemplo tendrá un enlace donde podrás correr el código. Además podrás hacerle fork para que experimentes con el algoritmo o añadas notas.

Al entrar a los enlaces de repl.it podrás darle play o Run al algoritmo para ver el resultado. Para ver el código, presiona Show files. Puedes copiarlo a tu cuenta presionando Fork repl.

👉 Recomiendo que intentes construir el algoritmo antes de proceder a mi solución. Puedes hacerlo en repl.it, localmente en tu computadora, o cualquier otro método que te permita correr funciones de JavaScript.

Introducción

Las estructuras de datos son uno de los temas favoritos en las entrevistas para desarrolladores. Son la manera en que organizamos la información en nuestras aplicaciones. Aunque generalmente se asocian con el backend, como desarrolladores frontend es importante saber cómo y cuándo usar cada tipo ya que interactuamos con información todo el tiempo. Encontrarás que algunas estructuras ya las usas a menudo en tu código y que otras, tal vez, son más especializadas. No existe una estructura mejor que las demás. La mejor estructura dependerá de la aplicación.

En esta serie de artículos hablaré sobre algunas de las estructuras más comunes, sus métodos, y ejemplos. Empezaré repasando el tema de clases en Javascript ya que serán la herramienta que utilizaremos para modelar las estructuras.

Stacks y queues son estructuras lineales bien parecidas. La diferencia entre estas es cómo se añaden nuevos elementos a la lista. Cubriremos ambos en este artículo.

Clases

Algunos lenguajes incluyen estas estructuras de datos, pero JavaScript no. Por esto, utilizaremos clases para crear estructuras que podrán ser reutilizadas. Esta no es la única manera de crear estas estructuras, pero como las clases nos permiten crear plantillas de objetos con propiedades y métodos predeterminados he decidido utilizarlas para este artículo.

Aquí les daré una breve introducción a conceptos básicos de clases. La palabra class crea una constante por lo que la clase no podrá ser definida nuevamente. El método para crear nuevos objetos es el constructor .

Ejemplo

En este ejemplo creamos una clase para artículos.

class Article {
constructor(title, author) {
this.title = title;
this.author = author;
}
}

Basados en esta clase, podremos crear artículos que contengan título y autor. Para esto, se utiliza la palabra clave new.

let dataStructuresArticle = new Article("Intro to Data Structures", "Leira Sánchez");
dataStructuresArticle.title; // "Intro to Data Structures"
let sortingAlgorithmsArticle = new Article("Intro to Sorting Algorithms", "Leira Sánchez");
sortingAlgorithmsArticles.title; //"Intro to Sorting Algorithms"

También podemos añadirle funcionalidad a través de métodos. Se le llama método a una función que afecta instancias individuales de una clase. Los métodos de dataStructuresArticles no afectarán a sortingAlgorithmsArticle.

class Article {
constructor(title, author) {
this.title = title;
this.author = author;
this.pageViews = 0;
}
addPageView() {
this.pageViews++;
}

Los métodos en las clases se añaden fuera del constructor y utilizan la misma sintaxis de una declaración de función, pero sin la palabra clave function. Accede a las variables utilizando this.

Añadirle un page view a dataStructuresArticle, no afecta los page views de sortingAlgorithmsArticle.

dataStructuresArticle.addPageView();
console.log(dataStructuresArticle.pageViews); // 1
console.log(sortingAlgorithmsArticle.pageViews); // 0

Stacks

Un stack es una estructura de datos para almacenar listas o colecciones. Lo que lo diferencia de otras es que sólo puedes tomar dos acciones:

  1. añadir elementos al final de la lista
  2. sacar elementos del final de la lista

Esto es conocido como LIFO, por sus siglas en inglés. Last In, First Out quiere decir que el último en entrar, es el primero en salir.

Algunos ejemplos de la vida real pueden ser los siguientes:

  1. Montaña de pancakes - montas pancake sobre pancake y empiezas a comer por el último que montaste
  2. Montaña de sillas - acomodas las sillas una encima de la otra, pero para poder sacar una tienes que sacar la última que pusiste y así sucesivamente

Además, tiene muchas aplicaciones en programación. Un ejemplo discutido en el primer artículo de esta serie es el call stack.

En JavaScript, esta estructura no existe, por lo que comúnmente se utiliza un arreglo en su lugar. Podemos utilizar los métodos de Array.prototype.push() y Array.prototype.pop() para imitar los métodos de un stack. El problema con esto es que los arreglos tienen muchos otros métodos que los stacks no tienen. Sin querer, podemos utilizar esos otros métodos rompiendo las reglas de lo que hace un stack. Vamos a implementar una clase que solo nos permita acceder los métodos que tiene un stack.

class Stack {
constructor() {
this.first = null;
this.last = null;
this.length = 0;
}
}

La clase Stack mantiene récord de los elementos en la primera y en la última posición y del tamaño del stack para garantizarnos un rendimiento de O(1) en cada una de estas acciones. Esta clase modela nuestra lista o colección. Esto es suficiente para crear una instancia de stack, pero no hemos creado los elementos que lo compondrán. Utilizaremos una clase para modelar los elementos a los cuales llamaremos nodes (nodo).

class Node {
constructor(val) {
this.val = val;
this.prev = null;
}
}

Un nodo solo se preocupa por su propio valor y por qué elemento estaba antes de él.

Pseudocode push(val)

  1. Crea un nodo con el valor aceptado por la función
  2. Si es el primer nodo, asígnalo como primero
  3. Si no es el primer nodo, asigna el último nodo como el anterior de este nuevo nodo
  4. Asigna el nuevo nodo como el último
  5. Aumenta el tamaño del stack por 1
push(val) {
// crea un nodo con el valor aceptado por el método
const node = new Node(val);
if (this.length === 0) {
// si es el primer nodo, asígnalo como primero
this.first = node;
} else {
// si no es el primer nodo, asigna el último nodo como el anterior de este nuevo nodo
const last = this.last;
node.prev = last;
}
// asigna el nuevo nodo como el último
this.last = node;
// aumenta el tamaño del stack por 1
this.length++;
// devuelve el nuevo stack
return this;
}

Vamos a crear nuestro primer stack y añadirle algunos nodos.

const stack = new Stack();
stack.push(1));
stack.push(2);
stack.push(3);
console.log(stack.length); // 3

Pseudocode pop()

  1. verifica si hay nodos en el stack, si no hay devuelve null
  2. si hay, guarda el último nodo en una constante
  3. si el stack solo tiene un nodo, re-asigna el primero y el último a null
  4. si tiene más de un nodo, re-asigna el último al anterior al penúlitmo
  5. reduce el tamaño del stack por 1
  6. devuelve el nodo que guardaste en el segundo paso
pop() {
// Verifica si hay nodos en el stack, si no hay devuelve null
if (!this.first) return null;
// Si hay, guarda el último nodo en una constante
const last = this.last;
if (this.length === 1) {
// Si el *stack* solo tiene un nodo, re-asigna el primero y el último a *null*
this.first = null;
this.last = null;
} else {
// Si tiene más de un nodo, re-asigna el último al anterior al penúlitmo
this.last = this.last.prev;
}
// Reduce el tamaño del stack por 1
this.length--;
// Devuelve el nodo que guardaste en el segundo paso
return last;
}

Ahora podemos remover nodos del Stack.

stack.pop(); // 3
console.log(stack.length); // 2

La complejidad de un stack es:

| Acción | Big O |
| --------- | ----- |
| Inserción | O(1) |
| Remoción | O(1) |
| Búsqueda | O(n) |

Como sólo tenemos información sobre los nodos al principio y al final, para buscar un nodo con un valor particular debemos ir nodo por nodo. Hay diferentes maneras de modelar un stack en Javascript. No importa la que escojas, asegúrate que escribirlo para que la complejidad constante para añadir y remover elementos ya que esto es una de las partes más importantes de un stack.

✨ Replit Stacks

Queues

Al igual que en el stack en el queue solo puedes añadir y remover. La diferencia es que en el queue añades al final y remueves del principio. Esto es conocido como FIFO (First In, First Out). El primer elemento en entrar a la lista, es el primero en salir.

Un ejemplo de la vida real es una fila (o cola) en el que el primero en llegar es el primero en ser atendido. En JavaScript, el ejemplo puede ser el event loop que procesa mensajes en orden de llegada.

Para modelar esta estructura en JavaScript utilizaremos los métodos de enqueue(val) y dequeue(). Estos son parecidos a los métodos de arreglos push(val) y unshift(), respectivamente.

La clase de Queue es muy parecida a la de Stack. Lo que cambia son los métodos.

class Queue {
constructor() {
this.first = null;
this.last = null;
this.length = 0;
}
}

La clase de Node para Queue se preocupa por su propio valor y por el nodo que le sigue. El stack se preocupaba por el anterior.

class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}

Pseudocode enqueue(val)

  1. crea un nuevo nodo con el valor aceptado por la función
  2. si el queue está vacío, asigna el nodo al primero y al último
  3. si el queue tiene nodos, asigna el nodo al próximo valor del último nodo
  4. asigna el nodo al último elemento en la lista
  5. aumenta el tamaño del queue por 1
  6. devuelve el queue
enqueue(val) {
// crea un nuevo nodo con el valor aceptado por el método
const node = new Node(val);
// si el queue está vacío, asigna el nodo al primero y al último
if (this.length === 0) {
this.first = node;
this.last = node;
} else {
// si el queue tiene nodos, asigna el nodo al próximo valor del último nodo
this.last.next = node;
// asigna el nodo al último elemento en la lista
this.last = node;
}
// aumenta el tamaño del queue por 1
this.length++;
// devuelve el queue
return this;
}

Pseudocode dequeue()

  1. si el queue está vacío, devuelve null
  2. si tiene nodos, guarda el primero en una constante
  3. si solo tiene un elemento, re-asigna el primero y el último a null
  4. si tiene más de un nodo, re-asigna el primero al segundo elemento
  5. reduce el tamaño del queue por 1
  6. devuelve el nodo que guardaste en el segundo paso
dequeue() {
// si el queue está vacío, devuelve null
if (this.length === 0) return null;
// si tiene nodos, guarda el primero en una constante
const first = this.first;
if (this.length === 1) {
// si solo tiene un elemento, re-asigna el primero y el último a null
this.first = null;
this.last = null;
} else {
// si tiene más de un nodo, re-asigna el primero al segundo elemento
this.first = first.next;
}
// reduce el tamaño del queue por 1
this.length--;
// devuelve el nodo que guardaste en el segundo paso
return first;
}

Ahora podemos crear queues y añadirle y removerle elementos.

const q = new Queue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.dequeue();
console.log(q.length); // 2
q.dequeue();
q.dequeue();
console.log(q.length); // 0
q.dequeue(); // null

La complejidad de un queue es:

| Acción | Complejidad | | --- | --- | | Inserción | O(1) | | Remoción | O(1) | | Búsqueda | O(n) | | Acceso | O(n) |

Como el queue sabe qué nodo está al principio y qué nodo está al final, inserción y remoción son constantes. Sólo hay que cambiar los punteros correspondientes y añadir el nuevo nodo. De igual manera, al tener sólo esta información, para recorrer o encontrar un valor particular, tenemos que visitar cada nodo hasta dar con el que buscamos.

✨ Replit Queue

Conclusión

A la hora de escoger una estructura de datos es importante considerar los requerimientos para escoger la mejor opción. Las estructuras discutidas en este artículo son excelentes cuando necesitas mantener un orden particular, pero solo necesitas acceso en algún extremo. En JavaScript, podrías imitarlas usando un arreglo y sus métodos push(val), pop(), unshift(val), shift(), pero en las últimas dos perderías el beneficio del rendimiento constante que caracteriza a estas estructuras.

En el próximo artículo discutiré otra estructura lineal parecida a estas, linked-lists. También podrías crear stacks y queues utilizando linked-lists, pero JavaScript no tiene ninguna de estas así que es conveniente crear una clase para la que vayas a utilizar.

Recursos

¿Quieres mejorar tus habilidades de frontend?