Stack vs Heap
Stack er en ordnet liste der innsetting og sletting av listeelementer kun kan gjøres i den ene enden k alt toppen. På grunn av denne grunn anses stack som en Last in First out (LIFO) datastruktur. Heap er en spesiell datastruktur som er basert på trær og den tilfredsstiller en spesiell egenskap k alt heap-egenskapen. En haug er også et komplett tre, noe som betyr at det ikke er hull mellom bladene på treet, dvs. i et komplett tre fylles hvert nivå ut før et nytt nivå legges til 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 kun den ene enden som kalles toppen. Stabler tillater bare to grunnleggende operasjoner k alt push og pop. Push-operasjonen legger til et nytt element på toppen av stabelen. Pop-operasjonen fjerner et element fra toppen av stabelen. Hvis stabelen allerede er full, når en push-operasjon utføres, betraktes det som et stabeloverløp. Hvis en pop-operasjon utføres på en allerede tom stabel, betraktes det som en stabelunderflyt. På grunn av det lille antallet operasjoner som kan utføres på en stabel, anses det som en begrenset datastruktur. I tillegg, i henhold til måten push- og pop-operasjonene er definert, er det klart at elementer som ble lagt til sist i stabelen, går ut av stabelen først. Derfor betraktes stabelen som en LIFO-datastruktur.
Hva er Heap?
Som tidligere nevnt er heap et komplett tre som tilfredsstiller haugegenskapen. Heap-egenskapen sier at hvis y er en undernode av x, bør verdien som er 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 være plassert ved roten. En haug konstruert ved hjelp av denne egenskapen kalles en max-heap. Det er en annen variant av heap-egenskapen som angir det motsatte av denne. (dvs. verdi(x) ≤ verdi(y)). Dette innebærer at noden med den minste verdien alltid vil være plassert ved roten, og dermed k alt en min-heap. Det er et bredt spekter av operasjoner utført på hauger, for eksempel å finne minimum (i min-heaps) eller maksimum (i max-heaps), slette minimum (i min-heaps) eller maksimum (i max-heaps), øke (i maks. hauger) -heaps) eller avtagende (i min-heaps) tast osv.
Hva er forskjellen mellom Stack og Heap?
Hovedforskjellen mellom stabler og heaps 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 heap er et komplett tre som følger heap-egenskapen. Videre er stack en begrenset datastruktur som kun 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.
