A sor hasonlóan működik, mint egy emberekből álló sor a pénztár előtt. Az elemeket abban a sorrendben vesszük ki, mint ahogy betettük.

Adatszerkezet alatt adatok tárolásának és elrendezésének egy lehetséges módját értjük. Az adattípus a mi értelmezésünkben egy adatszerkezet, a rajta értelmezett műveletekkel együtt.

A sor FIFO (first-in first-out) adattípus, azaz mindig az első betett elem elérhető, illetve törölhető. Egyaránt lehet tömbösen és láncoltan is ábrázolni.

Tömbös ábrázolás:

Kezdetben a sor a tömb elején kezdődik, később azonban, ahogy kiveszünk belőle elemeket, a tömb „belsejébe húzódik”, majd elérve a tömb végét, a beszúrás ciklikusan folytatódik a tömb elején.

A sor tömbös ábrázolásában az $Z : \mathcal{T} []$ tömb mellett a $k : \mathbb{N}$ (az első elem indexe) és a $n : \mathbb{N}$ (a sor aktuális mérete) is a sor részét képezi.

$Queue$

$- \space Z : \mathcal{T}[]$ $- \space n : \mathbb{N}$ $- \space k : \mathbb{N}$

$+ \space Queue ( m : \mathbb{N} ) \space \{ Z := \text{new} \space \mathcal{T}[m]; n := 0; k := 0 \}$ $+ \space \sim Queue() \space \{ delete \space Z \}$ $+ \space add(x : \mathcal{T})$ $ + \space rem() : \mathcal{T}$ $+ \space first() : \mathcal{T}$ $+ \space length() : \mathbb{N} \space \{ \text{return} \space n \}$ $+ \space isFull() : \mathbb{B} \space \{ \text{return} \space n = Z.length \}$ $+ \space isEmpty() : \mathbb{B} \space \{ \text{return} \space n = 0 \}$ $+ \space setEmpty() \space \{ n := 0 \}$

Mivel van a sornak egy maximális mérete, ezért bevezetjük az $IsFull()$ műveletet is.

Az $add()$ a sor végére rakja a paraméterként kapott elemet, amennyiben nincs tele a sor. A $rem()$ visszaadja a legelső elemet a sorból és ki is törli azt a sorból, ezzel arrébb csúszik a sor kezdete. A $first()$ visszaadja a legelső elemet és a sorban hagyja azt.

Ha egy üres sorból próbálunk meg elemet kivenni, a sor alulcsordul, amit hibának tekintünk. Ha a sor tele van és elemet szeretnénk belerakni, akkor a sor túlcsodul, amit szintén hibának tekintünk.

Láncolt ábrázolás:

A sor láncolt reprezentációjában a $first$ pointer nem csak az adattípushoz biztosít hozzáférést, hanem egyben a sor első elemére is mutat. Bevezetjük a $last$ pointert is, amely egy „joker” (végelem vagy trailer) elemre mutat, amiben nincs adat. Új elem beszúrásakor a beszúrandó kulcsot a végelemben tároljuk el és készítünk egy új végelemet. Üres sor esetén $first = last$, mivel a konstruktor létrehozza a „joker” elemet és a $first$ erre az elemre mutat kezdetben.

$Queue$

$- \space first, last : E1^*$ $- \space size : \mathbb{N}$

$+ \space Queue () \space \{ first := last := \text{new} \space E1; size := 0 \}$ $+ \space \sim Queue()$ $+ \space add(x : \mathcal{T})$ $ + \space rem() : \mathcal{T}$ $+ \space first() : \mathcal{T}$ $+ \space length() : \mathbb{N} \space \{ \text{return} \space size \}$ $+ \space isEmpty() : \mathbb{B} \space \{ \text{return} \space size = 0 \}$ $+ \space setEmpty()$

A láncolt ábrázolású sor műveletei között nem szerepel az $IsFull()$ művelet, mivel ebben a reprezentációban nem számolunk a tárolókapacitás gyakorlati felső korlátjával. A destruktor és a $setEmpty()$ műveletek futási ideje, így $\Theta (n)$.

Az $add()$ a lista végére szúrja be a paraméterként kapott elemet. A $rem()$ visszaadja a lista első elemét és ki is törli a lista elejéről. A $first()$ visszaadja a lista elején lévő elemet.

Műveletigény:

A tömbös és a láncolt reprezentációban a sor minden művelete konstans időben végrehajtható, azaz $\Theta (1)$, mivel nem tartalmaz se ciklust, se rekurziót.

Gyakorlati alkalmazása:

A sor adatszerkezetettel sok algoritmusban találkozhatunk, pl.: bináris fák szintfolytos bejárásánál, gráfok szélességi bejárásánál, sor alapú Bellman-Ford algoritmusnál.