Kolejki w Javie - jak wybrać właściwą implementację?

Gdy zadania mają być obsługiwane w kolejności napływania, zwykła lista szybko przestaje wystarczać. W Javie służy do tego kolejka, czyli struktura, która pozwala bezpiecznie dodawać elementy, pobierać je i sprawdzać pierwszy element bez ręcznego przesuwania danych. Pokażę, jak działa interfejs Queue, kiedy wybrać ArrayDeque, PriorityQueue lub kolejkę współbieżną, a także jak napisać własną prostą implementację.

Jak działa kolejka w Javie

Klasyczna kolejka działa według zasady FIFO, czyli first in, first out. Element trafia na koniec, a jest pobierany z początku. Dobrym obrazowym przykładem jest kolejka żądań HTTP, zadań do wydruku albo wiadomości czekających na obsłużenie przez pracownika.

W Javie kolejka jest opisana przez interfejs Queue z pakietu java.util. Sam interfejs nie przechowuje danych. Określa tylko operacje, a konkretne zachowanie zależy od wybranej implementacji. To rozdzielenie interfejsu od klasy jest praktyczne, bo mogę zmienić sposób przechowywania elementów bez przepisywania kodu, który z kolejki korzysta.

Queue zadania = new ArrayDeque<>();

zadania.offer("Raport");
zadania.offer("Powiadomienie");
zadania.offer("Eksport danych");

System.out.println(zadania.poll()); // Raport
System.out.println(zadania.peek()); // Powiadomienie

Najważniejsze metody mają pary o podobnym zastosowaniu, ale różnym zachowaniu w sytuacji problemowej. Ja w codziennym kodzie zwykle wybieram wersje offer(), poll() i peek(), ponieważ zwracają wartość sygnalizującą brak możliwości wykonania operacji zamiast od razu rzucać wyjątek.

W kolejce o nieograniczonym rozmiarze offer() najczęściej zwróci true, ale przy strukturach o stałej pojemności może zwrócić false. Trzeba też uważać na wartość null. Wiele implementacji jej nie dopuszcza, a metody takie jak poll() używają null do oznaczenia pustej kolejki.

ArrayDeque, LinkedList czy PriorityQueue

Wybór klasy ma większe znaczenie niż sama znajomość metod. Dla klasycznej kolejki FIFO najczęściej zaczynam od ArrayDeque. Jest oparta na tablicy o zmiennym rozmiarze, dobrze wykorzystuje pamięć i nie wymaga tworzenia osobnego obiektu dla każdego elementu.

LinkedList również implementuje Queue, ale w nowych projektach rzadko jest moim pierwszym wyborem. Lista wiązana przechowuje dodatkowe referencje w węzłach, przez co ma większy narzut pamięci. Jej zaletą jest elastyczność, jednak dla zwykłego dodawania na końcu i usuwania z początku ArrayDeque zazwyczaj jest prostsze i wydajniejsze.

PriorityQueue służy do innego problemu. Nie zwraca najstarszego elementu, lecz ten, który ma najmniejszą wartość według naturalnego porządku albo przekazanego komparatora. To dobre rozwiązanie dla harmonogramu zadań, algorytmu Dijkstry czy systemu, w którym pilniejsze zgłoszenia powinny być obsłużone wcześniej.

Praktyczna zasada jest prosta. Jeśli nie potrzebuję priorytetów ani synchronizacji, deklaruję zmienną jako Queue, a tworzę ArrayDeque. Dzięki temu kod pokazuje zamiar, a implementację można później wymienić bez zmiany całej logiki.

Queue liczby = new ArrayDeque<>();

Praktyczne operacje na elementach kolejki

Najczęstszy scenariusz wygląda tak, że program dodaje zadania, a osobny fragment kodu pobiera je aż do opróżnienia struktury. Do sprawdzania końca używam isEmpty(), a nie porównania rozmiaru z konkretną liczbą. Taki zapis jest czytelniejszy i nie zależy od tego, ile elementów znajdowało się w kolejce na początku.

Queue kolejka = new ArrayDeque<>();

kolejka.offer("plik-1.csv");
kolejka.offer("plik-2.csv");
kolejka.offer("plik-3.csv");

while (!kolejka.isEmpty()) {
    String plik = kolejka.poll();
    System.out.println("Przetwarzam " + plik);
}

Jeżeli chcę tylko zobaczyć pierwszy element, wybieram peek(), bo nie usuwa on danych. Metoda poll() usuwa początek, dlatego wywołanie jej w warunku diagnostycznym może niepostrzeżenie zmienić stan programu. Ten błąd zdarza się często przy logowaniu i testowaniu.

Przeczytaj również: C# LINQ Aggregate - Kiedy używać, a kiedy unikać?

Przykład z własnym porządkiem

Priorytet można zdefiniować przez komparator. W poniższym przykładzie mniejsza liczba oznacza pilniejsze zadanie. Kolejność dodawania nie ma tu decydującego znaczenia.

Queue zadania = new PriorityQueue<>(
    Comparator.comparingInt(Zadanie::priorytet)
);

zadania.offer(new Zadanie("Kopia zapasowa", 3));
zadania.offer(new Zadanie("Awaria serwera", 1));
zadania.offer(new Zadanie("Raport tygodniowy", 5));

Zadanie pilne = zadania.poll();

Trzeba pamiętać, że PriorityQueue gwarantuje właściwy element na początku, ale nie obiecuje pełnego posortowania wszystkich elementów podczas iteracji. Jeśli potrzebuję kompletnej kolejności, pobieram elementy metodą poll() albo stosuję inną strukturę.

Kolejki w aplikacjach wielowątkowych

Zwykłe ArrayDeque nie powinno być współdzielone przez wiele wątków bez dodatkowej synchronizacji. Gdy jeden wątek dodaje zadania, a drugi je pobiera, wybieram klasę z pakietu java.util.concurrent. To nie tylko kwestia wydajności, ale przede wszystkim poprawności operacji wykonywanych równocześnie.

BlockingQueue pasuje do modelu producent-konsument. Producent dodaje dane, a konsument może poczekać, aż pojawi się element. Metoda put() może zatrzymać wątek przy pełnej kolejce, natomiast take() czeka przy pustej. Właśnie takie zachowanie jest przydatne przy przetwarzaniu plików, zadań asynchronicznych i komunikacji między etapami aplikacji.

BlockingQueue zadania = new ArrayBlockingQueue<>(100);

zadania.put("wysyłka-maila");

String zadanie = zadania.take();
System.out.println(zadanie);

Limit 100 elementów chroni tu aplikację przed niekontrolowanym wzrostem pamięci. Jeśli producent działa szybciej niż konsument, kolejka w końcu się zapełni, a system dostanie szansę zwolnić zamiast przyjmować dane bez końca.

Gdy nie chcę blokować wątku, mogę użyć offer() i sprawdzić wynik. ConcurrentLinkedQueue jest przydatna w prostszych scenariuszach współbieżnych, ale nie rozwiązuje problemu oczekiwania na dane. Wybór zależy więc od tego, czy pustka lub pełność kolejki ma zatrzymać pracę, czy tylko zwrócić informację o braku możliwości operacji.

Jak napisać własną kolejkę dla nauki

W projekcie produkcyjnym korzystam z gotowych klas biblioteki standardowej. Własna implementacja ma jednak dużą wartość edukacyjną, bo pokazuje, co naprawdę dzieje się podczas dodawania i usuwania elementów. Najprościej użyć tablicy cyklicznej, w której indeks początku i końca przesuwa się po osiągnięciu ostatniej komórki.

public class SimpleQueue {
    private final Object[] data;
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public SimpleQueue(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("Pojemność musi być dodatnia");
        }
        data = new Object[capacity];
    }

    public boolean offer(E element) {
        if (element == null || size == data.length) {
            return false;
        }

        data[tail] = element;
        tail = (tail + 1) % data.length;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0) {
            return null;
        }

        E element = (E) data[head];
        data[head] = null;
        head = (head + 1) % data.length;
        size--;
        return element;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Ważny szczegół to wyzerowanie komórki po pobraniu elementu. Dzięki temu obiekt może zostać usunięty przez garbage collector, gdy nie ma już innych referencji. Pominięcie tej instrukcji prowadzi do niepotrzebnego przetrzymywania obiektów w pamięci, nawet jeśli logicznie kolejka jest pusta.

Ta wersja ma stałą pojemność i nie jest bezpieczna wielowątkowo. Nie obsługuje też wszystkich metod interfejsu Queue, dlatego traktowałbym ją jako ćwiczenie z indeksami, buforem cyklicznym i kontrolą stanu, a nie zamiennik ArrayDeque.

Błędy, które najczęściej psują działanie kolejki

• Użycie PriorityQueue tam, gdzie potrzebne jest FIFO. Priorytet zmienia kolejność obsługi.
• Wywołanie remove() lub element() bez sprawdzenia, czy kolejka zawiera dane.
• Współdzielenie ArrayDeque między wątkami bez synchronizacji.
• Założenie, że iteracja po PriorityQueue zwróci elementy w pełni posortowanej kolejności.
• Brak limitu w kolejce zasilanej szybciej, niż jest opróżniana.
• Wstawianie null i późniejsze traktowanie go jako sygnału pustej kolejki.

Ja zaczynam od określenia trzech rzeczy: czy kolejność ma być FIFO, czy elementy mają mieć priorytety oraz czy dane będą współdzielone przez wątki. Te trzy odpowiedzi zwykle prowadzą do właściwej klasy szybciej niż porównywanie wszystkich dostępnych implementacji.

Warto też testować sytuacje brzegowe. Sprawdzam pustą kolejkę, pojedynczy element, przepełnienie bufora oraz kolejność po wielokrotnym zawinięciu indeksu. W przypadku systemów współbieżnych dodaję testy obciążeniowe, bo błąd może pojawiać się tylko przy określonej kolejności działań wątków.

Dobry wybór zależy od sposobu obsługi danych

Do zwykłego bufora zadań wybrałbym ArrayDeque. Gdy ważność zadania ma pierwszeństwo przed momentem dodania, lepsza będzie PriorityQueue. Przy komunikacji między wątkami potrzebuję jednej z implementacji BlockingQueue albo kolejki współbieżnej, zależnie od tego, czy konsument ma czekać na dane.

Najważniejsze jest nie samo zapamiętanie nazw klas, lecz rozpoznanie modelu pracy. Kolejka jest dobrym narzędziem wtedy, gdy dane można obsługiwać etapami, kontrolować tempo przetwarzania i jasno określić, który element powinien zostać pobrany jako następny.

Gdy opanujesz różnicę między offer(), poll() i peek(), a potem dopasujesz implementację do FIFO, priorytetu lub współbieżności, większość problemów z kolejkami w Javie przestaje być zgadywaniem. Zostaje świadomy wybór struktury, jej pojemności i zasad obsługi błędów.