Kolejka — struktura danych (FIFO): definicja, operacje i priorytetowa
Kolejka FIFO — definicja, operacje (enqueue, dequeue, peek) i kolejka priorytetowa. Przykłady, zastosowania i praktyczne wyjaśnienie dla programistów i studentów.
W informatyce kolejka jest strukturą danych, używaną do przechowywania elementów, zanim zostaną one przetworzone. Ogólnie rzecz biorąc, istnieją następujące operacje:
- Enqueue: dodaj element na koniec kolejki
- Dequeue: usuń element z przodu kolejki
- Opcjonalnie może istnieć operacja przeglądania elementu z przodu kolejki, bez jego usuwania.
Pozycje, które znajdują się pomiędzy pierwszym a ostatnim elementem kolejki nie są bezpośrednio dostępne.
Istnieje pewna specjalizacja, zwana kolejką priorytetową: W kolejce priorytetowej każdy element posiada również wagę, która określa pozycję elementu w kolejce.
Definicja i własności
Kolejka to abstrakcyjna struktura danych działająca zgodnie z zasadą FIFO (first-in, first-out) — elementy są usuwane w tej samej kolejności, w jakiej zostały dodane. Typowe operacje to:
- enqueue (push, offer) — wstawienie elementu na koniec kolejki;
- dequeue (pop, poll) — usunięcie i zwrócenie elementu z przodu kolejki;
- peek (front, view) — odczyt elementu z przodu bez usuwania;
- isEmpty — sprawdzenie, czy kolejka jest pusta;
- size — zwrócenie liczby elementów w kolejce.
Implementacje
Kolejki można zaimplementować na kilka sposobów, różniących się złożonością operacji i wykorzystaniem pamięci:
- Tablica cykliczna (circular buffer) — stała pamięć, dwa wskaźniki (head/tail). Operacje enqueue i dequeue w czasie O(1). Wymaga obsługi przepełnienia (overflow) lub mechanizmu rozszerzania.
- Lista jednokierunkowa z wskaźnikami na początek i koniec — każdy enqueue dodaje element na końcu (O(1)), dequeue usuwa z początku (O(1)). Dynamiczne zarządzanie pamięcią, brak kosztownych przesunięć.
- Deque (double-ended queue) — umożliwia operacje na obu końcach; może działać jako stos lub kolejka.
- Kolejka priorytetowa — zwykle implementowana jako kopiec (binary heap) lub inne struktury (Fibonacci heap, drzewo Binomialne). Operacje insert i extract mają złożoności zależne od konkretnej implementacji (np. O(log n) dla binary heap).
Złożoność czasowa i złożoność pamięciowa
- Standardowe operacje enqueue, dequeue i peek w dobrze zaimplementowanej kolejce (tablica cykliczna lub lista) mają złożoność O(1) czasu.
- Kolejka priorytetowa (binary heap) oferuje zwykle O(log n) dla wstawiania i usuwania elementu o najwyższym priorytecie, a O(1) dla odczytu elementu najwyższego priorytetu (peek).
- Pamięć: struktury dynamiczne wykorzystują pamięć proporcjonalną do liczby przechowywanych elementów O(n). Tablica o stałym rozmiarze zużywa z góry przydzieloną pamięć.
Warianty i rozszerzenia
- Bounded queue — kolejka o ograniczonej pojemności; przy próbie wstawienia, gdy jest pełna, operacja może się nie powieść lub zablokować (w środowiskach wielowątkowych).
- Unbounded queue — dynamicznie rozszerzana; ryzyko wyczerpania pamięci przy dużej liczbie elementów.
- Blocking queue — w wielowątkowych systemach, operacje enqueue/dequeue mogą blokować wątek do czasu dostępności miejsca lub elementu (przykłady: Java BlockingQueue).
- Lock-free / wait-free queues — implementacje bez blokad, przydatne w programowaniu współbieżnym dla zwiększenia wydajności i unikania zakleszczeń.
- Stabilność priorytetów — w niektórych implementacjach kolejki priorytetowej elementy o tym samym priorytecie mogą zachowywać kolejność FIFO (stabilna kolejka priorytetowa).
Zastosowania
- Algorytm BFS (przeszukiwanie wszerz) w grafach i drzewach.
- Bufory i kolejki zadań w systemach operacyjnych (planowanie procesów, kolejki drukarki).
- Komunikacja między procesami/wątkami — model producent-konsument.
- Symulacje zdarzeń dyskretnych, gdzie zdarzenia są obsługiwane w kolejności zgłoszeń lub według priorytetu.
- Obsługa żądań sieciowych i kolejkowanie zapytań w serwerach.
Błędy i przypadki brzegowe
- Underflow — próba usunięcia elementu z pustej kolejki powinna być obsłużona (zwrot wartości specjalnej, wyjątek lub wartość null w zależności od API).
- Overflow — dla kolejki ograniczonej należy zdefiniować zachowanie przy przepełnieniu (odrzucenie nowego elementu, blokowanie, rozszerzenie tablicy itp.).
- Zarządzanie pamięcią i wydajnością w aplikacjach o dużym obciążeniu — konieczne monitorowanie i ew. ograniczanie długości kolejki.
Praktyczne wskazówki
- W prostych zastosowaniach, gdy znamy maksymalny rozmiar, tablica cykliczna daje najlepszą wydajność i niską reżię pamięciową.
- W aplikacjach współbieżnych używaj sprawdzonych struktur (np. implementacji z biblioteki standardowej języka), które zapewniają poprawność i wydajność.
- Dla zadań wymagających priorytetowego przetwarzania wybierz strukturę priorytetową (kopiec), a jeśli ważna jest zachowana kolejność elementów o równym priorytecie — wybierz stabilną implementację.
Podsumowując, kolejka to prosta, lecz bardzo użyteczna struktura danych o szerokim zastosowaniu w informatyce. Wybór konkretnej implementacji powinien zależeć od wymagań dotyczących pamięci, czasu operacji oraz współbieżności.
A kolejka
Przeszukaj encyklopedię