Stack vs Heap
Stack er en ordnet liste, hvor indsættelse og sletning af listeelementer kun kan udføres i den ene ende kaldet toppen. På grund af denne grund betragtes stakken som en Last in First out (LIFO) datastruktur. Heap er en speciel datastruktur, der er baseret på træer, og den opfylder en særlig egenskab kaldet heap-egenskaben. En bunke er også et komplet træ, hvilket betyder, at der ikke er mellemrum mellem træets blade, dvs. i et komplet træ er hvert niveau udfyldt, før der tilføjes et nyt niveau til træet, og noderne i et givet niveau udfyldes fra venstre mod højre.
Hvad er Stack?
Som tidligere nævnt er stak en datastruktur, hvor elementer tilføjes og fjernes fra kun den ene ende kaldet toppen. Stabler tillader kun to grundlæggende operationer kaldet push og pop. Trykoperationen tilføjer et nyt element til toppen af stakken. Pop-operationen fjerner et element fra toppen af stakken. Hvis stakken allerede er fuld, når en push-operation udføres, betragtes det som et stak-overløb. Hvis en pop-handling udføres på en allerede tom stak, betragtes det som et stak underflow. På grund af det lille antal operationer, der kan udføres på en stak, betragtes det som en begrænset datastruktur. I overensstemmelse med den måde, push- og pop-operationerne er defineret, er det desuden klart, at elementer, der blev tilføjet sidst i stakken, går først ud af stakken. Derfor betragtes stakken som en LIFO-datastruktur.
Hvad er Heap?
Som tidligere nævnt er heap et komplet træ, der opfylder heap-egenskaben. Heap-egenskab angiver, at hvis y er en underordnet node af x, så skal værdien lagret i node x være større end eller lig med værdien lagret i node y (dvs. værdi(x) ≥ værdi(y)). Denne egenskab indebærer, at noden med den største værdi altid vil blive placeret ved roden. En heap konstrueret ved hjælp af denne egenskab kaldes en max-heap. Der er en anden variation af heap-egenskaben, der angiver det modsatte af denne. (dvs. værdi(x) ≤ værdi(y)). Dette indebærer, at noden med den mindste værdi altid vil blive placeret ved roden, således kaldet en min-heap. Der er en bred vifte af operationer udført på dynger, såsom at finde minimum (i min-dynger) eller maksimum (i max-dynger), slette minimum (i min-dynger) eller maksimum (i max-dynger), øge (i max. -dynger) eller faldende (i min-dynger) tast osv.
Hvad er forskellen mellem Stack og Heap?
Den største forskel mellem stakke og heaps er, at mens stak er en lineær datastruktur, er heap en ikke-lineær datastruktur. Stack er en ordnet liste, der følger LIFO-egenskaben, mens heapen er et komplet træ, der følger heap-egenskaben. Desuden er stack en begrænset datastruktur, der kun understøtter et begrænset antal operationer som push og pop, mens heap understøtter en lang række operationer såsom at finde og slette minimum eller maksimum, øge eller mindske nøglen og flette.
