{"id":30256,"date":"2022-06-07T22:01:05","date_gmt":"2022-06-07T20:01:05","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=30256"},"modified":"2024-11-27T15:06:35","modified_gmt":"2024-11-27T14:06:35","slug":"java-deque","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/java-deque\/","title":{"rendered":"Deque-Interface in Java"},"content":{"rendered":"\n

Nachdem Java in Version 5 das Queue-Interface<\/a> bekommen hat, kamen in Java 6 das Interface java.util.Deque<\/code> und die ersten Deque-Implementierungen hinzu.\u00b9<\/p>\n\n\n\n

Die Implementierungen unterscheiden sich in diversen Eigenschaften (wie bounded\/unbounded, blocking\/non-blocking, threadsicher\/nicht threadsicher). Auf diese Eigenschaften werde ich im Verlauf dieses Tutorials eingehen.<\/p>\n\n\n\n

\u00b9 Das stimmt nicht ganz: LinkedList<\/code>, eine der Deque-Implementierungen, gibt es bereits seit Java 1.2.<\/p>\n\n\n\n

Java Deque-Klassenhierarchie<\/h2>\n\n\n\n

Hier siehst du zun\u00e4chst einen \u00dcberblick \u00fcber die Deque-Interfaces und -Klassen in Form eines UML-Klassendiagramms:<\/p>\n\n\n

\n
\"Java
Java Deque-Klassenhierarchie<\/figcaption><\/figure>\n<\/div>\n\n\n

Der kompletten linke Teil des Diagramms wird im Queue-Tutorial<\/a> behandelt.<\/p>\n\n\n\n

Das BlockingDeque-Interface<\/a> werde ich im n\u00e4chsten Teil des Tutorials vorstellen; danach folgen die konkreten Deque-Klassen ArrayDeque<\/a>, LinkedList<\/a>, ConcurrentLinkedDeque<\/a> und LinkedBlockingDeque<\/a>.<\/p>\n\n\n\n

Du kannst jederzeit \u00fcber die Navigation am rechten Rand zu den entsprechenden Teilen der Serie springen.<\/p>\n\n\n\n

Java Deque-Methoden<\/h2>\n\n\n\n

Das Deque<\/code>-Interface erbt von Queue<\/code> und definiert 15 (!) zus\u00e4tzliche Methoden zum Einf\u00fcgen, Entnehmen und Betrachten von Elementen auf beiden Seiten des Deques (12 Deque-Methoden und 3 Stack-Methoden).<\/p>\n\n\n\n

Aus Konsistenzgr\u00fcnden wurden die Operationen, die Deque<\/code> bereits von Queue<\/code> erbt, mit neuem Namen neu implementiert \u2013 beispielsweise Queue.add()<\/code> als Deque.addLast()<\/code> und Queue.remove()<\/code> als Deque.removeFirst()<\/code>.<\/p>\n\n\n\n

Das Deque<\/code>-Interface definiert zus\u00e4tzlich drei Stack-Methoden als Alternativen zu den Deque-Methoden, z. B. Deque.push()<\/code> als Alternative zu Deque.addFirst()<\/code>. Diese Methoden h\u00e4tten eigentlich in ein Stack-Interface<\/a> geh\u00f6rt.<\/p>\n\n\n\n

All diese Queue- und Stack-Methoden habe ich im Folgenden explizit mit aufgef\u00fchrt \u2013 und zwar jeweils bei den \u00e4quivalenten Deque-Methoden.<\/p>\n\n\n\n

Am Ende dieses Kapitels findest du eine zusammenfassende Tabelle.<\/p>\n\n\n\n

Methoden zum Einf\u00fcgen in das Deque<\/h3>\n\n\n\n

Zum Einstieg ein grafischer \u00dcberblick aller Enqueue-Methoden:<\/p>\n\n\n

\n
\"Methoden
Methoden zum Einf\u00fcgen in ein Deque<\/figcaption><\/figure>\n<\/div>\n\n\n

Deque.addFirst() + addLast()<\/h4>\n\n\n\n

Diese Methoden f\u00fcgen ein Element am Kopf bzw. am Ende des Deques ein. Bei Erfolg geben die Methoden true<\/code> zur\u00fcck. Wenn ein gr\u00f6\u00dfenbeschr\u00e4nktes (bounded) Deque voll ist, werfen diese Methoden eine IllegalStateException<\/code>.<\/p>\n\n\n\n

Die vom Queue<\/code>-Interface geerbte Methode Queue.add()<\/code> wird zu Deque.addLast()<\/code> weitergeleitet.<\/p>\n\n\n\n

Die Deque.push()<\/code>-Methode ist das Stack-\u00c4quivalent zu Deque.addFirst()<\/code>.<\/p>\n\n\n\n

Deque.offerFirst() + offerLast()<\/h4>\n\n\n\n

Auch offerFirst()<\/code> und offerLast()<\/code> f\u00fcgen Elemente in das Deque ein und geben im Erfolgsfall true<\/code> zur\u00fcck. Wenn ein bounded Deque voll ist, geben diese Methoden false<\/code> zur\u00fcck anstatt eine IllegalStateException<\/code> zu werfen.<\/p>\n\n\n\n

Die vom Queue<\/code>-Interface geerbte Methode Queue.offer()<\/code> wird zu Deque.offerLast()<\/code> weitergeleitet. <\/p>\n\n\n\n

Methoden zum Entnehmen aus dem Deque<\/h3>\n\n\n\n

Auch f\u00fcr die Dequeue-Methoden zun\u00e4chst ein grafischer \u00dcberblick:<\/p>\n\n\n

\n
\"Methoden
Methoden zum Entfernen aus einem Deque<\/figcaption><\/figure>\n<\/div>\n\n\n

Deque.removeFirst() + removeLast()<\/h4>\n\n\n\n

Die Methoden removeFirst()<\/code> und removeLast()<\/code> entnehmen das Element vom Kopf bzw. Ende des Deques. Wenn das Deque leer ist, werfen sie eine NoSuchElementException<\/code>.<\/p>\n\n\n\n

Die vom Queue<\/code>-Interface geerbte Methode Queue.remove()<\/code> wird zu Deque.removeFirst()<\/code> weitergeleitet.<\/p>\n\n\n\n

Deque.pop()<\/code> ist das Stack-\u00c4quivalent zu Deque.removeFirst()<\/code>.<\/p>\n\n\n\n

Deque.pollFirst() + pollLast()<\/h4>\n\n\n\n

pollFirst()<\/code> und pollLast()<\/code> entnehmen ebenfalls das Element vom Kopf bzw. Ende des Deques. Im Gegensatz zu removeFirst()<\/code> und removeLast()<\/code> werfen diese Methode bei einem leeren Deque keine Exception, sondern geben null<\/code> zur\u00fcck.<\/p>\n\n\n\n

Die vom Queue<\/code>-Interface geerbte Methode Queue.poll()<\/code> wird zu Deque.pollFirst()<\/code> weitergeleitet.<\/p>\n\n\n\n

Methoden zum Betrachten des Head- bzw. Tail-Elements<\/h3>\n\n\n\n

Und zum Abschluss ein grafischer \u00dcberblick der Peek-Methoden:<\/p>\n\n\n

\n
\"Methoden
Methoden zum Betrachten der Elemente am Anfang und Ende des Deques<\/figcaption><\/figure>\n<\/div>\n\n\n

Deque.getFirst() + getLast()<\/h4>\n\n\n\n

Die getFirst()<\/code>- und getLast()<\/code>-Methoden geben das Element vom Kopf bzw. Ende des Deques zur\u00fcck, ohne es aus dem Deque zu entfernen. Wenn das Deque leer ist, werfen diese Methoden eine NoSuchElementException<\/code>.<\/p>\n\n\n\n

Die vom Queue<\/code>-Interface geerbte Methode Queue.element()<\/code> wird zu Deque.getFirst()<\/code> weitergeleitet.<\/p>\n\n\n\n

Deque.peekFirst() + peekLast()<\/h4>\n\n\n\n

Auch peekFirst()<\/code> und peekLast()<\/code> geben das Kopf- bzw. Tail-Element zur\u00fcck, ohne es aus dem Deque zu entfernen. Bei einem leeren Deque werfen diese Methoden allerdings keine Exception, sondern geben null<\/code> zur\u00fcck.<\/p>\n\n\n\n

Die vom Queue<\/code>-Interface geerbte Methode Queue.peek()<\/code> wird zu Deque.peekFirst()<\/code> weitergeleitet. peek()<\/code> ist ebenfalls das Stack-\u00c4quivalent zu peekFirst()<\/code>.<\/p>\n\n\n\n

Deque-Methoden \u2013 Zusammenfassung<\/h3>\n\n\n\n

Die folgende Tabelle zeigt noch einmal alle zw\u00f6lf Deque-Methoden, die drei Stack-Methoden und die weitergeleiteten Queue-Methoden gruppiert nach Operation, Seite des Deques und Art der Fehlerbehandlung:<\/p>\n\n\n\n

<\/th>Kopf des Deques<\/th>Tail des Deques<\/th><\/tr>
<\/th>Exception<\/th>R\u00fcckgabewert<\/th>Exception<\/th>R\u00fcckgabewert<\/th><\/tr><\/thead>
Element
anh\u00e4ngen
(enqueue<\/em>):<\/td>		addFirst(E e)
 
push(E e)<\/code>\u00b2<\/td>		offerFirst(E e)
 
 <\/code><\/td>		addLast(E e)
add(E e)<\/code>\u00b9
 <\/td>		offerLast(E e)
offer(E e)<\/code>\u00b9
 <\/td><\/tr>
Element
entnehmen
(dequeue<\/em>):<\/td>		removeFirst()
remove()<\/code>\u00b9
pop()<\/code>\u00b2<\/td>		pollFirst()
poll()<\/code>\u00b9
 <\/td>		removeLast()
 
 <\/code><\/td>		pollLast()
 
 <\/code><\/td><\/tr>
Element
ansehen
(examine<\/em>):<\/td>		getFirst()
element()<\/code>\u00b9<\/td>		peekFirst()
peek()<\/code>\u00b9 \u00b2<\/td>		getLast()
 <\/code><\/td>		peekLast()
 <\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u00b9 Diese Methoden sind im Queue<\/code>-Interface implementiert und rufen die entsprechenden Deque<\/code>-Methoden auf.<\/p>\n\n\n\n

\u00b2 Diese Stack-Methoden sind zus\u00e4tzlich im Deque<\/code>-Interface definiert. Das JDK enth\u00e4lt leider kein Stack<\/code>-Interface.<\/p>\n\n\n\n

Wie erzeugt man ein Deque?<\/h2>\n\n\n\n

Das Interface java.util.Deque<\/code> kann nicht direkt instatiiert werden. Ein Interface beschreibt lediglich, welche Methoden eine Klasse implementieren muss, die dieses Interface implementiert.<\/p>\n\n\n\n

Es muss also eine konkreten Deque-Implementierungen ausgew\u00e4hlt werden, z. B. ein ArrayDeque<\/code>:<\/p>\n\n\n

Deque<Integer> deque = new<\/span> ArrayDeque<>();<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\n
Die konkreten, vom JDK angebotenen Deque<\/code>-Klassen werden in den folgenden Teilen des Tutorials \u2013 mit Erkl\u00e4rung ihrer Eigenschaften \u2013 vorgestellt:<\/p>\n\n\n\n