← Estructuras de datos desde cero · Lección 7/32
Pilas: el último en entrar sale primero
Sólo por arriba
Una pila (*stack*) sólo deja hacer tres cosas, y todas por arriba:
- push: poner algo encima.
- pop: quitar lo de encima.
- peek (o *top*): mirar lo de encima sin quitarlo.
El último que entra es el primero que sale: LIFO (*last in, first out*). Un arreglo de JavaScript ya es una pila si sólo usas push y pop por el final, y las dos cuestan O(1).
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
Entraron 1, 2, 3 y salieron 3, 2: al revés. Al final sólo queda el «plato 1», el primero que se puso.
Toda la lección en una página
Sólo por arriba
Una pila (*stack*) sólo deja hacer tres cosas, y todas por arriba:
- push: poner algo encima.
- pop: quitar lo de encima.
- peek (o *top*): mirar lo de encima sin quitarlo.
El último que entra es el primero que sale: LIFO (*last in, first out*). Un arreglo de JavaScript ya es una pila si sólo usas push y pop por el final, y las dos cuestan O(1).
const platos = [];
platos.push("plato 1");
platos.push("plato 2");
platos.push("plato 3");
console.log(platos);
console.log(platos[platos.length - 1]); // peek: mirar el de arriba
console.log(platos.pop()); // sale el último que entró
console.log(platos.pop());
console.log(platos);
Entraron 1, 2, 3 y salieron 3, 2: al revés. Al final sólo queda el «plato 1», el primero que se puso.
Una clase Pila, y el botón de deshacer
Envolver el arreglo en una clase sirve para prometer que nadie va a meter la mano por en medio: la pila sólo ofrece lo que una pila ofrece.
El botón de deshacer de cualquier editor es una pila: cada cambio se apila, y deshacer saca el más reciente. Por eso deshaces en el orden contrario al que escribiste.
class Pila {
constructor() { this.datos = []; }
push(x) { this.datos.push(x); }
pop() { return this.datos.pop(); }
peek() { return this.datos[this.datos.length - 1]; }
get vacia() { return this.datos.length === 0; }
}
let texto = "";
const historial = new Pila();
function escribir(s) { historial.push(texto); texto += s; }
function deshacer() { if (!historial.vacia) texto = historial.pop(); }
escribir("Hola");
escribir(", Sahuayo");
escribir("!!!");
console.log(texto);
deshacer();
console.log(texto);
deshacer();
console.log(texto);
Antes de cada cambio se apila cómo estaba el texto. Deshacer saca el estado más reciente: primero se van los «!!!» y luego «, Sahuayo».
Paréntesis que cierran bien
¿Está bien cerrado ([{}])? ¿Y ([)]? Una pila lo resuelve de una pasada: cada vez que abre algo, lo apilas; cada vez que cierra, lo de arriba de la pila tiene que ser su pareja. Al final, la pila debe quedar vacía.
Es exactamente lo que hace un compilador para avisarte que te faltó una llave. Y la computadora misma usa una pila para recordar qué función llamó a cuál: la pila de llamadas, que vas a ver en la unidad de recursión.
function balanceado(s) {
const pareja = { ")": "(", "]": "[", "}": "{" };
const pila = [];
for (const c of s) {
if (c === "(" || c === "[" || c === "{") pila.push(c);
else if (c in pareja) {
if (pila.pop() !== pareja[c]) return false; // no cierra lo último que abrió
}
}
return pila.length === 0; // ¿quedó algo abierto?
}
for (const s of ["([{}])", "([)]", "((", "f(a[0]) { }"]) {
console.log(s, "->", balanceado(s));
}
([)]falla en el): arriba de la pila hay un[.((no falla en ningún cierre, pero termina con dos abiertos:false.- Las letras y los números se ignoran: sólo cuentan los signos.