← Data structures from scratch · Lesson 7/32
Stacks: last in, first out
Only from the top
A stack only lets you do three things, all from the top:
- push: put something on top.
- pop: take the top thing off.
- peek (or *top*): look at the top without removing it.
The last one in is the first one out: LIFO. A JavaScript array is already a stack if you only use push and pop at the end, and both cost O(1).
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
In went 1, 2, 3 and out came 3, 2: reversed. In the end only "plato 1" is left, the first one placed.
The whole lesson on one page
Only from the top
A stack only lets you do three things, all from the top:
- push: put something on top.
- pop: take the top thing off.
- peek (or *top*): look at the top without removing it.
The last one in is the first one out: LIFO. A JavaScript array is already a stack if you only use push and pop at the end, and both cost 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: look at the top
console.log(platos.pop()); // the last one in comes out
console.log(platos.pop());
console.log(platos);
In went 1, 2, 3 and out came 3, 2: reversed. In the end only "plato 1" is left, the first one placed.
A Pila class, and the undo button
Wrapping the array in a class is a way of promising nobody will reach into the middle: the stack only offers what a stack offers.
The undo button in any editor is a stack: each change gets pushed, and undo pops the most recent one. That's why you undo in the opposite order from how you typed.
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);
Before each change, the text as it was gets pushed. Undo pops the most recent state: first the "!!!" goes, then ", Sahuayo".
Parentheses that close properly
Is ([{}]) properly closed? What about ([)]? A stack solves it in one pass: every time something opens, push it; every time something closes, the top of the stack must be its partner. At the end, the stack must be empty.
That's exactly how a compiler tells you a brace is missing. And the computer itself uses a stack to remember which function called which: the call stack, which you'll meet in the recursion unit.
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; // doesn't close the last opener
}
}
return pila.length === 0; // anything left open?
}
for (const s of ["([{}])", "([)]", "((", "f(a[0]) { }"]) {
console.log(s, "->", balanceado(s));
}
([)]fails at the): the top of the stack is a[.((never fails on a close, but ends with two still open:false.- Letters and digits are ignored: only the brackets count.