mały|Idea kolejki Kolejka () – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu , ; pierwszy na wejściu, pierwszy na wyjściu).
Operacje związane z kolejką zwyczajowo nazywa się („zakolejkuj”) oraz („odkolejkuj”). Kolejka działa tak jak kolejka w sklepie i ma podobną strukturę. Składa się z początku (, ) oraz końca (, ). Nowy element zawsze dodawany jest na końcu, analogicznie do klienta, który zawsze staje na końcu kolejki. Usunięcie z kolejki odpowiada obsłużeniu klienta w sklepie, czyli osoby, która aktualnie czekała najdłużej (tj. znajduje się z przodu kolejki).
Specjalną modyfikacją kolejki jest kolejka priorytetowa – każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet (klucz), który służy do określenia kolejności poszczególnych elementów w zbiorze. Oznacza to, że pierwsze na wyjściu niekoniecznie pojawią się te dane, które w kolejce oczekują najdłużej, lecz te o największym (lub najmniejszym) priorytecie.
Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego rodzaju obsługą zdarzeń. W szczególności w systemach operacyjnych ma zastosowanie kolejka priorytetowa, przydzielająca zasoby sprzętowe uruchomionym procesom.
Przeciwieństwem kolejki jest stos, bufor typu (ang. ; ostatni na wejściu, pierwszy na wyjściu), w którym jako pierwsze obsługiwane są dane wprowadzone jako ostatnie.
Przypisy
Bibliografia
Kategoria:Struktury danych