Loading AI tools
informatica Van Wikipedia, de vrije encyclopedie
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.
De operaties die op een stack kunnen worden toegepast, zijn:
Andere instructies, exclusief voor een call stack, zijn:
Soms worden nog ondersteund:
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:
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:
Na het uitvoeren van de procedure zal het volgende gebeuren:
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.
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.
Bij stackgeoriënteerd programmeren bevindt een programma zich als geheel op een stapel. Uitvoering gebeurt als volgt:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.