Stack

Related Topics:
Stack :: Stack_21 :: Stacked :: Stackhouse,_Jerry :: Stackpole,_Michael :: Stackhousiaceae

Een stack (Engels voor stapel) is in de informatica een datastructuur voor de opslag van een wisselend aantal elementen waarbij geldt dat 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. 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. Het eerste (onderste) bord van de stapel komt als laatste. Een bord tussen de stapel uit pakken kan ook, maar niet zomaar.

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

Bij stackoperaties werken een aantal instructies samen:

Eén instructie (bijvoorbeeld PUSH) schrijft een element in de stack en verhoogt direct daarna de pointer. Dit kan ook in omgekeerde volgorde. Het is ook mogelijk, dat de pointer juist wordt verlaagd.
Een andere (bijvoorbeeld POP) haalt een element van de stack. Vergeleken met het schrijven, werkt deze instructie de pointer in tegengestelde richting bij. Bovendien is de volgorde van de bewerkingen verwisseld.
Soms is het mogelijk, het laatst geplaatste element te lezen, zonder de pointer bij te werken (bijvoorbeeld TOP).

Bij onjuist gebruik kunnen twee fouten optreden:

Stack overflow: een nieuw element wordt geschreven, als de stack al vol is. Dit element overschrijft geheugen, dat ofwel niet tot de stack behoort, ofwel aan het andere eind van de stack.
Stack underflow: een element wordt gelezen, als de stack al leeg is. Dit levert een ongeldige waarde op.

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.

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 print drukt dit af op het scherm. 4 1 2 + * print

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.

Externe links

http://www.cs.sunysb.edu/~skiena/214/lectures/lect3/lect3.html (uitleg stacks en queues)

Datastructuur

Gourt Home::Gourt :: Stack

Stackgeoriënteerd programmeren

Externe links