Warteschlange

Eine Warteschlange ist eine Liste, bei der Elemente am Ende der Liste hinzugefügt und am Anfang entnommen werden können. Man spricht vom FIFO-Prinzip: First in - first out!

Denken Sie an eine Supermarktkasse: Kunden stellen sich hinten an der Schlange an und gehen nach dem Kassiervorgang vorne wieder heraus.

Implementierung als einfach verkettete Liste - erster Ansatz

Eine einfach verkettete Liste ist ein Ersatz für das Array um dessen Nachteile (Größenbeschränkung, Speicherplatzverschwendung und Aufwand beim Entnehmen) bei der Umsetzung der Warteschlange zu vermeiden.

Die Idee besteht darin, die Inhaltsobjekte hintereinanderzuhängen, indem jedes Inhaltselement ein Attribut nachfolger bekommt, das auf das jeweils nächste zeigt. Im Warteschlangen-Objekt wird dann nur noch die Referenz auf das erste Inhaltsobjekt gespeichert:

Beim letzten Inhaltsobjekt der Liste ist einfach nachfolger == null gesetzt.

Als Java-Programm:

Klassendiagramm

Es ergibt sich das rechts dargestellte Klassendiagramm.

Die einfach verkettete Liste ist eine rekursive Datenstruktur. Dabei weist rekursiv (lat. recurrere „zurücklaufen“) darauf hin, dass ein Kunde-Objekt wiederum ein Kunde-Objekt als Nachfolger hat. Zwischen den Klassen Warteschlange und Kunde bestehen zwei Aggregationsbeziehungen.

Aufgabe 1

Implementieren Sie die Methode getAnzahl(), die die Anzahl der Kunden in der Warteschlange ausgibt.

Probleme des einfachen Ansatzes:

Problem 1: Vermischung von Struktur und Daten
Bei dieser Implementierung der Warteschlange müssen wir die Klasse Kunde anpassen, um die Listenfunktionalität umzusetzen: Sie wird um ein zusätzliches Attribut nachfolger erweitert und bekommt unweigerlich auch Methoden zur Verwaltung der Listenstruktur (getAnzahlRekursiv, …). Stellen Sie sich vor, Sie programmieren ein Spiel und benötigen eine Liste zur Verwaltung der Spieler, eine zur Verwaltung der Gegner, eine zur Verwaltung der Hindernisse usw. Dies führt dazu, dass Sie die Spieler-, Gegner- und Hindernis-Klasse jeweils um das Attribut nachfolger und die Methoden zur Verwaltung der Listenstruktur erweitern müssen: IMMER WIEDER DERSELBE PROGRAMMCODE!

Der Kern des Problems liegt darin, dass der Code zur Modellierung der Daten (Klasse Kunde) und der Code zum Verwalten der Listenstruktur vermischt sind.

Problem 2: Performance beim Zugriff aufs n-te Element
Will man auf das n-te Element einer verketteten Liste zugreifen, so muss sich das Programm - beginnend beim ersten Element - n-mal "nach vorne hangeln". Das kostet viel Zeit, denn im Mittel sind n/2 Schritte nötig. Da man bei einer Warteschlange nicht aufs n-te Element zugreifen muss, ist eine verkettete Liste dafür aber insgesamt gut geeignet.