A Queue egy absztrakt adattípus , első az első kifelé elem hozzáférési fegyelmével ( FIFO , angol first in, first out ). Egy elem hozzáadása (általában enqueue szóval jelölve - sorba helyezés) csak a sor végén lehetséges, mintavételezés - csak a sor elejétől (amit általában dequeue szónak neveznek - eltávolítás a sorból), miközben a kiválasztott elem eltávolításra kerül a sorból.
Számos módja van a várólisták megvalósításának programnyelvekben.
Az első mód egy tömbként ábrázolja a sort, és két egész változó kezdődik és végződik.
Általában starta sor fejére mutat, arra end az elemre, amely akkor lesz kitöltve, amikor új elem kerül a sorba. Amikor egy elemet adunk a sorhoz, az q[end]új sorelemet a rendszer beírja és endeggyel csökkenti. Ha az end értéke kisebb lesz 1-nél, akkor körbejárjuk a tömböt, és a változó értéke egyenlő lesz n-nel. Egy elem kivonása a sorból hasonló módon történik: egy elem kivonása után q[start]a változó start1-gyel csökken. Az ilyen algoritmusok esetén a sorból egy cella nmindig üres lesz (mivel az nelemeket tartalmazó sort nem lehet megkülönböztetni üresből), amit az algoritmusok egyszerűsége kompenzál.
A módszer előnyei: enyhe memóriamegtakarítás lehetséges a második módszerhez képest; könnyebben fejleszthető.
Hátrányok: A sorban lévő elemek maximális számát a tömb mérete korlátozza. Ha túlcsordul, újra kell foglalni a memóriát, és át kell másolni az összes elemet egy új tömbbe.
A második módszer a dinamikus memóriával való munkavégzésen alapul. A sor lineáris listaként jelenik meg, amelyben az elemek hozzáadása/eltávolítása szigorúan a megfelelő végéről származik.
A módszer előnyei: a sor méretét csak a memória mennyisége korlátozza.
Hátrányok: nehezebben fejleszthető; több memória szükséges; ha ilyen sorral dolgozik, a memória töredezettebb; a sorban állás valamivel lassabb.
A sormetódusok két verem alapján valósíthatók meg S1az S2alábbiak szerint:
eljárássor ( x ): S1.push( x ) dequeue() függvény: ha S2 üres: ha S1 üres: hibajelentés: a sor üres amíg az S1 ki nem ürül: S2.push(S1.pop()) return S2.pop()Ez a megvalósítási mód a legkényelmesebb egy állandó sor felépítésének alapjaként. .
A várólisták szinte minden kifejlesztett programozási nyelven implementálva vannak. A CLI ehhez biztosítja a System.Collections.Queue osztályt, az Enqueue és Dequeue metódusokkal. Az STL -nek a fejlécfájl sorában definiált class queue<> is van. Ugyanazt a terminológiát használja (push és pop), mint a verem .
A programozási várólista akkor használatos, mint a való életben, amikor néhány műveletet a beérkezés sorrendjében kell végrehajtania, egymás után végrehajtva. Példa erre az események szervezése a Windows rendszerben. Amikor a felhasználó valamilyen műveletet hajt végre az alkalmazáson, a megfelelő eljárás nem kerül meghívásra az alkalmazásban (elvégre ebben a pillanatban az alkalmazás más műveleteket is végrehajthat), hanem üzenetet küldenek neki, amely információkat tartalmaz a végrehajtott műveletről, ez az üzenet sorba van állítva, és csak a korábban érkezett üzenetek feldolgozása után hajtja végre az alkalmazás a szükséges műveletet.
A BIOS - billentyűzet puffer egy gyűrűtömbként van felszerelve, amely általában 16 gépszóból áll, és két mutatót tartalmaz: a következő elemre és az első üres elemre.
| Adatstruktúrák | |
|---|---|
| Listák | |
| fák | |
| Számít | |
| Egyéb | |