Stosy i kolejki w Javie to kolejny krok w pracy ze strukturami danych. Do tej pory budowaliśmy fundamenty pracy z danymi. Zaczęliśmy od tablic, gdzie mieliśmy sztywny rozmiar i dostęp po indeksie. Później przeszliśmy przez kolekcje i listy, gdzie liczyła się elastyczność i możliwość dynamicznego dodawania elementów. Następnie pojawiły się zbiory, które pilnowały unikalności, a w ostatniej lekcji mapy, gdzie klucz decydował o dostępie do wartości.
Teraz zmienimy perspektywę. Nie skupiamy się na tym, co przechowujemy i jak znaleźć element, ale w jakiej kolejności go przetwarzamy.
Wprowadzenie
Wyobraźmy sobie, że stoimy przed wejściem na koncert. Ludzie ustawiają się w kolejce. Każdy wie, że kto przyszedł pierwszy, ten wejdzie pierwszy. Nowe osoby ustawiają się na końcu i czekają na swoją kolej.
Na zapleczu mamy stos pudeł. Dokładamy kolejne kartony na górę. Gdy chcemy coś zdjąć, sięgamy po ostatni. Wyjęcie elementu ze środka rozwaliłoby cały stos.
Obie sytuacje rozwiązują różne problemy. Jedna pilnuje kolejności przyjścia, a druga daje szybki dostęp do ostatniej operacji.
Dokładnie te dwa podejście implementujemy w Javie.
Stos
Stos działa według zasady Last in, First Out (LIFO). Ostatni element, który dodajemy, jako pierwszy zdejmujemy. Nie przeszukujemy struktury. Operujemy tylko na jednym końcu. Interesuje nas wyłącznie „góra” stosu.
W Javie stos najczęściej implementujemy przez interfejs Deque z użyciem klasy ArrayDeque
Na stosie wykonujemy trzy podstawowe operacje.
Dodajemy element na górę przez metodę push(), który umieszcza element na szczycie stosu. Pobieramy i usuwamy przez pop(), który usuwa element ze szczytu stosu. Podglądamy element bez usuwania przez peek(), który zwraca element z góry bez jego usuwania.
Przykład:
Najpierw zdejmujemy „Ela”, potem „Ola”, na końcu „Alfa”. Zachowanie wynika bezpośrednio z zasady LIFO.
Dlaczego nie używamy klasy java.util.Stack
W starszym kodzie można spotkać klasę Stack. Chociaż działa, w nowszym kodzie traktujemy ją jako rozwiązanie legacy (przestarzałe). Wynika to z kilku powodów:
Stackjest synchronizowany, co wprowadza niepotrzebny narzut w aplikacjach jednowątkowych.- Dziedziczy po
Vector, co łamie współczesne zasady projektowania struktur danych. - Ponieważ
Stackjest technicznie listą, udostępnia metody takie jakget(index), które pozwalają sięgać do środka struktury. To pozwala naruszyć logikę LIFO.
W nowoczesnej Javie stos implementujemy przez interfejs Deque, najczęściej używając klasy ArrayDeque. Jest ona szybsza, lżejsza i wymusza stosowanie poprawnych operacji stosowych.
Kolejka
Kolejka działa według zasady First In, First Out (FIFO). Pierwszy element, który dodajemy, jako pierwszy przetwarzamy.
Operujemy na dwóch końcach: dodajemy na końcu i pobieramy z początku.
W Javie używamy interfejsu Queue, najczęściej z implementacją LinkedList lub ArrayDeque.
Na kolejce wykonujemy trzy podstawowe operacje. Dodajemy element przez offer() lub add(). Element trafia na koniec kolejki. Pobieramy i usuwamy element przez poll(). Zawsze zabieramy pierwszy element. Podglądamy pierwszy element przez peek(), bez jego usuwania.
Przykład:
Najpierw obsługujemy „Ala”, potem „Ola”, na końcu „Ela”. Kolejność wejścia definiuje kolejność przetwarzania.
Zastosowania w praktyce
Stosy i kolejki nie są strukturami teoretycznymi. W systemach produkcyjnych pełnią bardzo konkretne role.
Stos w praktyce
Stos wykorzystujemy wszędzie tam, gdzie ważna jest historia operacji lub cofanie ostatnich działań.
- Mechanizm Cofnij (Ctrl+Z) w edytorach tekstu działa w oparciu o stos, gdzie każda akcja jest odkładana na jego szczyt. Gdy cofamy operację, system pobiera ostatni element ze stosu przez
pop()i odwraca zmianę. - Nawigacja wstecz w przeglądarkach internetowych również opiera się na tej samej zasadzie. Każda odwiedzona strona trafia na stos, a przycisk „Wstecz” zdejmuje ostatni zapis i przywraca poprzedni stan.
- Stos wywołań metod (call stack) używany w czasie działania programu i debugowaniu. Gdy uruchamiasz kod, Java używa stosu do zarządzania wywołaniami metod. Każda nowa metoda trafia na górę stosu.
Kolejka w praktyce
Kolejka obsługuje systemy, w których ważna jest kolejność napływu danych lub konieczność buforowania zadań, które nie mogą zostać przetworzone natychmiast.
- Bufory drukarek działają w modelu FIFO. Dokumenty trafiają do kolejki i są drukowane dokładnie w tej samej kolejności, w jakiej zostały wysłane.
- W architekturze mikroserwisów takich jak Kafka czy RabbitMQ, kolejki umożliwiają asynchroniczną komunikację między systemami. Jeśli odbiorca jest przeciążony, wiadomości pozostają w kolejce i czekają na przetworzenie, bez utraty kolejności przetwarzania.
- Algorytmy BFS (Breadth – First Search) wykorzystuje kolejkę do przeszukiwania grafu warstwami. Węzły są dodawane do kolejki w kolejności odkrycia, a następnie przetwarzane dokładnie w tej samej kolejności co pozwala przechodzić graf poziomami.
Współczesne systemy często łączą obie struktury. Serwer WWW może przyjmować requesty użytkowników przez kolejkę FIFO, a następnie w trakcie ich wykorzystuje stos do zarządzania wywołaniami metod i logiką wykonania kodu.
Podsumowanie
Stos i kolejka rozwiązują dwa różne problemy.
Stos daje szybki dostęp do ostatniego elementu. Sprawdza się przy cofaniu operacji, obsłudze historii, czy analizie wyrażeń.
Kolejka pilnuje kolejności przetwarzania. Używamy jej przy obsłudze zadań, kolejkowaniu requestów czy systemach przetwarzania zdarzeń.
W porównaniu do map nie zarządzamy powiązaniami danych, nie pilnujemy unikalności jak w zbiorach, nie skupiamy się na dostępie indeksowym ani przechowywaniu danych jak w kolekcjach i listach, a tablice ze swoim stałym rozmiarem przestają mieć znaczenie. Liczy się wyłącznie kolejność obsługi.
W kolejnej lekcji wprowadzamy lambdy i interfejsy funkcyjne. Zaczynamy przekazywać zachowanie jako argument co upraszcza kod i przygotowuje nas pod bardziej deklaratywny styl pracy z danymi.
O autorze
Tester oprogramowania z pasją do jakości i technologii. Łączy doświadczenie w testach manualnych i automatycznych, koncentrując się przede wszystkim na aplikacjach webowych oraz usługach SOAP i REST. Testowanie to dla niego nie tylko szukanie błędów, ale przede wszystkim kwestionowanie przyjętych założeń i usprawnianie tego, co nie działa – również w samym procesie testowym. Lubi zmieniać, angażować się i aktywnie budować proces testowy, tak by miał sens, a nie tylko formę. Prywatnie fan rocka, biwakowania, podróży.
