Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

3.4. A sor

3.4. A sor

3.5. Definíció. A sor adatstruktúra

A sor (queue) olyan dinamikus halmaz, amelyben előre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk és az az elem is amelyet a BESZÚR eljárással a halmazba beteszünk. Törlésre mindig az elemek közül a legrégebben beszúrt kerül. A beszúrt elem lesz a legfrissebb elem. Műveletek: beszúrás, törlés.

Az ilyen törlést Elsőként érkezik – Elsőként távozik (First In – First Out, FIFO) eljárásnak nevezzük. Ha az elemeket lineárisan egymás mellé felsorakoztatjuk az érkezésük sorrendjében, akkor szemléletesen mondhatjuk, hogy törlésre mindig az első helyen álló elem kerül, a beszúrás pedig az utolsó elemet követő helyre történik. A sornak, mint adatstruktúrának többféle realizációja lehetséges. Itt most a tömbös realizációval foglalkozunk. Legyen a tömb neve Q és legyen a tömbméret[Q] attributum értéke n, azaz a tömb n elemű. Az elemek indexelése legyen Tömbös realizáció esetén a tömb a méreténél legalább eggyel kevesebb elemű sort képes csak tárolni. A sor attributumai:

A sor elemei a tömbben a fej[Q], fej[Q]+1, fej[Q]+2,\dots ,vége[Q]-1 indexű helyeket foglalják el. Ebben az index felsorolásban az indexek ciklikusan követik egymást, azaz az n index után az 1 index következik, ha erre szükség van. A műveletek szempontjából a törlés esetében nyilvánvaló, hogy üres sorból nem lehet elemet törölni. Az üres sor felismerhető abból, hogy fej[Q]=vége[Q]. (Kezdetben fej[Q]=vége[Q]=1.). Ha üres sorból veszünk ki elemet, az hiba (alulcsordulás). A beszúrás esetében nem szabad azt elvégezni, ha a sor már megtelt. Ez a jelenség felismerhető abból, hogy A beszúrás tele sorba hibát eredményez (túlcsordulás). Nézzük a műveletek pszeudokódjait:

3.5. Példa. Végezzük el az alábbi műveleteket egy üres sorból kiindulva. A következő felsorolásban egy kulcsérték annak beszúrását jelenti. A T betű a sorból eltávolítást szimbolizálja. A tömb 5 elemű. A felsorolás: 345, 231, 768, T, 893, T, 259, 478. Az eredmény alább látható. Minden egyes lépésben megmutatjuk a sor állapotát. Vastagítottuk a sorhoz hozzátartozó elemeket.

Animációként:

Ugyanez lépésenként:

Sor realizálható láncolt listával is. Törölni mindig a lista első elemét töröljük, beszúrni pedig mindig a lista utolsó eleme után szúrunk be. Elegendő egyszeresen láncolt listával dolgozni, viszont ilyenkor érdemes a lista végének a mutatóját is külön tárolni. Ha kétszeresen láncolt listát használunk, akkor már a ciklikus lista használata a hatékonyabb és ekkor a listavég mutatót nem kell külön tárolni.