Queue, Deque, Stack: Arbeit mit Warteschlangen und Stacks

1. Interface Queue: klassische Warteschlange (FIFO)

In der Programmierung, wie auch im Leben, gibt es Situationen, in denen es nicht nur wichtig ist, eine Menge von Elementen zu speichern, sondern die Reihenfolge ihrer Verarbeitung zu steuern. Denken Sie an die Schlange im Supermarkt: Wer näher am Anfang steht, wird früher bedient. Das ist das FIFO-Prinzip – „zuerst rein – zuerst raus“. Ein Stapel Teller im Schrank funktioniert hingegen nach dem LIFO-Prinzip – „zuletzt rein – zuerst raus“. In Java entsprechen diesen Prinzipien die Collections: Warteschlangen Queue, doppelseitige Warteschlangen Deque und Stacks Stack.

Wo wird es eingesetzt:

• Verarbeitung von Aufgaben in Ankunftsreihenfolge (Aufgabenwarteschlange, Dokumentdruck, Ereignisverarbeitung).
• Implementierung von Undo/Redo (undo/redo) – Stack.
• Parsen von Ausdrücken, Traversieren von Bäumen und Graphen (Breiten-/Tiefensuche) und vieles mehr.

Was ist eine Warteschlange?

Eine Warteschlange (Queue) ist eine Collection, die nach dem FIFO-Prinzip arbeitet. Elemente werden am Ende hinzugefügt und am Anfang entnommen. Wie im Laden: Wer früher kommt, wird zuerst bedient.

Zentrale Methoden des Interfaces Queue

offer(e)

add(e)

poll()

remove()

peek()

element()

Sie haben sicher die methodischen Paare mit ähnlichem Verhalten bemerkt. Der Unterschied liegt in der „Sanftheit“: offer, poll, peek geben im Fehlerfall einen speziellen Wert zurück (typisch null oder false) und werfen keine Exceptions, während add, remove, element in Grenzfällen Exceptions werfen (leere Warteschlange, teils Überlauf).

Beispiel: Aufgabenwarteschlange

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Zähne putzen");
        tasks.offer("Gymnastik machen");
        tasks.offer("Kaffee trinken");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // Aufgabe vom Anfang der Warteschlange nehmen
            System.out.println("Führe aus: " + task);
        }
    }
}

Ausgabe:

Führe aus: Zähne putzen
Führe aus: Gymnastik machen
Führe aus: Kaffee trinken

Warum verwendet man meistens LinkedList?

Ein Interface ist ein Vertrag, und es gibt mehrere Implementierungen. Oft wird LinkedList verwendet, da sie schnell an beiden Enden einfügt/entfernt. Eine ausgezeichnete Alternative ist jedoch ArrayDeque. Es gibt auch spezialisierte Varianten: PriorityQueue (Prioritätswarteschlange), dazu weiter unten.

2. Interface Deque: doppelseitige Warteschlange

Deque (Double Ended Queue, „dek“) ist eine Warteschlange, in der man Elemente an beiden Seiten hinzufügen und entfernen kann: am Anfang und am Ende. Wie ein Bus mit zwei Türen: Ein- und Ausstieg sind auf beiden Seiten möglich.

Deque = Allrounder: kann als normale Warteschlange (FIFO), als Stack (LIFO) oder als Hybrid arbeiten.

Zentrale Methoden des Interfaces 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")

Beispiel: Deque als Warteschlange und als Stack

import java.util.*;

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

        // Als Warteschlange (FIFO) verwenden
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("Warteschlange (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // Als Stack (LIFO) verwenden
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("Stack (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

Ausgabe:

Warteschlange (FIFO):
A
B
C
Stack (LIFO):
3
2
1

Warum ArrayDeque?

ArrayDeque ist eine schnelle und kompakte Deque-Implementierung auf Basis eines Arrays. Für Stack und Warteschlange ist sie in der Regel schneller und zuverlässiger als der alte Stack und hat keine feste Größe (nur durch den Speicher begrenzt).

3. Stack: zuletzt rein, zuerst raus (LIFO)

Ein Stack ist eine Collection nach dem LIFO-Prinzip: Das oberste Element ist das zuletzt hinzugefügte. In der Programmierung ist ein Stack nützlich für Verlauf/History (Undo), das Traversieren rekursiver Strukturen (Bäume/Graphen), die Auswertung von Ausdrücken usw.

Die Klasse Stack (und warum sie nicht verwendet werden sollte)

In Java gibt es die Klasse Stack, die von dem veralteten Vector erbt. Heute wird sie für neue Projekte nicht empfohlen. Bevorzugt werden Deque/ArrayDeque.

Stack-Methoden (über Deque)

push(e)

pop()

peek()

Achtung: in Deque entsprechen diese Operationen den Methoden addFirst/removeFirst/peekFirst, aber zur Kompatibilität gibt es auch die „Stack“-Namen push/pop/peek.

Beispiel: Stack mit ArrayDeque

import java.util.*;

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

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

Ausgabe:

Dritter
Zweiter
Erster

Warum nicht Stack?

• Stack ist synchronisiert (langsamer) und erbt von dem veralteten Vector.
• ArrayDeque ist oft schneller und kompakter, blockiert keine Threads.
• Wenn Sie Stack in neuem Code sehen – meist ein Kandidat für ArrayDeque.

4. Wann welche Struktur verwenden

LinkedList, ArrayDeque, PriorityQueue

ArrayDeque

ArrayDeque, LinkedList

Beispiele aus dem Alltag:

• Schlange in der Bank – Queue.
• Aktionsverlauf im Editor – Stack.
• Busreihe mit Ein-/Ausfahrt von beiden Seiten – Deque.

5. Codebeispiele: Warteschlange und Stack in einer Mini-App

Beispiel 1: Druckwarteschlange

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("Wird gedruckt: " + doc);
        }
    }
}

Beispiel 2: Undo-Stack

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Texteinfügung");
        undoStack.push("Farbänderung");
        undoStack.push("Bild löschen");

        System.out.println("Letzte Aktion: " + undoStack.peek()); // Bild löschen

        while (!undoStack.isEmpty()) {
            System.out.println("Rückgängig: " + undoStack.pop());
        }
    }
}

Beispiel 3: Doppelseitige Warteschlange

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("Entnahme vom Anfang: " + deque.removeFirst()); // C
        System.out.println("Entnahme vom Ende: " + deque.removeLast());   // D
        System.out.println("Übrig: " + deque); // [A, B]
    }
}

6. Implementierungsdetails und Feinheiten

• ArrayDeque ist die schnellste und vielseitigste Implementierung für Warteschlange/Stack in den meisten Fällen.
• LinkedList implementiert ebenfalls Deque; kann nützlich sein, ist bei kurzen Warteschlangen aber oft langsamer als ArrayDeque.
• PriorityQueue ist eine Prioritätswarteschlange: Die Reihenfolge wird durch Priorität bestimmt (natürlich oder via Comparator), es ist keine normale FIFO-Warteschlange.
• Stack ist veraltet und synchronisiert; in neuen Projekten ist ArrayDeque vorzuziehen.
• Deque ist praktisch, weil sie sowohl mit Anfang als auch Ende der Struktur arbeitet und so Warteschlangen- und Stack-Szenarien mit einer Abstraktion abdeckt.

7. Typische Fehler beim Arbeiten mit Warteschlangen und Stacks

Fehler Nr. 1: Verwendung von Stack statt Deque.
Viele Einsteiger sehen die Klasse Stack und wählen sie „wegen des Namens“. In modernen Projekten verwendet man stattdessen ArrayDeque (oder LinkedList) mit den Methoden push/pop.

Fehler Nr. 2: Verletzung des Strukturprinzips.
Es wird versucht, auf Elemente der Warteschlange/des Stacks per Index zuzugreifen, z. B. queue.get(0) oder stack.get(0). Das ist falsch – verwenden Sie die passenden Methoden von Warteschlangen und Stacks (peek, poll, pop usw.).

Fehler Nr. 3: Verwendung von remove()/element()/add() ohne Prüfung.
Die Methoden remove, element, add können bei leerer/überfüllter Struktur eine Exception werfen. Sicherer sind die „weichen“ offer, poll, peek, die spezielle Werte zurückgeben.

Fehler Nr. 4: Verwendung von ArrayDeque mit null-Elementen.
ArrayDeque erlaubt kein null. Ein Versuch, null hinzuzufügen, führt zu NullPointerException.

Fehler Nr. 5: Verwendung von PriorityQueue als normale Warteschlange.
In PriorityQueue wird die Reihenfolge durch Prioritäten bestimmt (natürlich oder über einen Comparator). Für striktes FIFO verwenden Sie ArrayDeque oder LinkedList.

Fehler Nr. 6: Modifikation der Warteschlange/des Stacks während eines for-each-Durchlaufs.
Das Entfernen von Elementen aus einer Collection während eines for-each kann zu ConcurrentModificationException führen. Zum Entfernen verwenden Sie einen Iterator oder die Methoden poll/pop in einer Schleife, wie in den Beispielen gezeigt.

1

Aufgabe

JAVA 25 SELF, Level 27, Lektion 2

Gesperrt

Vorschau auf die nächste Aufgabe im System 💼

Vorschau auf die nächste Aufgabe im System 💼

Öffnen

1

Aufgabe

JAVA 25 SELF, Level 27, Lektion 2

Gesperrt

Druckersimulation und Aktionsverlauf 🖨️🔄

Druckersimulation und Aktionsverlauf 🖨️🔄

Öffnen