Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

3.3. A verem és az objektum lefoglalás/felszabadítás

3.3. A verem és az objektum lefoglalás/felszabadítás

3.4. Definíció. A verem adatstruktúra

A verem (stack) olyan dinamikus halmaz, amelyben előre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk. Ez az elem mindig az időben a legutoljára a struktúrába elhelyezett elem lesz. Műveletei: beszúrás (push), törlés (pop).

Az ilyen törlési eljárást Utolsóként érkezett – Elsőként távozik (Last In – First Out, LIFO) eljárásnak nevezzük.

A verem jele S, attributuma a tető[S], amely egy mutató, a legutóbb betett (beszúrt) elemre mutat. Itt a tömbös realizációt mutatjuk be. A vermet egy S tömb valósítja meg. A kezdő tömbindex az 1-es. Az üres verem esetén a tető[S] tartalma zérus. Beszúrásnál a tető[S] tartalma nő eggyel, és az elem a tető[S] által mutatott indexű rekeszbe kerül. Törlésnél csak a tető[S] tartalma csökken eggyel elem nem semmisül meg. Figyelnünk kell, hogy lehetetlen esetben ne végezzük el a műveletet. Nincs beszúrás, ha betelt a tömb, nincs törlés, ha üres a verem. Érdemes ezeket a vizsgálatokat külön eljárásként megírni. Alább következnek a megfelelő pszeudokódok.

3.3. Példa. Helyezzük el egy kezdetben üres verembe a megadott sorrendben érkező 342, 416, 112 kulcsú elemeket, majd ürítsük ki a veremet! A verem maximális mérete hat elem.

A törléseknél láthatóan az elemek nem törlődtek fizikailag, csak már nem elérhetők. Újabb beszúrások esetén természetesen felülíródnak az új elemmel és akkor végképpen elvesznek.

A verem realizálható olyan egyszeresen láncolt, nemrendezett, nemciklikus listával is, ahol a beszúrás mindig a lista első eleme elé történik, és a törlés mindig az első elemet törli.

Egy szép alkalmazása a veremnek és a listának együtt a memóriaterület (objektum) lefoglalása és felszabadítása. Legyen m rekeszünk az adatrekordok tárolására. Legyen n m rekesz lefoglalva listás szerkezettel. Szabadon áll m - n rekesz további elemek számára. Ezeket a szabad rekeszeket egy egyszeresen láncolt listában tartjuk nyilván. A szabad globális mutató mutat az első szabad helyre. Mindig az első szabad helyet foglaljuk le, vagy a felszabadult hely a szabadok közé az első helyre kerül. Tehát a szabad rekeszek egy vermet alkotnak. A felszabadult rekesz a verembe kerül, rekesz igénylés esetén pedig a veremből elégítjük ki az igényt. Két művelet jelentkezik, az objektum lefoglalása és az objektum felszabadítása. Pszeudokódjaik:

3.4. Példa. Legyen adott 6 rekesz – egy hatelemű tömb - tárolási célra. A tömb kezdetben üres. Végezzük el a megadott sorrendben a felsorolt kulcsokkal a műveleteket. Ha a kulcs előtt egy T betű áll, akkor azt törölni kell, ha nem áll semmi, akkor be kell szúrni. Az elemeket kétszeresen láncolt listában tartjuk nyilván, a beszúrás az egyszerűség kedvéért történjen mindig a lista elejére és az objektum lefoglalás/felszabadítás vermes módszerét alkalmazzuk. A kulcsok felsorolása: 987, 654, 365, 247, T654, 123, T247, 235.

A következő animáción látható a megoldás:

Ugyanez lépésenként: