Stack vs Heap
Sklad je urejeni seznam, na katerem je mogoče vstavljanje in brisanje elementov seznama izvajati samo na enem koncu, ki se imenuje vrh. Iz tega razloga se sklad šteje za strukturo podatkov Last in First out (LIFO). Kup je posebna podatkovna struktura, ki temelji na drevesih in izpolnjuje posebno lastnost, imenovano lastnost kopice. Tudi kup je celotno drevo, kar pomeni, da med listi drevesa ni vrzeli, tj. V celotnem drevesu se vsaka raven zapolni, preden se drevesu doda nova raven in vozlišča na dani ravni se zapolnijo iz od leve proti desni.
Kaj je Stack?
Kot smo že omenili, je sklad podatkovna struktura, v kateri so elementi dodani in odstranjeni samo z enega konca, imenovanega vrh. Slogi omogočajo le dve temeljni operaciji, imenovani push in pop. Potisna operacija doda nov element na vrh sklada. Operacija pop odstrani element z vrha sklada. Če je sklad že poln, se pri izvajanju potisne operacije šteje za prelivanje sklada. Če se pojavna operacija izvede na že praznem kupčku, se šteje za podlivanje sklada. Zaradi majhnega števila operacij, ki bi jih lahko izvedli na skladu, se šteje za omejeno strukturo podatkov. Poleg tega je glede na način definiranja potisnih in pop operacij jasno, da elementi, ki so bili zadnji dodani v sklad, najprej izstopijo iz sklada. Zato se sklad šteje za podatkovno strukturo LIFO.
Kaj je kup?
Kot smo že omenili, je kopica celotno drevo, ki izpolnjuje lastnost kopice. Lastnost kopice navaja, da če je y podrejeno vozlišče x, mora biti vrednost, shranjena v vozlišču x, večja ali enaka vrednosti, shranjeni v vozlišču y (tj. Vrednost (x) ≥ vrednost (y)). Ta lastnost pomeni, da bi bilo vozlišče z največjo vrednostjo vedno postavljeno v koren. Kup, zgrajen z uporabo te lastnosti, se imenuje max-heap. Obstaja še ena različica lastnosti kopice, ki navaja obratno od tega. (tj. vrednost (x) ≤ vrednost (y)). To pomeni, da bi bilo vozlišče z najmanjšo vrednostjo vedno postavljeno v koren, tako imenovano min-heap. Obstaja širok spekter operacij, ki se izvajajo na kupih, na primer iskanje najmanjšega (v najmanjših kupih) ali največjega (v največjih kupih), brisanje najmanjšega (v najmanjših kupih) ali največjega (v največjih kupih),tipka za naraščanje (v največji količini) ali padajočo (v najmanjši količini) itd.
Kakšna je razlika med skladom in kupom?
Glavna razlika med skladi in gomilami je v tem, da medtem ko je sklad niz linearnih podatkovnih struktur, je kopica nelinearnih podatkovnih struktur. Stack je urejeni seznam, ki sledi lastnosti LIFO, medtem ko je kopica celotno drevo, ki sledi lastnosti kupca. Poleg tega je sklad omejena podatkovna struktura, ki podpira le omejeno število operacij kot push in pop, medtem ko kopica podpira širok spekter operacij, kot so iskanje in brisanje najmanjšega ali največjega, povečanje ali zmanjšanje ključa in spajanje.
