7.2. Sor

Míg a veremnél egy adat meghatározza a verem méretét, a sornál kettőre van szükségünk. A sor feje a sor első elemét jelenti, míg a sor vége a sor utolsó elemét. Ha egy új elemet veszünk fel a sorba, akkor azt a sor végére írjuk, ahogy a pénztárnál is a sor végére állunk. Miután az első vevő fizetett a pénztárnál, elhagyja a sort. Hasonlóan a sor adattípusból is az első elemet, a sor fejét töröljük. Az alábbi programokban a Q listához tartozó Q.fej elem a sor első elemének indexe a Q[1..Q.hossz] tömbben. A Q.vége a sor utolsó eleme mögötti index, erre a helyre kerül a soron következő beszúrandó elem. A sor esetén is van egy lekérdező művelet, ez is arra ad választ, hogy az adatszerkezet üres-e vagy sem. A lista módosító műveletei hasonlóan a beszúrás (SORBA) és törlés (SORBÓL). Ha a lista üres, és így akarunk belőle törölni, akkor alulcsordul a sor. Ha pedig a megtelt listába akarunk még újabb elemeket szúrni, túlcsordul a sor. Ha hagyományos módon kezelnénk a tömböt, akkor a beszúrás és a törlés során a után mind a sor feje, mind a sor vége egyre hátrább és hátrább kerülne, s egy idő után bármilyen nagy tömb végét eléri mindkét index. Épp ezért a következő trükköt használjuk: kapcsoljuk össze a tömb végét és elejét, azaz készítsünk belőle egy gyűrűt.

Function ÜRES(Q) 
Input: Q sor 
Output: IGAZ, ha üres a sor, és HAMIS, ha nem 
1 if Q.fej == Q.vége then 
2    return IGAZ 
3 else 
4    return HAMIS 
5 endif  
Procedure SORBA(Q,x) 
Input: Q sor, x beszúrandó elem 
Eredmény: A sor végére beszúrja az adott elemet 
1  if Q.vége == Q.hossz then 
2     y = 1 
3  else 
4     y = Q.vége + 1
5  endif 
6  if Q.fej == y then 
7     hiba "Megtelt a sor!" 
8  else 
9     Q[Q.vége] = x 
10    Q.vége = y 
11 endif 
Function SORBÓL(Q) 
Input: Q sor 
Output: A sor első eleme, amelyet egyben töröl is a sorból 
1 x = Q[Q.fej] 
2 if Q.fej == Q.hossz then 
3    Q.fej = 1 
4 else 
5    Q.fej = Q.fej + 1 
6 return x 

7.1. példa - 15. példa

Hajtsuk végre párhuzamosan ugyanazokat a beszúró és törlő műveleteket egy soron és egy vermen!