Pilas

Comprobar que los paréntesis de {[()()]} se emparejan bien lleva una pila y 8 push y pop, uno por cada símbolo.

El último en entrar, el primero en salir

Piensa en una pila de platos. Pones un plato limpio encima y, cuando necesitas uno, lo tomas de arriba. El plato que pusiste al final es el primero en salir. Una pila es una estructura de datos con exactamente esa regla, llamada último en entrar, primero en salir (LIFO, por sus siglas en inglés). Ofrece dos operaciones principales: push pone un valor encima, y pop quita el valor de arriba y lo devuelve. Muchas pilas también ofrecen peek, que mira el valor de arriba sin quitarlo.

En las notas del 6.006 del MIT, la pila es un caso particular de la interfaz de secuencia: insert last(x) y delete last(). Eso ya te dice cómo construir una. Pon los valores en un arreglo dinámico y trata el final del arreglo como la cima. En la unidad anterior, el final era el extremo barato, así que push y pop cuestan 1 paso cada uno (amortizado, por la copia ocasional). El tamaño de la pila no importa. Hacer pop en una pila de 3 valores o de 3 millones es el mismo paso único.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, el último que entró
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Comprobar paréntesis

Un uso clásico de la pila es comprobar que los paréntesis estén equilibrados, algo que hacen todos los editores de código y compiladores. Lee el texto de izquierda a derecha. Cada símbolo de apertura, (, [ o {, se mete en la pila. Cada símbolo de cierre debe coincidir con el de apertura que está en la cima: si coincide, se saca ese símbolo de apertura; si la pila está vacía o el de arriba es de otro tipo, la cadena no está equilibrada. Al final la pila debe quedar vacía; si no, algún símbolo de apertura nunca se cerró.

Prueba las cadenas en el laboratorio. {[()()]} necesita 4 push y 4 pop, 8 pasos, y termina con la pila vacía. ([)] falla en el tercer carácter: el ) llega cuando [ está en la cima. (() llega hasta el final con un ( de sobra. ¿Por qué una pila sirve para esto? Los paréntesis se anidan, y el que se abrió más recientemente debe ser el primero en cerrarse. Eso es último en entrar, primero en salir.

Dónde más aparecen las pilas

• La pila de llamadas. Cuando la función a llama a b y b llama a c, la computadora apila un registro por cada llamada. Cuando c termina, su registro se saca y b continúa donde se había quedado. Una recursión infinita llena esta pila, y ese es el error de "desbordamiento de pila" (stack overflow).
• Deshacer. Un editor apila cada cambio. Deshacer saca el cambio más reciente y lo revierte.
• El botón Atrás. Un navegador apila cada página que dejas; Atrás saca la última.
• Búsqueda en profundidad. El curso de algoritmos usó una pila para llegar lo más hondo posible en un laberinto antes de retroceder.