Verem vs kupac
A Stack egy rendezett lista, amelyben a listaelemek beillesztése és törlése csak az egyik végén, az úgynevezett felső részen végezhető el. Emiatt a verem a Last in First out (LIFO) adatstruktúrának számít. A kupac egy speciális adatstruktúra, amely fákon alapul, és kielégíti a kupac tulajdonságnak nevezett speciális tulajdonságot. A kupac egy teljes fa, ami azt jelenti, hogy nincsenek hézagok a fa levelei között, vagyis egy teljes fában minden szint kitöltődik, mielőtt új szintet adna a fához, és az adott szint csomópontjai kitöltődnek balról jobbra.
Mi az a Stack?
Mint korábban említettük, a verem egy olyan adatstruktúra, amelyben az elemeket csak az egyik, felsőnek nevezett végből adják hozzá és távolítják el. A veremek csak két alapvető műveletet engednek meg, amit push and popnak hívnak. A tolási művelet új elemet ad a verem tetejéhez. A pop művelet eltávolít egy elemet a verem tetejéről. Ha a verem már megtelt, akkor egy tolási művelet végrehajtásakor azt verem túlcsordulásnak tekintjük. Ha egy pop műveletet egy már üres veremnél hajtanak végre, akkor az verem alulcsordulásnak számít. A veremen végrehajtható műveletek kis száma miatt korlátozott adatszerkezetnek számít. Ezenkívül a push és pop műveletek definiálásának módja alapján egyértelmű, hogy azok az elemek, amelyeket utoljára adtak a veremhez, először mennek ki a veremből. Ezért a verem LIFO adatstruktúrának számít.
Mi az a Halom?
Mint korábban említettük, a halom egy teljes fa, amely kielégíti a kupac tulajdonságait. A kupac tulajdonság azt állítja, hogy ha y x gyermekcsomópont, akkor az x csomópontban tárolt értéknek nagyobbnak vagy egyenlőnek kell lennie, mint az y csomópontban tárolt érték (azaz érték (x) ≥ érték (y)). Ez a tulajdonság azt jelenti, hogy a legnagyobb értékű csomópont mindig a gyökérnél lesz. Az e tulajdonság felhasználásával készült kupacot max-kupacnak nevezzük. A kupac tulajdonságnak van egy másik változata, amely ennek fordítottját állítja. (azaz érték (x) ≤ érték (y)). Ez azt jelenti, hogy a legkisebb értékű csomópont mindig a gyökérbe kerül, így min-kupacnak hívják. A halmokon végzett műveletek széles skálája létezik, például a minimum (min-halmokban) vagy a maximumok (max-halmokban), minimum törlése (min-halmokban) vagy maximumok (max-halmokban),növekvő (max-halmokban) vagy csökkenő (min-halmokban) kulcs stb.
Mi a különbség Stack és Heap között?
A halmok és a halmok közötti fő különbség az, hogy míg a verem lineáris adatszerkezet, a halom nem lineáris adatszerkezet. A Stack egy rendezett lista, amely a LIFO tulajdonságot követi, míg a kupac egy teljes fa, amely a kupac tulajdonságot követi. Ezenkívül a verem egy korlátozott adatstruktúra, amely csak korlátozott számú műveletet támogat push és pop módban, míg a halom olyan műveletek széles skáláját támogatja, mint például a minimum vagy a maximum megtalálása és törlése, a kulcs növelése vagy csökkentése és egyesítése.
