| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:adt:queue:start [11.10.2021 18:43] – [Struktur einer generischen Schlange] Mareike Nutz | faecher:informatik:oberstufe:adt:queue:start [23.04.2024 10:05] (aktuell) – [Struktur einer generischen Schlange] Frank Schiebel |
|---|
| Objekte vom Typ ''Node'' (deutsch: Knoten) speichern jeweils einen Verweis auf den nächsten Knoten (''nextNode'') sowie einen Verweis auf ein beliebiges Inhaltsobjekt (''content''), z.B. vom Typ Person. Damit übernehmen die Knoten die Verwaltung der Struktur der Schlange, die eigentlichen Inhalte sind jedoch in die Inhaltsobjekte ausgelagert. | Objekte vom Typ ''Node'' (deutsch: Knoten) speichern jeweils einen Verweis auf den nächsten Knoten (''nextNode'') sowie einen Verweis auf ein beliebiges Inhaltsobjekt (''content''), z.B. vom Typ Person. Damit übernehmen die Knoten die Verwaltung der Struktur der Schlange, die eigentlichen Inhalte sind jedoch in die Inhaltsobjekte ausgelagert. |
| |
| Jede Klasse hat also ihren eigenen Verantwortungsbereich: De Klasse ''Person'' verwaltet alle Daten zur Person, die Klasse ''Node'' stellt Attribute und Methoden zur Verfügung, die für die Organisation der FIFO-Daten-Struktur nötig sind. | Jede Klasse hat also ihren eigenen Verantwortungsbereich: Die Klasse ''Person'' verwaltet alle Daten zur Person, die Klasse ''Node'' stellt Attribute und Methoden zur Verfügung, die für die Organisation der FIFO-Daten-Struktur nötig sind. |
| |
| Da die Knoten lediglich Verweise auf Inhaltsobjekte verwalten, können Objekte eines beliebigen Typs in der Schlangenstruktur verwaltet werden. Man spricht von einer **generischen Schlange**. | Da die Knoten lediglich Verweise auf Inhaltsobjekte verwalten, können Objekte eines beliebigen Typs in der Schlangenstruktur verwaltet werden. Man spricht von einer **generischen Schlange**. |
| Damit das sinnvoll möglich ist, muss die ''queue''-Klasse Methoden zum Einfügen, Löschen und Auslesen von Elementen anbieten. | Damit das sinnvoll möglich ist, muss die ''queue''-Klasse Methoden zum Einfügen, Löschen und Auslesen von Elementen anbieten. |
| |
| ''queue'' speichert sie eine Referenz auf den ersten Knoten der Schlange (''head'') als Attribut, damit man auf das erste Schlangenelement zugreifen kann, außerdem und auch eine Referenz auf den letzten Knoten (''tail''), damit man am Ende der Schlange neue Elemente einfügen kann. | ''queue'' speichert sich eine Referenz auf den ersten Knoten der Schlange (''head'') als Attribut, damit man auf das erste Schlangenelement zugreifen kann, außerdem und auch eine Referenz auf den letzten Knoten (''tail''), damit man am Ende der Schlange neue Elemente einfügen kann. |
| |
| Zur Funktionalität der Datenstruktur **Schlange** (**Queue**) gehören, neben den Methoden Einfügen (''enqueue'') und Entfernen (''dequeue'') die Ausgabe des ersten Elements (''front'') sowie die Abfrage, ob die Warteschlange leer ist (''isEmpty''). | Zur Funktionalität der Datenstruktur **Schlange** (**Queue**) gehören, neben den Methoden Einfügen (''enqueue'') und Entfernen (''dequeue'') die Ausgabe des ersten Elements (''front'') sowie die Abfrage, ob die Warteschlange leer ist (''isEmpty''). |
| |
| * [[.enqueue:start|Einfügen eines Elements am Ende (enqueue)]] | * [[.enqueue:start|Einfügen eines Elements am Ende (enqueue)]] |
| * [[.dequeue:start|Entfernen eines Elkements (dequeue)]] | * [[.dequeue:start|Entfernen eines Elements (dequeue)]] |
| * [[.front:start|Erstes Element lesen (front)]] | |
| | |
| | ==== Alternative Implementation ==== |
| | |
| | |
| | |
| | * [[.array_queue:start|Alternative Implementation einer Schlange als Array]] |