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. Af denne grund betragtes stack som en Last in First out (LIFO) datastruktur. Heap er en speciel datastruktur, der er baseret på træer, og den opfylder en speciel egenskab kaldet heap-ejendommen. En bunke er også et komplet træ, hvilket betyder, at der ikke er nogen huller mellem træets blade, dvs. i et komplet træ udfyldes hvert niveau, før der tilføjes et nyt niveau til træet, og noderne i et givet niveau er fyldt fra venstre til højre.
Hvad er Stack?
Som tidligere nævnt er stack en datastruktur, hvor elementer tilføjes og fjernes fra kun den ene ende kaldet toppen. Stakke tillader kun to grundlæggende operationer kaldet push og pop. Push-operationen tilføjer et nyt element til toppen af stakken. Pop-operationen fjerner et element fra toppen af stakken. Hvis stakken allerede er fuld, betragtes den som stakoverløb, når der udføres en push-operation. Hvis en pop-operation udføres på en allerede tom stak, betragtes den som en stabelunderstrømning. På grund af det lille antal operationer, der kunne udføres på en stak, betragtes det som en begrænset datastruktur. I henhold til den måde, hvorpå push- og pop-operationerne er defineret, er det tydeligt, at elementer, der blev tilføjet sidst i stakken, går ud af stakken først. Derfor betragtes stack som en LIFO-datastruktur.
Hvad er Heap?
Som nævnt tidligere er bunke et komplet træ, der tilfredsstiller bungejendom. Heap-egenskab angiver, at hvis y er en undernode af x, skal værdien, der er gemt i node x, være større end eller lig med den værdi, der er gemt i node y (dvs. værdi (x) ≥ værdi (y)). Denne egenskab indebærer, at noden med den største værdi altid placeres ved roden. En bunke konstrueret ved hjælp af denne egenskab kaldes en max-bunke. Der er en anden variation af bunkeegenskaben, der angiver det modsatte af dette. (dvs. værdi (x) ≤ værdi (y)). Dette indebærer, at noden med den mindste værdi altid vil placeres ved roden, så kaldet en min-bunke. Der er en bred vifte af operationer, der udføres på dynger, såsom at finde minimum (i min-bunke) eller maksimum (i max-bunke), slette minimum (i min-bunke) eller maksimum (i max-bunke),stigende (i max-bunke) eller faldende (i min-bunke) nøgle osv.
Hvad er forskellen mellem Stack og Heap?
Hovedforskellen mellem stakke og dynger er, at mens stack er en lineær datastruktur, er heap en ikke-lineær datastruktur. Stack er en ordnet liste, der følger LIFO-ejendommen, mens bunken er et komplet træ, der følger heap-ejendommen. 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 bred vifte af operationer, såsom at finde og slette minimum eller maksimum, øge eller formindske nøglen og flette.
