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 stack som en sist in först ut (LIFO) datastruktur. Heap är en speciell datastruktur som är baserad på träd och den uppfyller en speciell egenskap som kallas heap-egenskapen. En hög är också ett komplett träd, vilket betyder att det inte finns några luckor mellan trädets löv, dvs i ett komplett träd fylls varje nivå i innan en ny nivå läggs till i trädet och noderna i en given nivå fylls från vänster till höger.
Vad är Stack?
Som nämnts tidigare är stack en datastruktur där element läggs till och tas bort från endast en ände som kallas toppen. Stackar tillåter endast två grundläggande operationer som kallas push och pop. Push-operationen lägger till ett nytt element till toppen av stapeln. Popoperationen tar bort ett element från toppen av stapeln. Om stapeln redan är full, när en push-operation utförs, betraktas det som ett stackspill. Om en pop-operation utförs på en redan tom stack, betraktas det som ett stack underflow. På grund av det lilla antalet operationer som kan utföras på en stack, betraktas det som en begränsad datastruktur. Dessutom, enligt hur push- och pop-operationerna definieras, är det tydligt att element som lades till sist i stacken går ut ur stacken först. Därför betraktas stack som en LIFO-datastruktur.
Vad är Heap?
Som tidigare nämnt är heap ett komplett träd som uppfyller högegenskapen. Heap-egenskapen anger att, om y är en undernod av x, så bör värdet lagrat i nod x vara större än eller lika med värdet lagrat i nod y (dvs värde(x) ≥ värde(y)). Denna egenskap innebär att noden med det största värdet alltid skulle placeras vid roten. En hög konstruerad med denna egenskap kallas en max-hög. Det finns en annan variant av heap-egenskapen som anger motsatsen till 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 min-hög. Det finns ett brett utbud av operationer som utförs på högar som att hitta minimum (i min-högar) eller maximum (i max-högar), ta bort minimum (i min-högar) eller maximum (i max-högar), öka (i max. -högar) eller minskande (i min-högar) tangent, etc.
Vad är skillnaden mellan Stack och Heap?
Den största skillnaden mellan stackar och heaps ä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 utbud av operationer som att hitta och ta bort minimum eller maximum, öka eller minska nyckeln och slå samman.
