Stapels

Controleren of de haakjes in {[()()]} goed gepaard zijn vraagt één stapel en 8 pushes en pops, één voor elk haakje.

Laatst erin, eerst eruit

Denk aan een stapel borden. Je legt een schoon bord bovenop en pakt er van bovenaf een als je het nodig hebt. Het laatst toegevoegde bord gaat er het eerst uit. Een stapel is een gegevensstructuur met precies die regel: laatst erin, eerst eruit (LIFO). Er zijn twee hoofdbewerkingen: push legt een waarde bovenop en pop verwijdert de bovenste waarde en geeft haar terug. Veel stapels bieden ook peek, dat de bovenkant bekijkt zonder te verwijderen.

In de MIT-notities van 6.006 is de stapel een speciaal geval van de reeksinterface: insert last(x) en delete last(). Dat vertelt al hoe je er een bouwt. Zet de waarden in een dynamische array en behandel het einde als de bovenkant. In het vorige hoofdstuk was het einde de goedkope kant, dus push en pop kosten elk 1 stap (geamortiseerd, door af en toe kopiëren). De stapelgrootte maakt niets uit. Pop op een stapel met 3 waarden of met 3 miljoen waarden kost dezelfde ene stap.

const stack = [];
stack.push(4);
stack.push(8);
stack.push(5);
console.log(stack.pop());           // 5, the last one pushed
console.log(stack[stack.length - 1]); // peek: 8
console.log(stack.length);          // 2

Haakjes controleren

Een klassieke toepassing van een stapel is controleren of haakjes in balans zijn, iets wat elke code-editor en compiler doet. Lees de tekst van links naar rechts. Elk openingshaakje, (, [ of {, wordt gepusht. Elk sluithaakje moet passen bij de opener bovenop de stapel: zo ja, pop die opener; is de stapel leeg of is de bovenkant een ander soort, dan is de string niet in balans. Aan het einde moet de stapel leeg zijn, anders is een opener nooit gesloten.

Probeer de strings in het lab. {[()()]} vraagt 4 pushes en 4 pops, 8 stappen, en eindigt met een lege stapel. ([)] gaat fout bij het derde teken: de ) komt terwijl [ bovenop ligt. (() bereikt het einde met één ( over. Waarom past een stapel hierbij? Haakjes zijn genest en de laatst geopende moet als eerste sluiten. Dat is laatst erin, eerst eruit.

Waar stapels nog meer voorkomen

• De aanroepstapel. Als functie a b aanroept en b c aanroept, pusht de computer voor elke aanroep een record. Als c terugkeert, wordt dat record gepopt en gaat b verder waar het stopte. Oneindige recursie vult die stapel: de fout ‘stack overflow’.
• Ongedaan maken. Een editor pusht elke wijziging. Ongedaan maken popt de nieuwste wijziging en keert die om.
• Terugknop. Een browser pusht elke pagina die je verlaat; Terug popt de laatste.
• Diepte-eerst zoeken. Bij algoritmen gebruikte je een stapel om in een doolhof zo diep mogelijk te gaan voordat je terugging.