Falls du den Artikel \"Queue mit einem Array implementieren<\/a>\" gelesen hast, wird dir vieles bekannt vorkommen. Denn die Deque-Implementierung ist im Grunde eine Erweiterung der Queue-Implementierung.<\/p>\n\n\n\n Beginnen wir mit dem bounded<\/em> Deque...<\/p>\n\n\n\n Wir beginnen mit einem leeren Array sowie zwei Variablen:<\/p>\n\n\n\n Wir lassen die Index-Variablen zun\u00e4chst auf die Mitte des Arrays zeigen, so dass wir ausreichend Platz haben, um sowohl am Kopf als auch am Ende des Deques Elemente hinzuzuf\u00fcgen:<\/p>\n\n\n Um ein Element am Ende des Deques hinzuzuf\u00fcgen, speichern wir es in demjenigen Arrayfeld, auf das Die folgende Grafik zeigt das Deque, nachdem wir die Elemente \"banana\" und \"cherry\" am Ende des Deques eingef\u00fcgt haben:<\/p>\n\n\n Um ein Element am Kopf des Deques einzuf\u00fcgen, verringern wir In der folgenden Grafik siehst du, wie die Elemente \"grape\", \"lemon\" und \"coconut\" (in dieser Reihenfolge) am Kopf des Deques eingef\u00fcgt wurden:<\/p>\n\n\n Um Elemente zu entnehmen gehen wir genau andersherum vor.<\/p>\n\n\n\n Um ein Element vom Ende des Deques zu entnehmen, verringern wir Die folgende Grafik zeigt das Deque, nachdem wir drei Elemente am Ende (\"cherry\", \"banana\", \"grape\") entnommen haben:<\/p>\n\n\n Um ein Element am Kopf des Deques zu entnehmen, lesen wir das Array an Position Die folgende Grafik zeigt das Deque, nachdem wir ein Element vom Kopf des Deques (\"coconut\") entnommen haben:<\/p>\n\n\n Damit haben wir die Funktionsweise der vier Grundfunktionen des Deques \u2013 Enqueue at front<\/em>, Enqueue at back<\/em>, Deque at front<\/em> und Deque at back<\/em> \u2013 behandelt.<\/p>\n\n\n\n Allerdings k\u00f6nnten wir (ohne zus\u00e4tzliche Logik) am Kopf des Deques nur noch zwei Elemente hinzuf\u00fcgen, obwohl erst eines von acht Feldern belegt ist. Ebenso k\u00f6nnten wir am Ende des Deques maximal f\u00fcnf Elemente anh\u00e4ngen.<\/p>\n\n\n\n Um das Deque bis zur Kapazit\u00e4tsgrenze auff\u00fcllen zu k\u00f6nnen (egal in welcher Richtung), m\u00fcssen wir aus dem Array einen Ringbuffer (englisch: \"circular array\") machen.<\/p>\n\n\n\n Wie das funktioniert, erf\u00e4hrst du im n\u00e4chsten Abschnitt.<\/p>\n\n\n\n Um zu zeigen, wie ein Ringbuffer funktioniert, habe ich das Array aus dem vorherigen Beispiel kreisf\u00f6rmig dargestellt:<\/p>\n\n\n Um Elemente am Kopf des Deques einzuf\u00fcgen, schreiben wir diese entgegen dem Uhrzeigersinn in das Array. Das folgende Beispiel zeigt, die die Elemente \"mango\", \"fig\", \"pomelo\" und \"apricot\" an die Positionen 1, 0, 7 und 6 eingef\u00fcgt wurden:<\/p>\n\n\n Wenn wir das Array wieder \"flach\" darstellen, sieht es wie folgt aus. Der \u00dcbersicht halber habe ich am Kopf des Deques einen Pfeil hinzugef\u00fcgt.<\/p>\n\n\n In beiden Darstellungen ist gut erkennbar, dass vor dem Element \"fig\" an Index 0 das Element \"pomelo\" an Index 7 steht.<\/p>\n\n\n\n Analog dazu f\u00fcgen wir Elemente am Ende des Deques ein und entnehmen Elemente. Zusammengefasst gehen wir bei den Operationen wie folgt vor:<\/p>\n\n\n\n Die Indexe 8 und 7 gelten f\u00fcr das Beispiel oben. Allgemein verwenden wir Sowohl bei einem vollen als auch bei einem leeren Deque zeigen Es gibt noch andere M\u00f6glichkeiten, um ein volles von einem leeren Deque zu unterscheiden:<\/p>\n\n\n\n Die Implementierung des oben beschriebenen Algorithmus ist nicht kompliziert, wie du im folgenden Beispiel-Code sehen wirst. Du findest den Code in der Klasse BoundedArrayDeque<\/a> im GitHub-Repository.<\/p>\n\n\nImplementierung eines bounded Deque mit einem Array<\/h2>\n\n\n\n
headIndex<\/code> \u2013 zeigt auf den Kopf des Deques, also das Element, das vom Kopf des Deques als n\u00e4chstes entnommen werden w\u00fcrde<\/li>tailIndex<\/code> \u2013 zeigt auf ein Feld rechts neben dem Ende des Deques, also das Feld, das am Ende des Deques als n\u00e4chstes gef\u00fcllt werden w\u00fcrde<\/li>numberOfElements<\/code> \u2013 die Anzahl der Elemente im Deque<\/li><\/ul>\n\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-empty-800x194.png\")
Funktionsweise der Enqueue-Operationen<\/h3>\n\n\n\n
tailIndex<\/code> zeigt; danach erh\u00f6hen wir tailIndex<\/code> um 1.<\/p>\n\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-enqueue-at-back-800x194.png\")
headIndex<\/code> um 1 und speichern das Element dann in demjenigen Arrayfeld, auf das headIndex<\/code> zeigt.<\/p>\n\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-enqueue-at-front.v2-800x194.png\")
Funktionsweise der Dequeue-Operationen<\/h3>\n\n\n\n
tailIndex<\/code> um 1, lesen das Array an Position tailIndex<\/code> aus und setzen dieses Feld dann auf null<\/code>.<\/p>\n\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-dequeue-at-back-800x194.png\")
headIndex<\/code> aus, setzen das Feld auf null<\/code> und erh\u00f6hen headIndex<\/code> um 1.<\/p>\n\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-dequeue-at-front-800x194.png\")
Ringbuffer<\/h3>\n\n\n\n
![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-1-element-400x343.png\")
<\/figure>\n<\/div>\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-5-elements-400x344.png\")
<\/figure>\n<\/div>\n\n\n![\"Deque](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/05\/implement-deque-using-circular-array-flat-800x194.png\")
tailIndex<\/code> um 1; wenn tailIndex<\/code> 8 erreicht, setze es auf 0.<\/li>headIndex<\/code> um 1; wenn headIndex<\/code> -1 erreicht, setze es auf 7.<\/li>tailIndex<\/code> um 1; wenn tailIndex<\/code> -1 erreicht, setze es auf 7.<\/li>headIndex<\/code> um 1; wenn headIndex<\/code> 8 erreicht, setze es auf 0.<\/li><\/ul>\n\n\n\nelements.length<\/code> statt 8 und element.length - 1<\/code> statt 7. <\/p>\n\n\n\nVolles Deque vs. leeres Deque<\/h3>\n\n\n\n
tailIndex<\/code> und headIndex<\/code> auf dasselbe Arrayfeld. Um zu erkennen, ob das Deque voll oder leer ist, speichern wir zus\u00e4tzlich die Anzahl der Elemente in numberOfElements<\/code>.<\/p>\n\n\n\ntailIndex<\/code> oder<\/em> den headIndex<\/code>. Den jeweils anderen Index k\u00f6nnen wir dann durch Addition oder Subtraktion der Anzahl der Elemente berechnen. Diese Variante f\u00fchrt zu komplexerem und schlechter lesbaren Code.<\/li>tailIndex<\/code> und headIndex<\/code> identisch sind \u2013 das Array an dieser Position leer ist.<\/li>numberOfElements<\/code>-Variable.<\/li><\/ul>\n\n\n\nQuellcode f\u00fcr das bounded Deque mit einem Array<\/h2>\n\n\n\n
public<\/span> class<\/span> BoundedArrayDeque<\/span><E<\/span>> implements<\/span> Deque<\/span><E<\/span>> <\/span>{\n\n private<\/span> final<\/span> Object[] elements;\n private<\/span> int<\/span> headIndex;\n private<\/span> int<\/span> tailIndex;\n private<\/span> int<\/span> numberOfElements;\n\n public<\/span> BoundedArrayDeque<\/span>(int<\/span> capacity)<\/span> <\/span>{\n if<\/span> (capacity < 1<\/span>) {\n throw<\/span> new<\/span> IllegalArgumentException(\"Capacity must be 1 or higher\"<\/span>);\n }\n\n elements = new<\/span> Object[capacity];\n }\n\n