0Pricing
Java Academy · Lektion

Deque-Operationen: Stack und Queue

Verwenden Sie LinkedList als Deque, um das Verhalten eines Stacks (push/pop) und einer Queue (offer/poll) umzusetzen.

Deque-Operationen: Stack und Queue ist eine kostenlose Java Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Java Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Deque: Warteschlange mit zwei Enden

Eine Deque (Double-Ended Queue) ermöglicht Einfügungen und Entfernungen an beiden Enden. Java's Deque-Schnittstelle wird von LinkedList und ArrayDeque implementiert.

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

ArrayDeque oder LinkedList als Deque

ArrayDeque wird im Allgemeinen gegenüber LinkedList als Deque bevorzugt:

  • Kein zusätzlicher Knotenaufwand pro Element
  • Bessere Cache-Lokalität
  • Etwas schneller bei Stack- und Queue-Operationen

Wählen Sie LinkedList nur, wenn Sie zusätzlich die List-Schnittstelle benötigen.

Stack-Operationen mit Deque

Verwenden Sie push (addFirst) und pop (removeFirst), um einen LIFO-Stack zu simulieren. Vermeiden Sie die veraltete Klasse Stack – sie ist synchronisiert und überholt.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

Queue-Operationen mit Deque

Verwenden Sie offer (addLast) und poll (removeFirst), um eine FIFO-Queue zu simulieren. offer gibt bei einem Fehler false zurück; add löst eine Ausnahme aus.

Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");

System.out.println(queue.poll());  // task1
System.out.println(queue.poll());  // task2
System.out.println(queue.size());  // 1

Referenztabelle für Deque-Methoden

Deque stellt zwei Methodenfamilien bereit – eine, die Ausnahmen auslöst, und eine, die spezielle Werte zurückgibt:

  • addFirst/addLast gegenüber offerFirst/offerLast
  • removeFirst/removeLast gegenüber pollFirst/pollLast
  • getFirst/getLast gegenüber peekFirst/peekLast

Bevorzugen Sie die offer-/poll-/peek-Familie, um Ausnahmen bei leeren Deques zu vermeiden.

Praxisbeispiel: Undo/Redo mit zwei Stacks

Ein klassischer Anwendungsfall für Deque: Der Undo-Verlauf ist ein Stack. Redo ist ein weiterer Stack.

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

Palindromprüfung mit Deque

Deques machen die Prüfung auf Palindrome elegant – Zeichen von beiden Enden werden gleichzeitig verglichen.

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

BFS mit Queue

Die Breitensuche (Breadth-First Search) verwendet eine Queue. ArrayDeque ist die Standardwahl für BFS beim Programmieren von Wettbewerbsaufgaben und beim Durchlaufen von Graphen.

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

DFS mit Stack

Die Tiefensuche (Depth-First Search) verwendet einen Stack. Auch hier sollten Sie ArrayDeque der veralteten Klasse Stack vorziehen.

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

Begrenzte Deque mit Größenprüfung

ArrayDeque wächst dynamisch, aber Sie können die Kapazität manuell begrenzen, um einen Puffer mit fester Größe zu simulieren:

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

Hinweise zur Leistung

ArrayDeque verwendet ein zirkuläres Array, dessen Größe bei voller Belegung verdoppelt wird. Die amortisierten Kosten aller Operationen betragen O(1). Aufgrund der Cache-Effizienz ist ArrayDeque in den meisten Benchmarks schneller als LinkedList. Synchronisieren Sie niemals manuell – verwenden Sie für nebenläufige Verarbeitung ConcurrentLinkedDeque oder eine blockierende Warteschlange.

Kurztest

Welche Klasse sollten Sie für LIFO-Operationen der veralteten Klasse Stack vorziehen?

Zusammenfassung: Deque-Operationen

Die wichtigsten Erkenntnisse:

  • Deque ermöglicht O(1)-Einfügungen und -Entfernungen an beiden Enden
  • ArrayDeque wird für die reine Verwendung als Stack oder Queue gegenüber LinkedList bevorzugt
  • push/pop → LIFO-Stack; offer/poll → FIFO-Queue
  • Klassische Anwendungsfälle: Undo/Redo, BFS/DFS, gleitendes Fenster, Palindromprüfung
  • Vermeiden Sie die veralteten Klassen Stack und Queue

Häufig gestellte Fragen

Ist die Lektion „Deque-Operationen: Stack und Queue“ kostenlos?

Ja — der vollständige Text von „Deque-Operationen: Stack und Queue“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Java Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Deque-Operationen: Stack und Queue“?

Verwenden Sie LinkedList als Deque, um das Verhalten eines Stacks (push/pop) und einer Queue (offer/poll) umzusetzen. Du übst Java Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Java Academy zu starten?

Keine Vorkenntnisse erforderlich. Java Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.

Wie lange dauert die Lektion „Deque-Operationen: Stack und Queue“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Java Academy-Lektion Code schreiben und ausführen?

Ja. Jede Java Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Interna von LinkedList
  2. Deque-Operationen: Stack und Queue
  3. LinkedList vs. ArrayList: Abwägungen
  4. PriorityQueue für geordnete Verarbeitung
← Zurück zu Java Academy