Stack (informatica)

Een stack of stapel is in de informatica een datastructuur voor de opslag van een wisselend aantal elementen, waarvoor geldt dat, net als bij een gewone stapel, het element dat het laatst werd toegevoegd, het eerst weer wordt opgehaald. Dit principe wordt ook wel LIFO (Last In First Out) genoemd.

De tegenhanger van de stack is de queue, die volgens het FIFO (First In First Out) principe werkt.

Datastructuur

De operaties die op een stack kunnen worden toegepast, zijn:

push: legt het meegegeven element op de stapel.
pop: neemt het bovenste element van de stapel af en levert het op.

Andere instructies, exclusief voor een call stack, zijn:

call: de programmateller wordt op de stack gezet en de executie wordt elders voortgezet.
return: pop naar de programmateller. Hierdoor wordt het door call onderbroken programma hervat.

Soms worden nog ondersteund:

isempty of null: levert true op als de stack leeg is en kan dienstdoen als bescherming voor een stack underflow.
top (of peek): levert het bovenste element van de stapel op zonder het er af te halen; kan gesimuleerd worden wanneer de stack door één thread tegelijkertijd wordt gebruikt.

Een stack is te vergelijken met een stapel borden: het laatste bord dat op de stapel is gelegd, wordt er het eerst weer van afgepakt. Een nog betere vergelijking is een stapel zoals in een bordenwagen, waarbij alleen het bovenste element zichtbaar is, en de eventuele rest in het interieur verdwijnt.

Een stack kan geïmplementeerd worden als een gelinkte lijst, of, als de grootte begrensd is, als een array, met een pointer die naar het laatste stackelement wijst.

Bij onjuist gebruik kunnen twee fouten optreden:

Stack underflow: een pop-operatie op een lege stack. Dit had de aanroeper moeten voorzien: het duidt op een programmeerfout.
Stack overflow: een push-operatie op een volle stack.

Stacks bij de uitvoering van programma's

Een zogenoemde call stack wordt gebruikt bij het aanroepen van subroutines in computerprogramma's. Bij het aanroepen van een subroutine wordt onder meer de programmateller, die verwijst naar de eerstvolgende uit te voeren instructie, opgeslagen. Een subroutine kan weer een andere subroutine aanroepen, waardoor er nogmaals data op de call stack gezet wordt. Dit kan meerdere keren gebeuren. Als een subroutine eindigt, wordt de bijhorende data weer van de stack gehaald.

De stack kan verder worden gebruikt voor het opslaan van lokale variabelen en procedureparameters. Een samenhangend blok stackgegevens met returnadres, aanroepparameters en lokale variabelen heet een frame.

De stackpointer wijst naar de top van de stack. De stackpointer is meestal een van de registers van een processor. Bij de Intel x86-architectuur is dit het (E)SP-register. Bewerkingen met registers kosten zeer weinig tijd. Sommige microprocessors hebben verschillende stackpointers.

Stap voor stap

Bij het aanroepen van een procedure gebeurt het volgende:

de actuele parameters worden op de stack gezet.
de huidige programmateller wordt erop gezet.
de basepointer (ook wel framepointer genoemd) wordt erop gezet. Deze basepointer wordt gebruikt zodat men weet waar het huidige stackframe begint.
de stackpointer wordt gelijkgesteld aan de basepointer, ze wijzen dus naar hetzelfde element op de stack.
er wordt geheugen vrijgemaakt (stackruimte) voor de lokale variabelen. Dit gebeurt door de stackpointer te verplaatsen.

Na het uitvoeren van de procedure zal het volgende gebeuren:

de stackpointer wordt gelijkgesteld aan de basepointer waardoor alle lokale variabelen worden 'verwijderd' (ze zijn er nog wel, maar zullen later overschreven worden).
de basepointer gaat teruggezet worden naar waar het ervoor op stond (namelijk het begin van het stackframe van de vorige procedure).
de oude waarde van de programmateller (het returnadres) wordt van de stack gehaald en de uitvoering gaat daar verder.

Een schema van de stack nadat een procedure DrawSquare() een procedure DrawLine() heeft aangeroepen.

Hardwarestack

Moderne processoren zijn steeds voorzien van een hardwarestack, wat betekent dat een deel van het geheugen voor de stack gereserveerd kan worden en dat er instructies bestaan voor het bedienen van de stack. De hardwarestack komt reeds voor op de PDP-11. De vanouds veel gebruikte IBM 360 had nog geen hardwarestack.

Stackgeoriënteerd programmeren

Bij stackgeoriënteerd programmeren bevindt een programma zich als geheel op een stapel. Uitvoering gebeurt als volgt:

haal het bovenste element van de stapel, dat geacht wordt een functie (operatie) te zijn;
bepaal het aantal argumenten dat de functie verwacht en haal ook die van de stapel;
voer de functie uit op de (0 of meer) argumenten;
plaats het functieresultaat, als dat er is, bovenop de stapel;
herhaal deze stappen tot de stapel leeg is, een fout optreedt, of een speciale functie wordt uitgevoerd die opdraagt om uitvoering te stoppen.

Het is gebruikelijk om dergelijke programma's weer te geven door de stapelinhoud te noteren van bodem tot top, wat betekent dat alle bewerkingen in omgekeerde Poolse notatie genoteerd zijn (Engels: Reverse Polish Notation, RPN).

Veel wetenschappelijke zakrekenmachines maken gebruik van deze techniek en manier van noteren, en ook programmeertalen zoals Forth en PostScript.

Er worden nog steeds microprocessoren gemaakt met een stackgeoriënteerde instructieset, bijvoorbeeld de ST20 van ST Microelectronics. Door hun eenvoud zijn meerdere kernen per chip realiseerbaar en dit blijkt op te wegen tegen de hogere kloksnelheid die met een registerarchitectuur mogelijk is.