Stack (informatica)

Uit Wikipedia, de vrije encyclopedie
Stack met de operaties push en pop.

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

Zie Call stack voor het hoofdartikel over dit onderwerp.

Een zogenoemde call stack wordt gebruikt bij het aanroepen van subroutines in computerprogramma's. De programmateller, die verwijst naar de eerstvolgende uit te voeren instructie, vormt een van de elementen die worden opgeslagen en weer teruggehaald. De stackpointer wijst naar de top van de stack. De stack kan verder worden gebruikt voor lokale variabelen.

Bij het aanroepen van een procedure gebeurt het volgende:

  1. de actuele parameters worden op de stack gezet.
  2. de huidige programmateller wordt erop gezet.
  3. de basepointer (ook wel framepointer genoemd) wordt erop gezet. Deze basepointer wordt gebruikt zodat men weet waar het huidige stackframe begint.
  4. de stackpointer wordt gelijkgesteld aan de basepointer, ze wijzen dus naar hetzelfde element op de stack.
  5. 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:

  1. de stackpointer wordt gelijkgesteld aan de basepointer waardoor alle lokale variabelen worden 'verwijderd' (ze zijn er nog wel, maar zullen later overschreven worden).
  2. de basepointer gaat terug gezet worden naar waar het ervoor op stond (namelijk het begin van het stackframe van de vorige procedure).
  3. 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.

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.

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

Hardwarestack[bewerken | brontekst bewerken]

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 PDP11. De vanouds veel gebruikte IBM 360 heeft nog geen hardwarestack.

Stackgeoriënteerd programmeren[bewerken | brontekst bewerken]

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.