Stack (informatica)
Uit Wikipedia, de vrije encyclopedie
Een stack (Engels voor stapel) is in de informatica een datastructuur voor de opslag van een wisselend aantal elementen waarbij geldt 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.
Inhoud |
[bewerken] De datastructuur stack
De operaties op een stack zijn de volgende:
- push: legt het meegegeven element op de stapel
- pop: neemt het bovenste element van de stapel af en levert het op
- isempty: levert true op als de stack leeg is
Soms wordt ook wel ondersteund:
- top (of peek): levert het bovenste element op de stapel op zonder het er af te halen
Een stack is te vergelijken met een stapel borden: het laatste bord dat je op de stapel heb gelegd pak je er het eerst weer van af. 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; een algemene remedie is niet te geven.
- Stack overflow: een push-operatie op een volle stack. Dit kan alleen optreden voor stacks met een begrensde grootte.
[bewerken] Stacks bij de uitvoering van programma's
Een zogenaamde callstack wordt gebruikt bij het aanroepen van subroutines in computerprogramma's. Het returnadres, dat de eerstvolgende uit te voeren instructie bevat, vormt hier het element dat wordt opgeslagen en weer teruggehaald. De stackpointer is meestal een van de registers van een processor. Bewerkingen hiermee kosten zeer weinig tijd. Sommige microprocessors hebben verschillende stackpointers.
Een variabelenstack wordt gebruikt voor het opslaan van lokale variabelen. Het is technisch mogelijk dat de callstack en de variabelenstack dezelfde is. Deze constructie is echter niet gebruikelijk omdat hij bijzonder kwetsbaar is voor programmeerfouten, waardoor het returnadres beschadigd raakt. Een samenhangend blok stackgegevens met returnadres, aanroepparameters en lokale variabelen heet een frame.
[bewerken] Stackgeoriënteerd programmeren
De programmeertaal Forth maakt weinig gebruik van variabelen, maar plaatst de tussenresultaten van berekeningen op een stack. Ook de argumenten van een berekening moeten eerst op deze stack geplaatst worden. Waar je in een andere programmeertaal bijvoorbeeld schrijft:
print 4 * (1 + 2)
gaat dat in Forth als volgt. Zet eerst 4 op de stack, daarna 1 en 2. Tel 1 en 2 op met de +. Nu staan de 4 en de som van 1 en 2 (3 dus) op de stack. Vermenigvuldig deze twee waarden met *. Het resultaat 12 verschijnt op de top van de stack. Het commando . (leestekens zijn geldige namen in Forth) drukt dit af op het scherm.
4 1 2 + * .
Er worden nog steeds microprocessoren gemaakt met een stackgeörië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.
Rekenmachines van HP maakten voorheen gebruik van de zogenaamde omgekeerde Poolse notatie (Eng: Reverse Polish Notation, RPN) hetgeen erop neerkomt dat je de rekenmachine bedient zoals in het voorbeeld van Forth hierboven.
[bewerken] Externe links
- http://www.cs.sunysb.edu/~skiena/214/lectures/lect3/lect3.html (uitleg stacks en queues)
