Stack vs Heap
Stack er en ordnet liste der innsetting og sletting av listeelementer bare kan gjøres i den ene enden kalt toppen. På grunn av dette betraktes stack som en Last in First out (LIFO) datastruktur. Heap er en spesiell datastruktur som er basert på trær og tilfredsstiller en spesiell egenskap som kalles heap-eiendommen. Også, en haug er et komplett tre, noe som betyr at det ikke er noen hull mellom treets blader, dvs. i et komplett tre er hvert nivå fylt ut før du legger til et nytt nivå i treet, og nodene i et gitt nivå fylles fra venstre til høyre.
Hva er Stack?
Som nevnt tidligere er stack en datastruktur der elementer legges til og fjernes fra bare den ene enden som kalles toppen. Stabler tillater bare to grunnleggende operasjoner kalt push og pop. Push-operasjonen legger til et nytt element på toppen av bunken. Popoperasjonen fjerner et element fra toppen av bunken. Hvis stabelen allerede er full, betraktes den som en stackoverløp når en push-operasjon utføres. Hvis en pop-operasjon utføres på en allerede tom stabel, betraktes den som en stabelunderstrømning. På grunn av det lille antallet operasjoner som kan utføres på en bunke, betraktes det som en begrenset datastruktur. I tillegg, i henhold til måten push- og pop-operasjonene er definert på, er det klart at elementer som ble lagt til sist i bunken, går ut av bunken først. Derfor betraktes stack som en LIFO-datastruktur.
Hva er Heap?
Som nevnt tidligere er haug et komplett tre som tilfredsstiller haugegenskapen. Heap-egenskapen sier at hvis y er en undernode av x, skal verdien lagret i node x være større enn eller lik verdien som er lagret i node y (dvs. verdi (x) ≥ verdi (y)). Denne egenskapen innebærer at noden med størst verdi alltid vil bli plassert i roten. En haug konstruert ved bruk av denne egenskapen kalles en maks-haug. Det er en annen variant av haugegenskapen som sier omvendt av denne. (dvs. verdi (x) ≤ verdi (y)). Dette innebærer at noden med den minste verdien alltid vil bli plassert ved roten, og dermed kalt en min-haug. Det er et bredt spekter av operasjoner som utføres på dynger, for eksempel å finne minimum (i min-dynger) eller maksimum (i maks-dynger), slette minimum (i min-dynger) eller maksimum (i maks-dynger),økende (i maks-hauger) eller avtagende (i min-hauger) nøkkel, etc.
Hva er forskjellen mellom Stack og Heap?
Hovedforskjellen mellom stabler og dynger er at mens stack er en lineær datastruktur, er heap en ikke-lineær datastruktur. Stack er en ordnet liste som følger LIFO-egenskapen, mens haugen er et komplett tre som følger haugegenskapen. Videre er stack en begrenset datastruktur som bare støtter et begrenset antall operasjoner som push og pop, mens heap støtter et bredt spekter av operasjoner som å finne og slette minimum eller maksimum, øke eller redusere nøkkelen og slå sammen.
