1. Čakalno vrsto lahko definiramo kot urejen seznam, ki omogoča izvajanje operacij vstavljanja na enem koncu, imenovanem ZADAJ in operacije brisanja, ki jih je treba izvesti na drugem klicanem koncu SPREDAJ .
2. Čakalna vrsta se imenuje seznam prvi prišli, prvi ven.
3. Na primer, ljudje, ki čakajo v vrsti za železniško vozovnico, tvorijo vrsto.
Aplikacije čakalne vrste
Zaradi dejstva, da čakalna vrsta izvaja dejanja po principu prvi prispe, prvi ven, kar je povsem pošteno za vrstni red dejanj. Spodaj so obravnavane različne uporabe čakalnih vrst.
- Čakalne vrste se pogosto uporabljajo kot čakalne vrste za posamezen skupni vir, kot je tiskalnik, disk, CPE.
- Čakalne vrste se uporabljajo pri asinhronem prenosu podatkov (kjer se podatki ne prenašajo z enako hitrostjo med dvema procesoma), npr. cevi, datoteka IO, vtičnice.
- Čakalne vrste se uporabljajo kot medpomnilniki v večini aplikacij, kot so MP3 predvajalnik, CD predvajalnik itd.
- Čakalna vrsta se uporablja za vzdrževanje seznama predvajanja v medijskih predvajalnikih za dodajanje in odstranjevanje skladb s seznama predvajanja.
- Čakalne vrste se v operacijskih sistemih uporabljajo za obdelavo prekinitev.
Kompleksnost
| Struktura podatkov | Časovna zapletenost | Prostor Compleity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Povprečje | Najslabše | Najslabše | |||||||
| Dostop | Iskanje | Vstavljanje | Izbris | Dostop | Iskanje | Vstavljanje | Izbris | ||
| Čakalna vrsta | jaz (n) | jaz (n) | i(1) | i (1) | O(n) | O(n) | O(1) | O(1) | O(n) |