Queue, Deque, Stack: praca z kolejkami i stosami

1. Interfejs Queue: klasyczna kolejka (FIFO)

W programowaniu, tak jak w życiu, zdarzają się sytuacje, gdy ważne jest nie tylko przechowywanie zbioru elementów, ale i zarządzanie kolejnością ich przetwarzania. Wyobraź sobie kolejkę w supermarkecie: kto bliżej początku — jest obsługiwany wcześniej. To zasada FIFO — „pierwszy wszedł — pierwszy wyszedł”. A stos talerzy w szafce działa według zasady LIFO — „ostatni wszedł — pierwszy wyszedł”. W Javie tym zasadom odpowiadają kolekcje: kolejki Queue, kolejki dwukierunkowe Deque i stosy Stack.

Zastosowania:

• Przetwarzanie zadań w kolejności napływu (kolejka zadań, drukowanie dokumentów, obsługa zdarzeń).
• Realizacja cofania/powtarzania akcji (undo/redo) — stos.
• Parsowanie wyrażeń, przechodzenie drzew i grafów (przeszukiwanie wszerz/w głąb) i wiele więcej.

Czym jest kolejka?

Kolejka (Queue) — to kolekcja zbudowana według zasady FIFO. Elementy dodaje się na koniec i pobiera z początku. Jak w sklepie: kto przyszedł wcześniej, ten jest obsługiwany pierwszy.

Podstawowe metody interfejsu Queue

offer(e)

add(e)

poll()

remove()

peek()

element()

Zapewne zauważyłeś pary metod o podobnym zachowaniu. Różnica polega na „łagodności”: offer, poll, peek zwracają wartość specjalną w razie niepowodzenia (zwykle null lub false) i nie rzucają wyjątków, natomiast add, remove, element — rzucają wyjątki w sytuacjach brzegowych (pusta kolejka, czasem przepełnienie).

Przykład: kolejka zadań

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Umyć zęby");
        tasks.offer("Zrobić rozgrzewkę");
        tasks.offer("Wypić kawę");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // Pobieramy zadanie z początku kolejki
            System.out.println("Wykonuję: " + task);
        }
    }
}

Wynik:

Wykonuję: Umyć zęby
Wykonuję: Zrobić rozgrzewkę
Wykonuję: Wypić kawę

Dlaczego najczęściej używa się LinkedList?

Interfejs to kontrakt, a implementacji jest kilka. Często używa się LinkedList, ponieważ szybko dodaje/usuwa z obu końców. Jednak świetną alternatywą jest ArrayDeque. Są też wyspecjalizowane warianty: PriorityQueue (kolejka priorytetowa) — o niej niżej.

2. Interfejs Deque: kolejka dwukierunkowa

Deque (Double Ended Queue, „dek”) — kolejka, do której można dodawać i z której można usuwać elementy z obu stron: z początku i z końca. Jak autobus z dwojgiem drzwi: wejść/wyjść można z każdej strony.

Deque = uniwersalny żołnierz: może działać jak zwykła kolejka (FIFO), jak stos (LIFO) i jako hybryda.

Podstawowe metody interfejsu Deque

addFirst(e)

queue.addFirst("A")

addLast(e)

queue.addLast("B")

removeFirst()

queue.removeFirst()

removeLast()

queue.removeLast()

peekFirst()

queue.peekFirst()

peekLast()

queue.peekLast()

offerFirst(e)

queue.offerFirst("C")

offerLast(e)

queue.offerLast("D")

Przykład: Deque jako kolejka i jako stos

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Używamy jako kolejki (FIFO)
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("Kolejka (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // Używamy jako stosu (LIFO)
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("Stos (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

Wynik:

Kolejka (FIFO):
A
B
C
Stos (LIFO):
3
2
1

Dlaczego ArrayDeque?

ArrayDeque — szybka i kompaktowa implementacja Deque oparta na tablicy. Dla stosu i kolejki zwykle jest szybsza i bardziej niezawodna niż stary Stack i nie ma stałego rozmiaru (ogranicza ją jedynie pamięć).

3. Stack: stos — ostatni wszedł, pierwszy wyszedł (LIFO)

Stos — kolekcja zgodna z zasadą LIFO: zdejmujemy element jako ostatnio dodany. W programowaniu stos jest przydatny do historii działań (undo), przechodzenia struktur rekurencyjnych (drzewa/grafy), obliczania wyrażeń itp.

Klasa Stack (i dlaczego nie należy jej używać)

W Javie istnieje klasa Stack, która dziedziczy po przestarzałej Vector. Dziś nie zaleca się jej używania w nowych projektach. Preferowane są Deque/ArrayDeque.

Metody stosu (Deque)

push(e)

pop()

peek()

Uwaga: w Deque operacje te odpowiadają metodom addFirst/removeFirst/peekFirst, ale dla zgodności istnieją też „stosowe” nazwy push/pop/peek.

Przykład: stos na ArrayDeque

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Pierwszy");
        stack.push("Drugi");
        stack.push("Trzeci");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Wynik:

Trzeci
Drugi
Pierwszy

Dlaczego nie Stack?

• Stack jest zsynchronizowany (wolniejszy) i dziedziczy po przestarzałej Vector.
• ArrayDeque jest na ogół szybsza i bardziej kompaktowa, nie blokuje wątków.
• Jeśli widzisz Stack w nowym kodzie — zazwyczaj to kandydat do zastąpienia przez ArrayDeque.

4. Kiedy i czego używać

LinkedList, ArrayDeque, PriorityQueue

ArrayDeque

ArrayDeque, LinkedList

Przykłady z życia:

• Kolejka w banku — Queue.
• Historia działań w edytorze — Stack.
• Kolejka autobusów, wjazd/wyjazd z obu stron — Deque.

5. Przykłady kodu: realizujemy kolejkę i stos w miniaplikacji

Przykład 1: Kolejka drukowania dokumentów

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("Dokument1.pdf");
        printQueue.offer("Dokument2.docx");
        printQueue.offer("Dokument3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("Drukuje się: " + doc);
        }
    }
}

Przykład 2: Stos cofania (undo)

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Wstawienie tekstu");
        undoStack.push("Zmiana koloru");
        undoStack.push("Usunięcie obrazka");

        System.out.println("Ostatnia akcja: " + undoStack.peek()); // Usunięcie obrazka

        while (!undoStack.isEmpty()) {
            System.out.println("Cofanie: " + undoStack.pop());
        }
    }
}

Przykład 3: Kolejka dwustronna

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("Pobieramy z początku: " + deque.removeFirst()); // C
        System.out.println("Pobieramy z końca: " + deque.removeLast());   // D
        System.out.println("Pozostało: " + deque); // [A, B]
    }
}

6. Cechy implementacji i niuanse

• ArrayDeque — najszybsza i najbardziej uniwersalna implementacja kolejki/stosu dla większości zadań.
• LinkedList — również implementuje Deque; może być przydatny, ale dla krótkich kolejek zwykle jest wolniejszy niż ArrayDeque.
• PriorityQueue — kolejka priorytetowa: porządek określa priorytet (naturalny lub przez Comparator), to nie zwykła kolejka FIFO.
• Stack — przestarzały, zsynchronizowany; w nowych projektach preferowana jest ArrayDeque.
• Deque jest wygodny, bo pozwala pracować zarówno z początkiem, jak i z końcem struktury, obejmując scenariusze kolejek i stosów jedną abstrakcją.

7. Typowe błędy przy pracy z kolejkami i stosami

Błąd nr 1: Używanie Stack zamiast Deque.
Wielu początkujących widzi klasę Stack i wybiera ją „po nazwie”. We współczesnych projektach zamiast niej używa się ArrayDeque (lub LinkedList) z metodami push/pop.

Błąd nr 2: Naruszanie zasady działania struktury.
Próby odwoływania się do elementów kolejki/stosu po indeksie, na przykład queue.get(0) lub stack.get(0). Tak nie wolno — używaj odpowiednich metod kolejek i stosów (peek, poll, pop itp.).

Błąd nr 3: Używanie remove()/element()/add() bez sprawdzenia.
Metody remove, element, add mogą rzucić wyjątek przy pustej/przepełnionej strukturze. Bezpieczniej korzystać z „łagodnych” offer, poll, peek, które zwracają wartości specjalne.

Błąd nr 4: Używanie ArrayDeque z elementami null.
ArrayDeque nie dopuszcza null. Próba dodania null spowoduje NullPointerException.

Błąd nr 5: Używanie PriorityQueue jak zwykłej kolejki.
W PriorityQueue porządek określają priorytety (naturalne lub zdefiniowane przez Comparator). Do ścisłego FIFO używaj ArrayDeque lub LinkedList.

Błąd nr 6: Modyfikowanie kolejki/stosu podczas iteracji for-each.
Usuwanie elementów z kolekcji podczas for-each może prowadzić do ConcurrentModificationException. Do usuwania używaj iteratora lub metod poll/pop w pętli, jak pokazano w przykładach.