Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:adt:queue:array_queue:start [11.11.2021 07:04] – angelegt sbel
+++ faecher:informatik:oberstufe:adt:queue:array_queue:start [23.04.2024 10:04] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
 ====== Alternative Implementation einer Schlange als Array ======
+Da es sich bei einer Schlange um einen abstrakten Datentyp handelt, spielt es für die Funktionalität keine Rolle, wie die Elemente im Hintergrund verwaltet werden.
+{{ :faecher:informatik:oberstufe:adt:queue:array_queue:queue_array.png|}}
+Die Elemente der Queue können auch in einem Array gespeichert werden. Dabei merkt man sich mit Hilfe zweier Attribute ''first'' und ''last'', welcher Bereich des Arrays die Queue repräsentiert.
+  * Das Attribut ''first'' ist dabei sinnvollerweise inklusive gemeint, ''last'' sollte eine exklusive Grenze sein (Beispiel 1).
+  * Beim Einreihen eines neuen Elements wird dieses am Index ''last'' ins Array geschrieben und ''last'' wird um 1 erhöht (Beispiel 2).
+  * Wenn ein Index so erhöht wird, dass er die Länge des Arrays erreicht, wird er auf 0 zurückgesetzt (Beispiel 3).
+  * Um das vorderste Element der Queue zu entfernen, nimmt man den Wert am Index ''first'' und erhöht ''first'' um 1 (Beispiel 4). Es stört nicht, dass der alte Wert weiterhin im Array steht – wir greifen nie wieder lesend auf ihn zu. Irgendwann wird der Wert wieder überschrieben.
+  * Wenn nach dem Einfügen eines neuen Wertes ''first'' und ''last'' gleich sind, ist das Array //"voll"// (Beispiel 5). Damit später weiterhin Elemente eingefügt werden können, muss das Array vergrößert werden. Man erzeugt ein neues Array, das z.B. doppelt so groß ist und kopiert die alten Werte ins neue Array. Dann passt man die Indizes ''first'' und ''last'' passend an.
-Die Elemente der Queue können auch in einem Array gespeichert werden. Dabei merkt man sich mit Hilfe zweier Variablen first und last, welcher Bereich des Arrays die Queue repräsentiert. Die Variable first ist dabei sinnvollerweise inklusive gemeint, last sollte eine exklusive Grenze sein (Beispiel 1).
+Implementiere die Klasse ''ArrayQueue'' nach diesem Prinzip und führe die Tests der zugehörigen Testklasse aus. Eine entsprechende Codevorlage [[ https://codeberg.org/qg-info-unterricht/bluej-array-queue|findest du hier]].
-Beim Einreihen eines neuen Elements wird dieses am Index last ins Array geschrieben und der Index wird um 1 erhöht (Beispiel 2).
-Wenn ein Index so erhöht wird, dass er die Länge des Arrays erreicht, wird er auf 0 zurückgesetzt (Beispiel 3).
-Um das vorderste Element der Queue zu entfernen, nimmt man den Wert am Index first und erhöht first um 1 (Beispiel 4). Es stört nicht, dass der alte Wert weiterhin im Array steht – wir greifen nie wieder lesend auf ihn zu. Irgendwann wird der Wert wieder überschrieben.
-Wenn nach dem Einfügen eines neuen Wertes first und last gleich sind, ist das Array „voll“ (Beispiel 5). Damit später weiterhin Elemente eingefügt werden können, muss das Array vergrößert werden. Man erzeugt ein neues Array, das z.B. doppelt so groß ist und kopiert die alten Werte ins neue Array. Dann passt man die Indizes first und last noch an.
+**Hinweis:** In Java kann man kein Array eines generischen Typs erzeugen. Stattdessen erzeugt man ein Object-Array und führt beim Auslesen einen Cast zum generischen Typ T aus:
-Implementieren Sie die Klasse ArrayQueue nach diesem Prinzip und führen Sie die Tests der zugehörigen Testklasse aus.
-Hinweis: In Java kann man kein Array eines generischen Typs erzeugen. Stattdessen erzeugt man ein Object-Array und führt beim Auslesen einen Cast zum generischen Typ T aus:
+<code java>
 Object[] daten = new Object[10];
-…
+...
-T front = (T)daten[5];
+T myValue = (T)daten[5];
+</code>