# A verem adatstruktúra: LIFO elv és alkalmazások Üdvözöllek! Ebben a tananyagban a számítástechnika egyik legfontosabb és leggyakrabban használt adatstruktúrájával, a veremmel ismerkedünk meg. A verem megértése alapvető fontosságú a programozásban és az algoritmusok tervezésében, hiszen számos feladat megoldásához nyújt elegáns és hatékony eszközt. Képzeld el úgy, mint egy halom tányért: csak a legfelső tányért tudod levenni, és csak a tetejére tudsz újat tenni. Ez a mindennapi példa tökéletesen illusztrálja a verem működését, amelyet egy speciális elv, a LIFO (Last In, First Out) vezérel. ## Mi az a verem? A verem (angolul: **stack**) egy olyan lineáris adatstruktúra, amelyben az elemek hozzáadása és eltávolítása egyetlen végponton, a verem tetején keresztül történik. Ez a sajátosság adja a verem egyedi működését, amelyet a LIFO elvvel írunk le. > A **LIFO (Last In, First Out)** elv azt jelenti, hogy az utoljára hozzáadott elem lesz az első, amelyet eltávolíthatunk a veremből. Gondolj egy halom könyvre: a legutoljára letett könyvet fogod először levenni, ha csak a legfelsőhöz férsz hozzá. Did you know, hogy a verem koncepciója a 20. század közepén, az első számítógépek fejlesztésével párhuzamosan jelent meg, és alapvető szerepet játszott az első fordítóprogramok megalkotásában? ## A verem alapműveletei A verem kezeléséhez két fő művelet áll rendelkezésünkre, amelyekkel elemeket adhatunk hozzá vagy távolíthatunk el. Ezeken kívül vannak kiegészítő műveletek is, amelyekkel a verem állapotát ellenőrizhetjük. ### Push (betesz) művelet A **Push** művelet egy új elemet helyez a verem tetejére. Amikor egy elemet beteszünk, az lesz az új legfelső elem. Fontos megjegyezni, hogy a veremnek lehet egy **maximális kapacitása** (különösen a tömbös megvalósításoknál). Ha a verem tele van, és megpróbálunk új elemet hozzáadni, akkor **verem túlcsordulás** (stack overflow) hiba történik. > A **Verem túlcsordulás (Stack Overflow)** akkor következik be, amikor egy `push` műveletet próbálunk végrehajtani egy már tele veremen. ### Pop (kivesz) művelet A **Pop** művelet eltávolítja a verem legfelső elemét, és visszaadja annak értékét. A pop művelet után az előzőleg alatta lévő elem válik a verem új tetejévé. Ha a verem üres, és megpróbálunk elemet kivenni belőle, az hibát eredményez, ezt **verem alulcsordulásnak** (stack underflow) nevezzük. > A **Verem alulcsordulás (Stack Underflow)** akkor következik be, amikor egy `pop` műveletet próbálunk végrehajtani egy üres veremen. ### Kiegészítő műveletek Az alapvető `push` és `pop` műveletek mellett gyakran használnak kiegészítő műveleteket is a verem hatékonyabb kezeléséhez: * **Peek (megnéz)** vagy **Top (tető)**: Ez a művelet visszaadja a verem legfelső elemének értékét anélkül, hogy eltávolítaná azt. Hasznos, ha csak ellenőrizni szeretnénk a legfelső elemet a verem módosítása nélkül. * **IsEmpty (üres-e)**: Ez a logikai művelet `true` értékkel tér vissza, ha a verem nem tartalmaz elemeket, és `false` értékkel, ha igen. * **IsFull (tele van-e)**: Ez a logikai művelet `true` értékkel tér vissza, ha a verem elérte a maximális kapacitását (fix méretű implementáció esetén), és `false` értékkel, ha még van benne hely. ## A verem tömbös megvalósítása A verem adatstruktúra egyik leggyakoribb és legegyszerűbb megvalósítási módja egy **statikus (fix méretű) tömb** használata. Ehhez a megvalósításhoz szükségünk van egy tömbre, amely tárolja a verem elemeit, és egy **mutatóra** (vagy indexre), amely a verem tetejét jelöli. Ezt a mutatót gyakran `top` vagy `veremTeteje` néven ismerjük. Kezdetben a verem üres, és a `top` mutató általában $-1$ értékkel inicializálódik, jelezve, hogy nincs még elem a veremben. A tömb indexei $0$-tól kezdődnek. ### Push művelet tömbös megvalósítás esetén 1. **Ellenőrzés:** Először ellenőrizzük, hogy a verem tele van-e. Ez azt jelenti, hogy a `top` mutató értéke elérte-e a tömb maximális indexét, ami a tömb mérete mínusz egy, azaz $mathrm{méret} - 1$. Ha i