Amikor egy mozi pénztáránál beállsz a sor végére, akkor az történik, hogy a sor elején lévő vásárol jegyet, majd kilép a sorból és a sor további tagjai előrelépnek. Amikor új vásárló érkezik, akkor az a sor végére áll (normális esetben).
Sor (Queue) - Olyan informatikai fogalom, amelyet az informatikában sok helyen használnak különböző sebességű rendszerek összekapcsolásakor. Például hálózatokban nem garantálható, hogy a küldő és a fogadó mindig ugyanolyan sebességgel dolgozik, ezért a két fél mindig használ egy sor adatszerkezetet, hogy a sebességkülönbségeket kiegyenlítse. Ha a küldő és a fogadó sebessége átlagosan megegyezik, vagy a fogadó gyorsabban tud adatokat fogadni, mint ahogy a kóldő adja az adatokat, akko működni fog a rendszer. Ha a küldő gyorsabban ad adatot, mint amit a fogadó tud feldolgozni, akkor egy idő múlva bedugul a rendszer. (Ilyen, amikor túlterheléses támadást intéznek egy szerver ellen.)
Ezt az adatszerkezetet angolul First In First Out = FIFO adatszerkezetnek hívják.
Megvalósítás
A Queue megvalósítása nem túl bonyolult és OOP módon (is) lehetséges. Az alábbiakban lépésről lépésre létrehozunk egy queue típust és kipróbáljuk.
Ez egy teljesen működőképes program. A Main(), azaz a főprogram egy keretet határoz meg. A Queue osztály példányosításával kezdődik a program. Véletlenszerűen teszünk 0-tól 100-ig terjedő véletlenszámokat egy sorba, összesen 100-at és véletlenszerűen veszünk ki adatokat a sorból. Ha többször teszünk be adatot, mint amennyit kiveszünk, akkor betelhet a sor, ha pedig többször veszünk ki adatot, mint beteszünk, akkor üres lesz a sor.
A betevés és kivétel ciklus a példában 100 szor zajlik le. A betétel és a sorból való kivétel valószínűségét a bev és kiv változók kezdőértékeivel lehet szabályozni.
Amikor a főprogramban meghívjuk a q.sorba() metódust, akkor a sor végére teszünk adatot, a q.sorbol() metódussal kiveszünk egy adatot a sor elejéről. A q.allapot() segítségével kiirathatjuk a sor pillanatnyi állapotát.
A Queue osztály leírása
A Queue osztályban az állapotot privát, tehát kívülről nem látható tulajdonságok írják le. A példányosításkor lefut a a konstruktor metódus, aminek a neve kötelezően ugyanaz, mint az osztály neve.
Ebben a példában minden metódus publikus, tehát kívülről elérhető. Fent leírtam röviden a főbb metódusok feladatait. A kód végigkövetésével látszik, hogy milyen feltételek esetén lehet még betenni adatot a sorba, illetve ha betelt, akkor a konzolra kiírja, hogy !Betelt!. Erre a q.sorba() metódust használjuk.
Ugyanígy amikor kivesszük a sor első elemét, akkor ha üres a sor, akkor -1-et ad vissza eredményül a q.sorbol() és kiírja a konzolra, hogy !Üres!
Az alábbiakban a működő forráskód:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace queue
{
class Program
{
public static void Main(string[] args)
{
Queue q = new Queue();
Random r = new Random();
Random v1 = new Random();
Random v2 = new Random();
int bev = 60; //A bemenő adat valószínűsége 0..100 között.
int kiv = 40; //A sorból kivenni való adat valószínűsége 0..100 között.
int adat;
int ki;
Console.Clear();
for (int i = 0 ; i<100; i++)
{
adat = r.Next(0, 100);
Console.Write("Be: ");
if(v1.Next(0,100) < 60 )
{
Console.Write(adat);
q.sorba(adat);
}
else
{
Console.Write("- ");
}
Console.Write(" ===> ");
if( v2.Next(0,100) < 40 )
{
ki = q.sorbol();
Console.Write("Ki: {0}", ki);
}else{
Console.Write("Ki: - ");
}
q.allapot();
}
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
}
class Queue
{
//privát állapotleíró változók
private const int hossz = 10; //A tároló tömb hossza
private int[] sor = new int[hossz]; //A sorban lévő adatokat tároló tömb
private int utolso; //Hol van az utolsó adat a tömbben
private int db = 0; //Hányadik adatátvitel zajlik
//Az osztály konstruktora inicializálja a
public Queue(){
utolso = -1;
}
//Ez a metódus teszi be a sor végére az új adatot
public void sorba(int adat)
{
//Ha van hely még a sorban, akkor beteszi az adatot a végére
if(utolso < hossz-1)
{
utolso++;
sor[utolso] = adat;
}
else
{
Console.Write(" !Betelt! ");
}
}
//Ez a metódus adja vissza a sor első tagját
public int sorbol()
{
int vissza;
//Ha nem üres a sor akkor ki tudunk venni adatot
if (utolso > -1 )
{
vissza = sor[0];
//Egy hellyel előremásolja a sorban lévő adatokat
for(int i=0 ;i < hossz-1 ;i++)
{
sor[i] = sor[i+1];
}
sor[hossz-1] = 0;
utolso--; //A sorban lévő adatok számát csökkentem
}
else
{
vissza = -1; //A -1 jelentése: nincs érvényes visszatérő adat
Console.Write(" !Üres! ");
}
return vissza;
}
// Ez a metódus a sor állapotát írja ki
public void allapot()
{
Console.Write(" A sor: ");
for(int i=0 ; i< hossz ; i++)
{
Console.Write("{0,2}, ", sor[i]);
}
Console.WriteLine();
db++;
}
}
}A fenti egyszerű példa jó arra, hogy szemléltessem az osztályok létrehozását, használatát és értelmét. Ha ezt vagy ehhez hasonló alkalmazást többen fejlesztenek, akkor az osztály és a futás alatt az objektum paramétereit csak a publikus metódusokon keresztül lehet módosítani.
Megjegyzem, hogy a sornak ez a megvalósítása nem a legoptimálisabb. Ha ezt a megvalósítást gyorsítani kellene, akkor is csak a fenti három metódust kellene használni, de azoknak a belsejét teljesen át lehetne írni.
A sor adatszerkezet javítása
Az eredeti sor osztály lelassul, ha megnöveljük a sor méretét, mivel minden adatkivételnél a sorban lévő adatokat eggyel előre kell másolni. Jobb lenne, ha kivételkor nem kellene a sok adatot mozgatni!
A megoldás: Képzeljük el, hogy a tárolási hely olyan dobozok sorozata, amelyek körbe vannak téve és az új szabad helyet és a következő adatot két mutató mutatja nekünk meg. Mondjuk legyen az elso és az utolso.
Ha beteszünk egy adatot, akkor az utolso+1 helyre tesszük a tömbbe és növeljük az utolsó mutatót eggyel.
Ha kiveszünk a sorból egy adatot, akkor kivesszuk az elso által mutatott helyen lévő adatot és növeljük az elso változót eggyel.
Sajnos a tárolást továbbra is csak tömbökben lehet megvalósítani. Mivel a tömb véges, ezért az elso és az utolso változo is előbb utóbb eléri a tömb utolsó elemét. Ekkor a következő beteendő adatot a tömb első helyére kell tenni és a mutatót is 0-ra kell állítani. Ugyanígy ha a tömb utolsó helyén lévő adatot akarjuk kivenni, akkor az elso változót is 0-ra kell állítani.
Mikor üres a sor?
Ha az elso és az utolso nevű változó ugyanoda mutat, akkor nem tudunk kivenni adatot.
Mikor van teli a sor?
Ha az utolso nevű változó "utoléri" az elsőt, azaz majdnem ugyanoda mutat, és új adatot tennénk a sorba, akkor felülírhatjuk a korábbi aktuálisan kiveendő adatot. Vagyis teli van a sor, ha az utolso+1 utoléri az elso változót.