Stack vs Heap
Stack yra sutvarkytas sąrašas, kuriame sąrašo elementus galima įterpti ir ištrinti tik viename gale, vadinamame viršuje. Dėl šios priežasties dėklas yra laikomas paskutinio iš pradžių (LIFO) duomenų struktūra. Krūva yra speciali duomenų struktūra, pagrįsta medžiais ir atitinkanti specialią savybę, vadinamą krūvos savybe. Be to, krūva yra užbaigtas medis, o tai reiškia, kad tarp medžio lapų nėra tarpų, t. y. pilname medyje kiekvienas lygis užpildomas prieš pridedant naują medį, o tam tikro lygio mazgai užpildomi nuo iš kairės į dešinę.
Kas yra Stack?
Kaip minėta anksčiau, krūva yra duomenų struktūra, kurioje elementai pridedami ir pašalinami tik iš vieno galo, vadinamo viršuje. Stackai leidžia tik dvi pagrindines operacijas, vadinamas push ir pop. Stūmimo operacija prideda naują elementą krūvos viršuje. Iššokantis veiksmas pašalina elementą iš krūvos viršaus. Jei krūva jau pilna, kai atliekama stūmimo operacija, tai laikoma krūvos perpildymu. Jei iššokimo operacija atliekama jau tuščioje dėtuvėje, ji laikoma dėklo pertekliumi. Dėl nedidelio operacijų, kurias galima atlikti su krūva, skaičiaus, ji laikoma ribota duomenų struktūra. Be to, atsižvelgiant į tai, kaip apibrėžiamos „push“ir „pop“operacijos, aišku, kad elementai, kurie buvo įtraukti paskutiniai į krūvą, pirmiausia išeina iš krūvos. Todėl dėklas laikomas LIFO duomenų struktūra.
Kas yra krūva?
Kaip minėta anksčiau, krūva yra visas medis, atitinkantis krūvos savybę. Krūvos savybė teigia, kad jei y yra antrinis x mazgas, tada mazge x saugoma reikšmė turėtų būti didesnė arba lygi y mazge saugomai vertei (t. y. reikšmė(x) ≥ reikšmė(y)). Ši savybė reiškia, kad didžiausią vertę turintis mazgas visada būtų šaknyje. Krūva, sukurta naudojant šią savybę, vadinama maksimalia krūva. Yra dar vienas krūvos ypatybės variantas, kuris teigia priešingai. (t. y. reikšmė(x) ≤ reikšmė(y)). Tai reiškia, kad mazgas, turintis mažiausią reikšmę, visada būtų įdėtas į šaknį, todėl vadinamas min krūva. Krūvose atliekamos įvairios operacijos, pvz., minimumo (min-krūvose) arba maksimumo (maks.-krūvose) suradimas, minimumo (min-krūvose) arba maksimumo (maks. krūvose) ištrynimas, didinimas (maks. -krūvos) arba mažėjimo (min-krūvos) klavišas ir kt.
Kuo skiriasi Stack ir Heap?
Pagrindinis skirtumas tarp krūvų ir krūvų yra tas, kad nors krūva yra linijinė duomenų struktūra, krūva yra nelinijinė duomenų struktūra. Stack yra sutvarkytas sąrašas, kuris seka LIFO ypatybę, o krūva yra visas medis, sekantis krūvos ypatybę. Be to, dėklas yra ribota duomenų struktūra, kuri palaiko tik ribotą skaičių operacijų, pvz., „push“ir „pop“, o krūva palaiko daugybę operacijų, tokių kaip minimumo arba maksimumo radimas ir ištrynimas, rakto padidinimas arba sumažinimas ir sujungimas.
