Deque<\/code> und Stack<\/code>?<\/li>- Warum sollten wir
Deque<\/code> statt Stack<\/code> verwenden?<\/li><\/ul>\n\n\n\nSchauen wir uns zun\u00e4chst einmal die Datenstrukturen an...<\/p>\n\n\n\n
Unterschied zwischen Deque und Stack<\/h2>\n\n\n\n
Ein Stack ist eine Datenstruktur, die nach dem LIFO-Prinzip arbeitet: Elemente, die zuletzt auf den Stack gelegt werden, werden als erstes wieder entnommen \u2013 und umgekehrt:<\/p>\n\n\n
\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/stack-data-structure.v2-600x281.png\")
Stack-Datenstruktur<\/figcaption><\/figure>\n<\/div>\n\n\nWeitere Details findest du im Hauptartikel \u00fcber die Stack-Datenstruktur<\/a>.<\/p>\n\n\n\nEin Deque (ausgesprochen \"Deck\") hingegen ist eine Datenstruktur, bei der Elemente auf zwei Seiten eingef\u00fcgt und entnommen werden k\u00f6nnen:<\/p>\n\n\n
\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/deque-data-structure.v4-800x135.png\")
Deque-Datenstruktur<\/figcaption><\/figure>\n<\/div>\n\n\nDetails findest du im Hauptartikel \u00fcber die Deque-Datenstruktur<\/a>.<\/p>\n\n\n\nEin Deque kann als Stack eingesetzt werden, indem Elemente an derselben Seite eingef\u00fcgt und wieder entnommen werden.<\/p>\n\n\n\n
Unterschied zwischen Java Stack und Deque<\/h2>\n\n\n\n
In diesem Abschnitt geht es um die Unterschiede zwischen dem Java-Interface java.util.Deque<\/code> und der Klasse java.util.Stack<\/code>.<\/p>\n\n\n\nKlasse vs. Interface<\/h3>\n\n\n\n
Stack<\/code> ist eine Klasse (\u2192 alle Details \u00fcber die Stack-Klasse<\/a>), also eine konkrete Implementierung des Stack-Datentyps. <\/p>\n\n\n\nDeque<\/code> hingegen ist ein Interface (\u2192 alle Details \u00fcber das Deque-Interface<\/a>) und hat mehrere Implementierungen mit unterschiedlichen Eigenschaften. Du kannst also \u2013 basierend auf deinen Anforderungen \u2013 eine geeignete Deque-Implementierung ausw\u00e4hlen<\/a>.<\/p>\n\n\n\nThread-Sicherheit<\/h3>\n\n\n\n
Bei der Klasse Stack<\/code> sind alle Methoden mit dem synchronized<\/code>-Keyword versehen. Du kannst Stack<\/code> also problemlos in einer Multithreading-Anwendung einsetzen. <\/p>\n\n\n\nF\u00fcr eine single-threaded Anwendung ist diese Synchronisation allerdings \u00fcberfl\u00fcssig und w\u00fcrde die Performance negativ beeinflussen. Au\u00dferdem ist die Synchronisation durch pessimistische Locks nur in Situationen mit einer hohen Anzahl an Zugriffskonflikten (\"thread contention\") sinnvoll. Andernfalls ist optimistisches Locking sinnvoller.<\/p>\n\n\n\n
Das JDK bietet zum einen nicht-threadsichere Implementierungen, die ohne Locks arbeiten (ArrayDeque<\/a> und LinkedList<\/a>) \u2013 und zum anderen threadsichere Implementierungen, die ein pessimistisches Lock (LinkedBlockingDeque<\/a>) oder optimistischen Locking (ConcurrentLinkedDeque<\/a>) verwenden.<\/p>\n\n\n\nIteration<\/h3>\n\n\n\n
Da Stack<\/code> und Deque<\/code> Collections sind, implementieren sie letztendlich das Iterable<\/code>-Interface, so dass wir komfortabel \u00fcber die enthaltenen Elemente iterieren k\u00f6nnen.<\/p>\n\n\n\nAllerdings unterscheidet sich die Reihenfolge, in der die Iteratoren von Stack und Deque arbeiten, wie das folgende Beispiel zeigt:<\/p>\n\n\n
Stack<String> stack = new<\/span> Stack();\nstack.push(\"A\"<\/span>);\nstack.push(\"B\"<\/span>);\nstack.push(\"C\"<\/span>);\n\nSystem.out.println(\"Stack: \"<\/span>);\nfor<\/span> (String s : stack) {\n System.out.println(s);\n}\n\nDeque<String> deque = new<\/span> ArrayDeque();\ndeque.push(\"A\"<\/span>);\ndeque.push(\"B\"<\/span>);\ndeque.push(\"C\"<\/span>);\n\nSystem.out.println(\"\\nDeque: \"<\/span>);\nfor<\/span> (String s : deque) {\n System.out.println(s);\n}<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\nDie Ausgabe dieses Beispiel-Codes lautet:<\/p>\n\n\n
Stack: \nA\nB\nC\n\nDeque: \nC\nB\nA<\/code><\/span>Code-Sprache:<\/span> Klartext<\/span> (<\/span>plaintext<\/span>)<\/span><\/small><\/pre>\n\n\nDer Iterator von Stack<\/code> iteriert \u00fcber die Elemente von unten nach oben, also in der Reihenfolge des Einf\u00fcgens. Der Iterator von Deque<\/code> hingegen iteriert von oben nach unten, also in Entnahmereihenfolge.<\/p>\n\n\n\nUm \u00fcber ein Deque<\/code> in Einf\u00fcgereihenfolge zu iterieren, kann \u00fcber die Methode descendingIterator()<\/code> ein entsprechender Iterator abgerufen werden:<\/p>\n\n\nfor<\/span> (Iterator<String> iterator = deque.descendingIterator(); iterator.hasNext(); ) {\n String s = iterator.next();\n \/\/ ... do something with s ...<\/span>\n}\n<\/code><\/span>Code-Sprache:<\/span> Java<\/span> (<\/span>java<\/span>)<\/span><\/small><\/pre>\n\n\nVerletzung des Interface-Segregation-Prinzips<\/h3>\n\n\n\n
Sowohl Stack<\/code> als auch Deque<\/code> bieten weitaus mehr Methoden, als diese Datenstrukturen eigentlich anbieten sollten und verletzen damit das Interface-Segregation-Prinzip<\/a>.<\/p>\n\n\n\nBeide erben Methoden wie remove()<\/code>, removeIf()<\/code>, removeAll()<\/code> und ratainAll()<\/code> von Collection<\/code>. Mit diesen Methoden k\u00f6nnen Elemente aus der Mitte des Stacks bzw. des Deques entfernt werden.<\/p>\n\n\n\nStack<\/code> bietet au\u00dferdem eine insertElementAt()<\/code>-Methode, um ein Element an beliebiger Position des Stacks einzuf\u00fcgen.<\/p>\n\n\n\nDeque<\/code> bietet die Methoden removeFirstOccurrence()<\/code> und removeLastOccurrence()<\/code>, mit denen ebenfalls Elemente entnommen werden k\u00f6nnen, die nicht am Kopf bzw. Ende des Deques liegen.<\/p>\n\n\n\nWie ein Stack-Interface eigentlich aussehen sollte, erf\u00e4hrst du im Artikel \"Stack in Java implementieren<\/a>\".<\/p>\n\n\n\nWie ein Deque-Interface aussehen sollte, liest du in \"Deque mit einem Array implementieren<\/a>\".<\/p>\n\n\n\nWarum wir Deque statt Stack verwenden sollten<\/h2>\n\n\n\n
Als in Java 6 das Deque<\/code>-Interface eingef\u00fchrt wurde, wurde die Stack<\/code>-Klasse mit folgendem Hinweis versehen:<\/p>\n\n\n\n\"A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.\"<\/em><\/p>\n\n\n\nDass das Deque-Interface konsistenter ist als Stack, sehe ich nicht. Beide Interfaces haben zahlreiche Methoden, die eine Stack- bzw. eine Deque-Datenstruktur eigentlich nicht haben sollte (s. Abschnitt \"Verletzung des Interface-Segregation-Prinzips<\/a>\" oben).<\/p>\n\n\n\nDennoch stimme ich zu, dass wir fortan Deque<\/code> verwenden sollten. Deque<\/code> ist ein Interface und bietet mehrere Implementierungen mit verschiedenen Eigenschaften (s. Abschnitt \"Thread-Sicherheit<\/a>\" oben), w\u00e4hrend wir bei Stack<\/code> auf eine Implementierung festgelegt sind.<\/p>\n\n\n\nWenn wir beispielsweise von nur einem Thread auf unseren Stack zugreifen, ist die Synchronisation von Stack<\/code> \u00fcberfl\u00fcssig, und wir sollten lieber ein ArrayDeque einsetzen.<\/p>\n\n\n\nSch\u00f6ner w\u00e4re es allerdings, wenn die Java-Entwickler zus\u00e4tzlich ein Stack-Interface eingef\u00fchrt h\u00e4tten.<\/p>\n\n\n\n
Zusammenfassung<\/h2>\n\n\n\n
In diesem Artikel hast du die Unterschiede zwischen den Datenstrukturen Stack und Deque sowie den entsprechenden Java-Klassen bzw. -Interfaces kennengelernt. Du hast au\u00dferdem erfahren, warum du Javas Stack<\/code>-Klasse nicht mehr verwenden solltest. Die geeignete Deque-Implementierung f\u00fcr deinen Use Case findest du im Artikel \"Java Deque-Implementierungen \u2013 Welche einsetzen?<\/a>\"<\/p>\n\n\n\n