Skillnad mellan stack och hög

Stack vs Heap

Stack är en beställd lista där infogning och radering av listobjekt kan göras endast i ena änden kallad toppen. På grund av den här orsaken betraktas stapeln som en senast in första ut (LIFO) datastruktur. Heap är en speciell datastruktur som bygger på träd och det uppfyller en speciell egenskap som kallas heapegenskapen. En hög är också ett komplett träd vilket innebär att det inte finns några luckor mellan trädens löv, dvs i ett komplett träd fylls varje nivå innan du lägger till en ny nivå på trädet och noderna i en given nivå fylls från vänster till höger.

Vad är Stack?

Som tidigare nämnts är stapel en datastruktur där element läggs till och tas bort från en enda ände som kallas toppen. Stackar tillåter bara två grundläggande operationer som kallas push och pop. Tryckoperationen lägger till ett nytt element överst i stapeln. Popoperationen tar bort ett element från toppen av stapeln. Om stacken redan är full, när en push-operation utförs betraktas den som en stapelflöde. Om en popoperation utförs på en redan tom stack betraktas den som en stack underflöde. På grund av det lilla antal operationer som kan utföras på en stapel betraktas det som en begränsad datastruktur. Dessutom är det enligt det sätt som push och pop-operationerna definieras tydligt att element som tillsattes sist i stacken först går ut ur stapeln. Därför betraktas stapel som en LIFO datastruktur.

Vad är Heap?

Som tidigare nämnts är heap ett komplett träd som uppfyller hönsegenskapen. Heap-egenskapen anger att om y är en barnnod på x, 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 störst värde alltid kommer att placeras i roten. En hög byggd med den här egenskapen kallas en max-heap. Det finns en annan variant av heapegenskapen som anger omvänden av detta. (dvs värde (x) ≤ värde (y)). Detta innebär att noden med det minsta värdet alltid skulle placeras i roten, så kallade en minhöga. Det finns ett brett spektrum av operationer som utförs på högar som att hitta minimum (i minhögar) eller maximalt (i maxhöjder), radera minimum (i minhöjder) eller maximalt (i maxhögar), ökar (i max -heaps) eller minskande (i min-hål) nyckeln, etc..

Vad är skillnaden mellan Stack and Heap?

Huvudskillnaden mellan staplar och högar är att medan stacken är en linjär datastruktur är heap en icke-linjär datastruktur. Stack är en ordnad lista som följer LIFO-fastigheten, medan högen är ett komplett träd som följer högen. Stack är dessutom en begränsad datastruktur som endast stöder ett begränsat antal operationer som push och pop, medan högen stöder ett brett spektrum av operationer som att hitta och ta bort minimum eller maximalt, ökar eller minskar nyckeln och sammanfogar.