1. A sor definiálható rendezett listaként, amely lehetővé teszi beszúrási műveletek végrehajtását az egyik végén, ún. HÁTULSÓ és törölje a végrehajtandó műveleteket egy másik végén ELÜLSŐ .
2. A várólista az Első In First Out lista.
3. Például a vasúti jegyért sorban álló emberek sorba állnak.
A Queue alkalmazásai
Tekintettel arra, hogy a queue a műveleteket first in first out alapon hajtja végre, ami meglehetősen korrekt az akciók sorrendje szempontjából. A várólistáknak különféle alkalmazásai vannak, amelyeket az alábbiak szerint tárgyalunk.
- A sorokat széles körben használják várólistaként egyetlen megosztott erőforráshoz, például nyomtatóhoz, lemezhez, CPU-hoz.
- A várólisták az aszinkron adatátvitel során használatosak (ahol az adatok nem azonos sebességgel kerülnek átvitelre két folyamat között) pl. csövek, reszelő IO, aljzatok.
- A sorokat pufferként használják a legtöbb alkalmazásban, például MP3 médialejátszóban, CD-lejátszóban stb.
- A Queue a lejátszási lista karbantartására szolgál a médialejátszókban, hogy hozzáadhassa és eltávolítsa a dalokat a lejátszási listáról.
- Az operációs rendszerekben sorokat használnak a megszakítások kezelésére.
Bonyolultság
| Adatstruktúra | Idő összetettsége | Space Compleity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Átlagos | Legrosszabb | Legrosszabb | |||||||
| Hozzáférés | Keresés | Beillesztés | Törlés | Hozzáférés | Keresés | Beillesztés | Törlés | ||
| Sor | ban ben) | ban ben) | i(1) | i(1) | Tovább) | Tovább) | O(1) | O(1) | Tovább) |