Verem (adatszerkezet)
A verem az egyik legfontosabb adatszerkezet a számítástechnikában. Ahhoz, hogy megértsük, hogyan működik a verem, gondoljunk egy képpel lefelé fordított kártyapaklira. Csak a tetején lévő kártyához férhetünk hozzá könnyedén. Ha meg akarjuk nézni a legfelső kártyát, két dolgot tehetünk: megkukkantjuk, de a pakliban hagyjuk, vagy leemeljük. Amikor leemeljük a legfelső tárgyat, akkor levesszük a veremről. Ha egy másik kártyát akarunk a verem tetejére tenni, akkor pusholjuk.
A veremet last-in-first-out (LIFO) gyűjteménynek nevezzük. Ez azt jelenti, hogy az utolsó dolog, amit hozzáadtunk (toltunk), az lesz az első dolog, amit kihúzunk (popped). Ha az utolsó kártya, amit a kártyakupacra tettünk, egy ász volt, akkor az első kártya, amit a tetejéről lehúztunk, ugyanez az ász.
Két művelet a veremben: push és pop.
Történelem
A halmot először 1955-ben javasolta, majd 1957-ben szabadalmaztatta a német Friedrich L. Bauer. Ugyanezt a koncepciót az ausztrál Charles Leonard Hamblin ettől függetlenül, nagyjából ugyanebben az időben fejlesztette ki.
Egyéb műveletek
A modern számítógépes nyelvekben a verem általában a "push"-nál és a "pop"-nál több művelettel van megvalósítva. Egyes implementációkban van olyan függvény, amely visszaadja a verem aktuális hosszát. Egy másik tipikus segédművelet a "top" (más néven "peek"), amely vissza tudja adni a verem aktuális legfelső elemét anélkül, hogy eltávolítaná azt. Egy másik gyakori művelet a "dup", amely másolatot készít a verem tetején lévő elemről.
Kapcsolódó oldalak
- Stack gép
