7. fejezet - Elemi adatszerkezetek

Az informatikában nagyon gyakran használt adatszerkezet a verem és a sor. Eme dinamikus adatszerkezetek esetén a lekérdező műveleteket rendszerint nem használjuk, illetve csupán az teszteljük, hogy az adott adatszerkezet üres-e vagy sem. A módosító műveleteknél bizonyos korlátozások érvényesülnek, pontosabban a veremnél a legutoljára beszúrt elemet törölhetjük elsőként, míg a sornál a legel őször beszúrt elemet. Épp ezért a TÖRÖL utasításnál nem kell megadni a törlend ő elemet, vagy annak kulcsát. Emiatt használják ezen adatszerkezetek megnevezésére a LIFO (last in-first out, azaz utolsóként be, elsőként ki) illetve a LILO (last in-last out, azaz utolsóként be, utolsóként ki) rövidítéseket. A sor adatszerkezetet jól jellemzi a keskeny alagút, ahol az alagútba először behajtó kocsi hagyja el azt elsőként. Míg a zsákutcába behajtó kocsik közül az utolsónak kell kitolatnia elsőként, ez pedig a verem jellemzője.

7.1. Verem

Mind a verem, mind a sor adatszerkezet ábrázolható tömbökkel. Tekintsük az S tömböt! Jelölje az S.tető a legutoljára berakott elem indexét, így az S[1..S.tető] tömbrész tartalmazza a verem aktuális értékét. Ha S.tető= 0, akkor veremben nincs elem, azaz a verem üres. Ha üres veremből próbálunk törölni, az alulcsordulásnak nevezzük, míg ha egy S.hossz +1-dik elemet próbálunk beszúrni, akkor túlcsordulásról beszélünk. Az egyetlen lekérdező művelettel azt állapíthatjuk meg, hogy üres-e a verem, vagy sem. Az angol szakirodalomban Push és Pop néven nevezett beszúró és törlő műveletekre mi a VEREMBE és VEREMBŐ L nevekkel hivatkozunk. Mind a lekérdezés, mind beszúrás és törlés is O(1) bonyolultságú.

Function ÜRES(S) 
Input: S verem 
Eredmény: IGAZ, ha üres a verem, és HAMIS, ha nem 
1 if S.tető == 0 then 
2    return IGAZ 
3 else 
4    return HAMIS
5 endif

Procedure VEREMBE(S,x) 
Input: S verem, x beszúrandó elem 
Eredmény: Az adott elemet beszúrja verem tetejére 
1 if S.tető ≤ S.hossz then 
2    S.tető = S.tető + 1 
3    S[S.tető] x 
4 else 
5    hiba "túlcsordulás" 
6 endif 

Function VEREMBőL(S) 
Input: S verem 
Output: A verem felső eleme, melyet egyben töröl is a veremből 
1 if ÜRES(S) then 
2    hiba "alulcsordulás" 
3 endif 
4 S.tető S.tető − 1 
5 return S[S.tető + 1]