Stack vs Heap
Stack är en ordnad lista där infogning och radering av listobjekt endast kan göras i ena änden som kallas toppen. På grund av denna anledning betraktas stacken som en LIFO-datastruktur (Last in First out). Heap är en speciell datastruktur som är baserad på träd och uppfyller en speciell egenskap som kallas heap-egenskapen. En hög är också ett komplett träd, vilket innebär att det inte finns några luckor mellan trädets löv, dvs. i ett komplett träd fylls varje nivå innan du lägger till en ny nivå i trädet och noderna i en given nivå fylls från vänster till höger.
Vad är Stack?
Som tidigare nämnts är stack en datastruktur där element läggs till och tas bort från endast en ände som kallas toppen. Stackar tillåter bara två grundläggande operationer som kallas push och pop. Push-operationen lägger till ett nytt element på toppen av stacken. Popoperationen tar bort ett element från toppen av stacken. Om stacken redan är full, när en push-operation utförs, betraktas den som stack-overflow. Om en pop-operation utförs på en redan tom stack, betraktas den som ett stack-underflöde. På grund av det lilla antalet operationer som kan utföras på en stack anses det vara en begränsad datastruktur. Enligt det sätt som push- och pop-operationerna definieras är det dessutom uppenbart att element som lades in senast i stacken går ut ur stacken först. Därför betraktas stack som en LIFO-datastruktur.
Vad är Heap?
Som tidigare nämnts är heap ett komplett träd som uppfyller heapegenskapen. Heap-egenskapen anger att om y är en undernod av x bör värdet som lagras i nod x vara större än eller lika med värdet som är lagrat i nod y (dvs. värde (x) ≥ värde (y)). Den här egenskapen innebär att noden med det största värdet alltid skulle placeras vid roten. En hög konstruerad med den här egenskapen kallas en max-heap. Det finns en annan variant av heapegenskapen som anger det motsatta av detta. (dvs. värde (x) ≤ värde (y)). Detta innebär att noden med det minsta värdet alltid skulle placeras vid roten, så kallad en minhög. Det finns ett brett utbud av operationer som utförs på högar som att hitta minimum (i min-högar) eller maximala (i max-högar), ta bort minimum (i min-högar) eller maximala (i max-högar),ökar (i maxhögar) eller minskar (i minhögar) -tangent etc.
Vad är skillnaden mellan Stack och Heap?
Huvudskillnaden mellan stackar och högar är att medan stack är en linjär datastruktur, är heap en icke linjär datastruktur. Stack är en ordnad lista som följer LIFO-egenskapen, medan heapen är ett komplett träd som följer heap-egenskapen. Dessutom är stack en begränsad datastruktur som endast stöder ett begränsat antal operationer som push och pop, medan heap stöder ett brett spektrum av operationer som att hitta och ta bort minimi eller maximum, öka eller minska nyckeln och slå samman.
