Forskellen mellem stak og bunke

Stak vs Heap

Stabel er en ordnet liste, hvor indsættelse og sletning af listeelementer kun kan udføres i den ene ende kaldet toppen. På grund af denne grund betragtes stack som en LIFO-datastruktur (Last in First out). Heap er en speciel datastruktur, der er baseret på træer, og den tilfredsstiller en speciel egenskab kaldet heap-egenskaben. En bunke er også et komplet træ, hvilket betyder, at der ikke er nogen huller mellem træets blade, dvs. i et komplet træ udfyldes hvert niveau, før der tilføjes et nyt niveau til træet, og knudepunkterne i et givet niveau udfyldes fra venstre til højre.

Hvad er stak?

Som nævnt tidligere er stack en datastruktur, hvor elementer tilføjes og fjernes fra kun den ene ende kaldet toppen. Stakke tillader kun to grundlæggende operationer kaldet push and pop. Trykoperationen tilføjer et nyt element øverst i stakken. Pop-operationen fjerner et element fra toppen af ​​stakken. Hvis stakken allerede er fuld, betragtes den, når en push-handling udføres, som en stakoverløb. Hvis en pop-operation udføres på en allerede tom stakle, betragtes den som en stakunderstrøm. På grund af det lille antal operationer, der kan udføres på en stak, betragtes det som en begrænset datastruktur. I henhold til den måde, hvorpå push- og pop-operationerne er defineret, er det klart, at elementer, der sidst blev tilføjet til stakken, først går ud af stakken. Derfor betragtes stack som en LIFO-datastruktur.

Hvad er Heap?

Som nævnt tidligere er bunke et komplet træ, der tilfredsstiller bunkeegenskaben. Heap-egenskab siger, at hvis y er et underordnet knudepunkt på x, skal værdien, der er gemt i knude x, være større end eller lig med den værdi, der er gemt i knudepunkt y (dvs. værdi (x) ≥ værdi (y)). Denne egenskab indebærer, at knuden med den største værdi altid vil blive placeret ved roden. En bunke konstrueret ved hjælp af denne egenskab kaldes en max-heap. Der er en anden variation af bunkeegenskaben, der siger det modsatte af dette. (dvs. værdi (x) ≤ værdi (y)). Dette indebærer, at knudepunktet med den mindste værdi altid vil blive placeret ved roden, således kaldet en min-heap. Der er en bred vifte af operationer, der udføres på dynger, såsom at finde minimum (i min-dynger) eller maksimum (i maks. Dynger), slette minimum (i min-dynger) eller maksimum (i max-dynger), stigning (i max -heaps) eller faldende (i min-heaps) nøgle osv.

Hvad er forskellen mellem Stack and Heap?

Den største forskel mellem stabler og dynger er, at selv om stakken er en lineær datastruktur, er dyngen en ikke-lineær datastruktur. Stabel er en ordnet liste, der følger LIFO-egenskaben, mens dyngen er et komplet træ, der følger bunkeegenskabet. Endvidere er stack en begrænset datastruktur, der kun understøtter et begrænset antal operationer som push og pop, mens heap understøtter en lang række operationer, såsom at finde og slette minimum eller maksimum, øge eller formindske nøglen og fusionere.