Java ArrayDeque-Klasse | W3Docs Learn Java

ArrayDeque<E> ist ein zirkuläres Array, das bei Bedarf wächst. Es implementiert sowohl Queue<E> als auch Deque<E> und kann daher ohne Codeänderungen als FIFO-Warteschlange, LIFO-Stack oder doppelseitige Warteschlange eingesetzt werden. Das Javadoc zu Stack empfiehlt Deque gegenüber der Legacy-Klasse; das Javadoc zu Deque ergänzt die praktische Empfehlung, dass ArrayDeque Ihre Standardimplementierung sein sollte. Es ist fast immer schneller als LinkedList, verbraucht weniger Speicher und ist die bevorzugte Wahl der Standardbibliothek, sobald man das List-Interface nicht mehr benötigt.

Warum ein zirkuläres Array

Eine klassische „Warteschlange aus einem Array" hat ein Problem: Nach wenigen Zyklen von Hinzufügen am Ende und Entfernen am Anfang füllt sich das Array am Ende, während am Anfang leere Slots entstehen. Eine naive Lösung wäre, bei jedem Entfernen alles nach links zu verschieben — O(n) pro Entfernung, was die Performance ruiniert.

Der zirkuläre-Array-Trick löst das Problem. Die Klasse hält zwei Indizes, head und tail, und lässt sie über das Ende hinauslaufen:

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst dekrementiert head, addLast inkrementiert tail, beides modulo der Array-Länge. removeFirst und removeLast machen das Umgekehrte. Jede Operation ist O(1); die einzigen Kosten entstehen beim Verdoppeln des Backing-Arrays, wenn head mit tail kollidieren würde — dies wird amortisiert.

Das Ergebnis: keine Knoten-Allokation pro Element, keine Zeiger-Verfolgung, cache-freundlicher Zugriff. Das ist der technische Grund, warum ArrayDeque für Warteschlangen- und Stack-Workloads meist die schnellste Wahl ist.

Das Deque-Interface im Überblick

Ein Deque hat zwei Enden. Jede Operation gibt es in drei Varianten:

Operation	Erstes (head) — wirft Exception	Erstes (head) — Sonderwert	Letztes (tail) — wirft Exception	Letztes (tail) — Sonderwert
Einfügen	`addFirst(e)`	`offerFirst(e)`	`addLast(e)`	`offerLast(e)`
Entfernen	`removeFirst()`	`pollFirst()`	`removeLast()`	`pollLast()`
Betrachten	`getFirst()`	`peekFirst()`	`getLast()`	`peekLast()`

Darüber hinaus werden die Queue- und Stack-Synonyme auf das head-Ende abgebildet:

Queue-Methode	Deque-Äquivalent
`add(e)` / `offer(e)`	`addLast(e)` / `offerLast(e)`
`remove()` / `poll()`	`removeFirst()` / `pollFirst()`
`element()` / `peek()`	`getFirst()` / `peekFirst()`

Stack-Methode	Deque-Äquivalent
`push(e)`	`addFirst(e)`
`pop()`	`removeFirst()`
`peek()`	`peekFirst()`

Deque ist also ein Interface, das gleichzeitig eine Warteschlange und einen Stack bereitstellt — je nachdem, welchen Namen man für das head-Ende verwendet. Diese Abbildungen wurden in den Kapiteln zu Queue und Stack behandelt; Deque ist der Punkt, an dem sie zusammenlaufen.

Was `ArrayDeque` zusätzlich bietet

In der Praxis ist es API-seitig kaum mehr — das ist der Sinn. Die Klasse stellt den Deque-Vertrag zuverlässig bereit: die zwei Enden, die drei Fehlerbehandlungsstile pro Operation sowie clear(), iterator(), descendingIterator(), contains, size, isEmpty. Die Iteration mit dem Standarditerator erfolgt von head nach tail; descendingIterator ist der günstige Weg, von tail nach head zu traversieren, ohne umzukehren.

Die Konstruktoren entsprechen denen von ArrayList:

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Vorbelegen, wenn die Arbeitslast bekannt ist. Der Standardwert 16 wird auf die nächste Zweierpotenz aufgerundet, und das Wachstum verdoppelt das Array — eine Million offerLast-Aufrufe ausgehend von einem Standard-Deque lösen etwa 16 Vergrößerungs- und Kopiervorgänge aus.

Die Regeln: keine null-Werte, nicht thread-sicher, fail-fast

Drei Regeln, die man verinnerlichen sollte:

ArrayDeque lässt keine null-Elemente zu. Jeder Einfügevorgang wirft eine NullPointerException. So bleibt eindeutig, dass pollFirst() bei einer leeren Deque null zurückgibt.
Nicht thread-sicher. Zwei Threads, die dieselbe ArrayDeque verändern, korrumpieren sie. Für parallelen Zugriff sollte man ConcurrentLinkedDeque (sperrfrei, unbegrenzt) oder LinkedBlockingDeque (begrenzt, blockierend) verwenden.
Fail-fast-Iteration. Eine Änderung der Deque außerhalb des Iterators während der Iteration wirft eine ConcurrentModificationException. Verwende Iterator.remove() oder removeIf für sichere Mutation.

Wann `ArrayDeque` gegenüber Alternativen bevorzugt werden sollte

Der Entscheidungsfluss:

Brauche ich eine Queue? → ArrayDeque. Standardwahl.
Brauche ich einen Stack? → ArrayDeque. Standardwahl. push / pop / peek verwenden.
Brauche ich eine Deque? → ArrayDeque. Standardwahl.
Brauche ich sowohl Deque- als auch List-Semantik am selben Objekt? → LinkedList. Selten.
Brauche ich eine Prioritätsreihenfolge? → PriorityQueue. Andere Abstraktion.
Brauche ich gleichzeitigen Zugriff? → ConcurrentLinkedDeque (unbegrenzt) oder LinkedBlockingDeque (begrenzt). Die richtige Wahl hängt davon ab, ob Gegendruck benötigt wird.

Das Javadoc formuliert die Empfehlung im Klartext: „This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." Das stammt direkt von den JDK-Autoren und ist wörtlich zu nehmen.

Ein durchgearbeitetes Beispiel: Warteschlange, Stack, Deque, gleitendes Fenster

Das folgende Programm verwendet eine ArrayDeque-Instanz als FIFO-Warteschlange, eine weitere als LIFO-Stack und eine dritte als Speicher hinter einem gleitenden Fenster-Maximum — ein klassisches Problem, bei dem ArrayDeque die Lehrbuchantwort ist, weil man günstige Mutation an beiden Enden benötigt.

java— editable, runs on the server

import java.util.*;

public class ArrayDequeShowcase {
  public static void main(String[] args) {
    // --- 1. FIFO queue ---
    Deque<String> queue = new ArrayDeque<>();
    queue.offerLast("a"); queue.offerLast("b"); queue.offerLast("c");
    System.out.println("FIFO order:  poll=" + queue.pollFirst()
        + " poll=" + queue.pollFirst()
        + " poll=" + queue.pollFirst());

// --- 2. LIFO stack ---
    Deque<String> stack = new ArrayDeque<>();
    stack.push("a"); stack.push("b"); stack.push("c");
    System.out.println("LIFO order:  pop=" + stack.pop()
        + " pop=" + stack.pop()
        + " pop=" + stack.pop());

// --- 3. Iteration: head-to-tail vs descending ---
    Deque<Integer> ints = new ArrayDeque<>(List.of(1, 2, 3, 4, 5));
    System.out.print("forward:  "); ints.forEach(x -> System.out.print(x + " "));
    System.out.println();
    System.out.print("reverse:  ");
    Iterator<Integer> r = ints.descendingIterator();
    while (r.hasNext()) System.out.print(r.next() + " ");
    System.out.println();

// --- 4. Null rejection ---
    try { ints.offerLast(null); }
    catch (NullPointerException e) {
      System.out.println("offerLast(null) → " + e.getClass().getSimpleName());
    }

// --- 5. Sliding window maximum — the canonical ArrayDeque algorithm ---
    int[] xs = { 1, 3, -1, -3, 5, 3, 6, 7 };
    int k = 3;
    System.out.println("\nsliding window max, k=" + k + ", input=" + Arrays.toString(xs));
    System.out.println("output=" + Arrays.toString(slidingMax(xs, k)));
  }

// O(n) algorithm: deque holds indices, kept in decreasing order of xs[i].
  // Push at the tail, pop from the head when out of window — both O(1).
  static int[] slidingMax(int[] xs, int k) {
    int[] out = new int[xs.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < xs.length; i++) {
      while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
      while (!dq.isEmpty() && xs[dq.peekLast()] < xs[i]) dq.pollLast();
      dq.offerLast(i);
      if (i >= k - 1) out[i - k + 1] = xs[dq.peekFirst()];
    }
    return out;
  }
}

Was man aus diesem Ablauf mitnehmen kann:

Abschnitte 1 und 2 zeigen dieselbe Klasse, die zwei Aufgaben übernimmt, indem verschiedene Methoden aufgerufen werden. FIFO-Warteschlange: offerLast / pollFirst. LIFO-Stack: push / pop. Es gibt keine separate Klasse zu erlernen.
descendingIterator() ist der günstige Rückwärtsdurchlauf — nützlich, wenn man eine Deque als Stack aufgebaut hat und sie von unten nach oben ausgeben möchte.
Die Sliding-Window-Funktion verwendet beide Enden in derselben Schleife — pollFirst, um Indizes zu entfernen, die aus dem Fenster gefallen sind, pollLast, um einen monoton absteigenden Stack zu erhalten, peekFirst, um das aktuelle Maximum zu lesen. Dieser beidseitige Zugriff ist der Grund, warum ArrayDeque existiert; der Versuch, dies mit einer ArrayList zu tun, wäre quadratisch.

Was kommt als Nächstes

Du hast gesehen, wie ArrayDeque beide Enden der Warteschlangen-/Stack-Geschichte implementiert. Das Interface, das es die ganze Zeit implementiert, verdient ein eigenes Kapitel — Deque ist der Vertrag, der alles zusammenführt, was wir über warteschlangenartige Collections behandelt haben. Das nehmen wir in der nächsten Sitzung auf.

Übungen

Übung

Du benötigst einen schnellen LIFO-Stack für `String`-Token und weißt, dass du den Inhalt zum Debuggen von unten nach oben iterieren wirst. Welche Deklaration entspricht der modernen Empfehlung?

`Deque<String> tokens = new ArrayDeque<>();` dann `push`/`pop`/`peek`, plus `descendingIterator()` für das Traversieren von unten nach oben in O(n)`Stack<String> tokens = new Stack<>();` — die dedizierte Klasse signalisiert die Absicht und unterstützt `get(0)` für das unterste Element`List<String> tokens = new LinkedList<>();` mit `add(0, x)` und `remove(0)` für push/pop`PriorityQueue<String> tokens = new PriorityQueue<>(Comparator.reverseOrder());` — umgekehrte Reihenfolge lässt sie wie einen Stack wirken