Stapel versus hoop
Stack is een geordende lijst waarin het invoegen en verwijderen van lijstitems alleen kan worden gedaan aan één uiteinde, de bovenste genaamd. Om deze reden wordt stack beschouwd als een Last in First out (LIFO) -gegevensstructuur. Heap is een speciale datastructuur die is gebaseerd op bomen en voldoet aan een speciale eigenschap, de heap-eigenschap. Een hoop is ook een volledige boom, wat betekent dat er geen openingen zijn tussen de bladeren van de boom, dwz in een volledige boom wordt elk niveau ingevuld voordat een nieuw niveau aan de boom wordt toegevoegd en worden de knooppunten in een bepaald niveau gevuld vanaf van links naar rechts.
Wat is stapel?
Zoals eerder vermeld, is stack een datastructuur waarin elementen worden toegevoegd en verwijderd vanaf slechts één uiteinde, de top genaamd. Stacks staan slechts twee fundamentele bewerkingen toe: push en pop. De push-operatie voegt een nieuw element toe aan de bovenkant van de stapel. De pop-operatie verwijdert een element van de bovenkant van de stapel. Als de stapel al vol is en een push-bewerking wordt uitgevoerd, wordt dit beschouwd als een stapeloverloop. Als een pop-bewerking wordt uitgevoerd op een reeds lege stapel, wordt dit beschouwd als een stapelonderloop. Vanwege het kleine aantal bewerkingen dat op een stapel kan worden uitgevoerd, wordt het beschouwd als een beperkte gegevensstructuur. Bovendien is het, volgens de manier waarop de push- en pop-operaties zijn gedefinieerd, duidelijk dat elementen die als laatste aan de stapel zijn toegevoegd, als eerste uit de stapel gaan. Daarom wordt stack beschouwd als een LIFO-gegevensstructuur.
Wat is hoop?
Zoals eerder vermeld, is heap een complete boom die voldoet aan de heap-eigenschap. Heap-eigenschap stelt dat, als y een kindknooppunt van x is, de waarde die is opgeslagen in knooppunt x groter moet zijn dan of gelijk moet zijn aan de waarde die is opgeslagen in knooppunt y (dwz waarde (x) ≥ waarde (y)). Deze eigenschap houdt in dat het knooppunt met de grootste waarde altijd bij de wortel wordt geplaatst. Een heap die met deze eigenschap is geconstrueerd, wordt een max-heap genoemd. Er is nog een variant van de heap-eigenschap die het omgekeerde hiervan aangeeft. (dwz waarde (x) ≤ waarde (y)). Dit houdt in dat het knooppunt met de kleinste waarde altijd bij de root wordt geplaatst, dus een min-heap genoemd. Er wordt een breed scala aan bewerkingen op hopen uitgevoerd, zoals het vinden van minimum (in min-heaps) of maximum (in max-heaps), verwijderen van minimum (in min-heaps) of maximum (in max-heaps),toenemende (in max-Heaps) of afnemende (in min-Heaps) sleutel, etc.
Wat is het verschil tussen Stack en Heap?
Het belangrijkste verschil tussen stapels en hopen is dat terwijl stapel een lineaire gegevensstructuur is, heap een niet-lineaire gegevensstructuur is. Stack is een geordende lijst die de LIFO-eigenschap volgt, terwijl de heap een volledige boom is die de heap-eigenschap volgt. Bovendien is stack een beperkte datastructuur die slechts een beperkt aantal bewerkingen ondersteunt, zoals push en pop, terwijl heap een breed scala aan bewerkingen ondersteunt, zoals het vinden en verwijderen van het minimum of maximum, het verhogen of verlagen van de sleutel en het samenvoegen.
