A. La Evolución del Almacenamiento
¿Cómo pasamos de los arreglos estáticos de tamaño fijo en los años 70 a los arreglos dinámicos y colecciones de objetos en la web moderna?
La evolución pasó de arreglos estáticos de tamaño fijo (años 70) a colecciones modernas mediante la gestión automática de memoria y abstracciones de alto nivel. Los arreglos dinámicos duplicaban su espacio al llenarse, mientras que lenguajes modernos introdujeron estructuras flexibles (ArrayList, Lists) que manejan objetos complejos, facilitando la manipulación de datos en la web actual.
- Años 70 - Arreglos Estáticos: Definidos con tamaño fijo, los arreglos requerían asignar memoria al inicio, limitando la flexibilidad y causando ineficiencia si el tamaño era desconocido.
- Gestión Dinámica: Para resolver esto, los arreglos dinámicos (como
std::vectoren C++ oArrayListen Java) permiten cambiar de tamaño au - Colecciones de Objetos: La Programación Orientada a Objetos (POO) permitió agrupar no solo datos primitivos, sino objetos complejos. Las "colecciones" modernas (como las listas en JavaScript o Java) facilitan añadir, eliminar y manipular estos objetos de forma eficiente.
- tomáticamente. Cuando se llena, el sistema crea una copia más grande (generalmente duplicando el tamaño) en una nueva ubicación de memoria.
- Web Moderna: Hoy, los arreglos se gestionan dinámicamente en el navegador o servidor, permitiendo estructuras de datos flexibles y eficientes adaptadas a las necesidades de aplicaciones web dinámicas.
¿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.
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.
- Call Stack (Pila de llamadas): Ejecuta el código síncrono. Si está vacío, el Event Loop actúa.
- Call Stack (Pila de llamadas): Ejecuta el código síncrono. Si está vacío, el Event Loop actúa.
- Microtask Queue (Cola de microtareas): Alta prioridad. Incluye callbacks de promesas (
.then/catch)queueMicrotask, yasync/await. Se ejecutan inmediatamente después del Call Stack vacío. - Task Queue / Callback Queue (Cola de macrotareas): Menor prioridad. Incluye
setTimeout``setInterval, y eventos de usuario (clics, DOM). - Event Loop: Supervisa continuamente el Call Stack y las colas. Mueve la primera tarea de la cola al stack para su ejecución cuando este está vacío, priorizando siempre la Microtask Queue.
- Se vacía el Call Stack.
- El Event Loop ejecuta todas las microtareas de la Microtask Queue.
- El Event Loop ejecuta una macrotarea de la Task Queue.
- Se repite el proceso
- API web : Proporcionan funciones del navegador como
setTimeouteventos DOM y solicitudes HTTP. Estas API gestionan operaciones asincrónicas. - Cola de tareas (Cola de devolución de llamadas) : Almacena tareas que esperan ser ejecutadas después de que la pila de llamadas se vacíe. Estas tareas se ponen en cola mediante
setTimeout,setIntervalu otras API. - Cola de microtareas : Una cola de mayor prioridad para promesas y
MutationObserverdevoluciones de llamadas. Las microtareas se ejecutan antes que las tareas de la cola de tareas. - Bucle de eventos : verifica continuamente si la pila de llamadas está vacía y envía tareas desde la cola de microtareas o la cola de tareas a la pila de llamadas para su ejecución.
Cómo funciona (simplificado con una analogía):
- JavaScript ejecuta el código línea por línea en un solo hilo (como seguir una receta). Esto se llamapila de llamadas.
- Tareas en espera (Eventos): Algunas tareas requieren tiempo (p. ej., obtener datos de internet, temporizadores). En lugar de bloquear el progreso, estas tareas se envían a una cola de espera (conocida como cola de eventos ).
- El administrador (bucle de eventos): El bucle de eventos verifica constantemente:
- ¿La tarea principal (pila de llamadas) está vacía?
- ¿Hay tareas esperando en la cola?
Si es así, selecciona una tarea de la cola y la mueve a la pila para su ejecución.
Tipos de tareas en JavaScript
- Tareas sincrónicas : se ejecutan inmediatamente en la pila de llamadas (por ejemplo, llamadas de funciones, declaraciones de variables).
- Microtareas : tareas asincrónicas de alta prioridad, como
Promisedevoluciones de llamadas yqueueMicrotask. - Macrotareas : tareas asincrónicas de menor prioridad, como
setTimeout,setInterval, y eventos DOM.
- Nodos como Nodos de Lista Enlazada: Cada nodo en el DOM es un objeto que actúa como un nodo de una lista, conteniendo datos (el tipo de elemento, su valor) y punteros (referencias) al siguiente elemento en el árbol.
- Relaciones de Nodos (Lista Enlazada):
nextSibling(siguiente hermano): Puntero al nodo siguiente.previousSibling(hermano anterior): Puntero al nodo anterior.parentNode(padre): Puntero hacia arriba en la jerarquía.childNodes(hijos): A menudo implementado como una lista de nodos, permitiendo recorrer la jerarquía de forma similar a una lista enlazada.
- Estructura Dinámica: Al igual que las listas enlazadas, el DOM permite añadir, eliminar o modificar nodos (elementos, atributos, estilos) de manera eficiente en tiempo real sin tener que reestructurar todo el documento en memoria.
- Acceso y Manipulación: Los métodos como
getElementByIdoquerySelectoracceden a estos nodos, permitiendo a JavaScript navegar por la estructura de "punteros" para cambiar el contenido de la página
Cómo funciona el DOM en JavaScript
La mayor utilidad del DOM se da en el ámbito de la programación en JavaScript. Como hemos dicho, es el mecanismo que nos permite acceder, modificar y reaccionar a las acciones del usuario dentro de la página web.
Acceso al DOM desde JavaScript: seleccionar elementos y nodos
El lenguaje de programación JavaScript nos ofrece diferentes formas de acceder a los elementos del DOM. Los métodos más utilizados son:
- getElementById(): Selecciona un elemento por su ID (atributo id de la etiqueta HTML).
- querySelector() y querySelectorAll(): Seleccionan elementos usando selectores CSS, lo que permite una mayor flexibilidad y potencia de selección.
