1. Kolejkę można zdefiniować jako uporządkowaną listę, która umożliwia wykonanie operacji wstawiania na jednym końcu, tzw TYŁ i usuń operacje, które mają być wykonane na innym końcu o nazwie PRZÓD .
2. Kolejka nazywana jest listą „pierwszy na wejściu, pierwszy na wyjściu”.
3. Na przykład osoby oczekujące w kolejce po bilet kolejowy tworzą kolejkę.
Zastosowania kolejki
Z uwagi na to, że kolejka wykonuje akcje na zasadzie „pierwszy weszło, pierwsze wyszło”, co jest w miarę sprawiedliwe w przypadku kolejności działań. Istnieją różne zastosowania kolejek omówione poniżej.
- Kolejki są powszechnie stosowane jako listy oczekujących na pojedynczy współdzielony zasób, taki jak drukarka, dysk czy procesor.
- Kolejki wykorzystuje się w asynchronicznym przesyłaniu danych (gdzie dane nie są przesyłane z tą samą szybkością pomiędzy dwoma procesami) np. potoki, plik IO, gniazda.
- Kolejki służą jako bufory w większości aplikacji, takich jak odtwarzacze multimedialne MP3, odtwarzacze CD itp.
- Kolejki służą do utrzymywania listy odtwarzania w odtwarzaczach multimedialnych w celu dodawania i usuwania utworów z listy odtwarzania.
- Kolejki są używane w systemach operacyjnych do obsługi przerwań.
Złożoność
| Struktura danych | Złożoność czasu | Kompletność przestrzeni | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Przeciętny | Najgorszy | Najgorszy | |||||||
| Dostęp | Szukaj | Wprowadzenie | Usunięcie | Dostęp | Szukaj | Wprowadzenie | Usunięcie | ||
| Kolejka | W) | W) | ja(1) | ja(1) | NA) | NA) | O(1) | O(1) | NA) |