Warteschlangen

Multibehälter von einem Sacktyp kümmern sich nicht um die Reihenfolge ihrer Elemente, sondern nehmen eine beliebige. Im Gegensatz dazu erinnert sich eine Folge an die Reihenfolge der Eintragungen.

Arten von Folgen

Aus den bis jetzt kennengelernten Multibehältern konnten die eingetragenen Elemente in beliebiger Reihenfolge gelesen oder entfernt werden; es mußte allerdings genannt werden, welches Element erreicht werden soll. Es gibt Behälter, auf deren Daten der Zugriff nur in einer bestimmten Reihenfolge möglich ist. Wir nennen diese Listen. Naturgemäß sind alle Listen spezielle Arten von Folgen, da sie einerseits ein Element mehrfach aufnehmen können, andererseits sich die Reihenfolge der Eintragung merken.

Folgen

Die verschiedenen Arten von Listen unterscheiden sich vor allem dadurch, in welcher Reihenfolge die geschriebenen Daten gelesen und entfernt werden können. Es gibt manche, die wie eine Warteschlange am Postschalter funktionieren: Wer zuerst da war, wird zuerst bedient. Der zuerst geschriebene Wert wird dementsprechend zuerst herausgegeben. Sie heißen auch so: Warteschlangen oder FIFO-Behälter. Andere machen es umgekehrt: Nach dem LIFO-Prinzip arbeitet der Stapel oder Keller.

Ein Sortierkanal ist auch eine Liste: Er gibt das kleinste jemals gespeicherte Element zuerst heraus. Wiederum andere bieten dem Benutzer die Möglichkeit, die Ausgabereihenfolge selber zu bestimmen. In ein Telefonbuch (als Datenbehälter) können beispielsweise zuerst Einträge mit Namen und Telefonnummer eingegeben werden. Bei der Ausgabe gibt dann der Benutzer den Namen an und bekommt die entsprechende Telefonnummer. Solche Multibehälter heißen Assoziativspeicher, da sie einen Namen mit der Telefonnummer assoziieren.

Diese Arten von Folgen werden wir jetzt ausführlicher untersuchen und dabei neue Programmiertechniken kennenlernen.

Warteschlangen

Einer der einfachsten Listen ist der FIFO-Datenbehälter, die Warteschlange. Ihre Elemente können in derselben Reihenfolge gelesen und entfernt werden, wie sie hineingeschrieben worden sind. Ein Zugriff auf andere Elemente ist nicht möglich, da immer nur das älteste Element erreichbar ist. Die Schnittstelle der Warteschlange ist:

generic
	type TElement is private;
package GWarteschlange is -- aus der Datei GuWschl.ads
	type TWarteschlange is limited private; -- ensures Leer
	procedure Entleeren (Schlange: out TWarteschlange); -- ensures Leer
	procedure Eintragen (Schlange: in out TWarteschlange; Element: in TElement); 
	-- requires not Voll; ensures not Leer; raises:
	ESchlange_voll: exception;
	function Lesen (Schlange: TWarteschlange) return TElement; -- requires not Leer; raises:
	ESchlange_leer: exception;
	procedure Entfernen (Schlange: in out TWarteschlange); 
	-- requires not Leer; ensures not Voll; raises ESchlange_leer;
	function Leer (Schlange: TWarteschlange) return Boolean;
	function Voll (Schlange: TWarteschlange) return Boolean;
	procedure Kopieren (Ziel: out TWarteschlange; Quelle: in TWarteschlange);
		-- ensures Ziel = Quelle; raises Constraint_Error, wenn Ziel zu klein
	function "=" (Links, Rechts: TWarteschlange) return Boolean;
	procedure Speichern (Schlange: in TWarteschlange; Dateiname: in String); -- Persistenzoperationen
	procedure Laden (Schlange: out TWarteschlange; Dateiname: in String); -- raises:
	EDatei: exception; -- der Inhalt der Datei paßt nicht in Schlange, oder keine Datei mit Dateiname
private ... -- implementierungsabhängig
end GWarteschlange;

In dieser Moduldefinition haben wir Zusicherungen in Form von Kommentaren Gebrauch gemacht. Die Zusicherung in der Typdefinition stellt sicher, daß eine (dynamisch oder statisch) angelegte Warteschlange leer ist. Ist dies nicht garantiert, wie z.B. bei Mengen oder Säcken, ist es notwendig, die Operation Entleeren als Konstruktor aufzurufen, um das Objekt in einen definierten Zustand zu bringen.

Anwendung

Sie können gemerkt haben, daß die Warteschlange keinen Iterator wie z.B. Alles_anzeigen hat, der alle in der Warteschlange enthaltenen Zeichen anzeigen würde. Es ist eine Eigenschaft von Warteschlangen, daß immer nur der älteste Eintrag erreichbar ist.

Ein Beispiel für die Verwendung dieser Paketschablone ist die Computerisierung des Wartezimmers in einer Arztpraxis (allerdings zunächst einmal ohne die Möglichkeit, einen neuen Patienten aufzunehmen):

with GWarteschlange, Meldungsfenster, GAufz_EA, GMenue; -- mit zwei Menüpunkten
procedure Arztpraxis is
	type TPatient is (Mueller, Mayer, ... ); -- alle Patienten werden aufgelistet
	package MPatient_EA is new GAufz_EA (T => TPatient);
	package MPat_Schl is new GWarteschlange (TElement => TPatient);
	Liste: MPat_Schl.TWarteschlange; -- Warteliste für die Patienten
	procedure Patient_kommt is -- Rückrufprozedur für den ersten Menüpunkt
		Patient: TPatient;
	begin
		MPatient_EA.Eingabemaske (Ergebnis => Patient); -- raises EDatenfehler; -- Name eingetippt
		MPat_Schl.Eintragen (Schlange => Liste, Element => Patient); -- raises ESchlange_voll;
	exception
		when MPatient_EA.EDatenfehler => Meldungsfenster ("Patient unbekannt", "Tippfehler");
		when MPat_Schl.ESchlange_voll => Meldungsfenster ("Patient muss draussen warten",
			"Wartezimmer voll");
	end Patient_kommt;
	procedure Naechste_bitte is -- Rückrufprozedur für den zweiten Menüpunkt
		Patient: TPatient;
	begin
		Patient := MPat_Schl.Lesen (Schlange => Liste); -- raises ESchlange_leer;
		Meldungsfenster (Meldung => TPatient'Image (Patient), Titel => "Patient ausrufen");
		MPat_Schl.Entfernen (Schlange => Liste); -- Patient wird aus der Liste ausgetragen
	exception
		when MPat_Schl.ESchlange_leer => Meldungsfenster (Meldung => "Feierabend"); -- kein Patient wartet
	end Naechste_bitte;

Eine mögliche Vorgehensweise bei der Entwicklung eines solchen Programms ist - neben der objektorientierten - die "von oben nach unten Strategie". Hier fangen Sie Ihre Überlegungen mit der Bedieneroberfläche an:

• Planen Sie die Oberfläche Ihres Programms: Welche Menüpunkte, Masken, Meldungen, Fenster sollen erscheinen? Denken Sie daran, der Bediener soll die Internas Ihres Programms nicht kennen (Objekte, Prozeduren, auch keine Bezeichner): Versetzen Sie sich in seine Denkweise hinein. Im obigen Programm sind das 2 Menüpunkte und die Eingabemaske für die Patienten.
• Planen Sie die diesen Oberflächenobjekten entsprechenden Programmelemente: Subroutinen für die Menüpunkte, Datenobjekte für die Masken, usw. Im obigen Programm entsprechen diesen die 2 Subroutinen für die Menüpunkte und der Datentyp TPatient für die Eingabemaske.
• Generieren und importieren Sie die nötigen Bibliothekseinheiten. Im obigen Programm werden Meldungsfenster, GAufz_EA und GMenue gebraucht.
• Untersuchen Sie, welcher Informationsfluß zwischen Ihren Subroutinen stattfindet. Woran soll sich Ihr Programm zwischen den Ereignissen (Menüauswahlen) erinnern? Das Gedächtnis des Programms implementieren Sie mit Hilfe von globalen Objekten. Im obigen Programm ist es das Objekt Liste.
• Alle andere Objekte sollen lokal in Ihren Rückrufprozeduren sein.
• Die Art und Weise, wie aus dem Gedächtnis die Daten abgerufen werden sollen, entscheidet, von welchem Typ diese Datenobjekte sein sollen. Im obigen Programm handelt es sich um eine Warteschlange.
• Sie müssen nun ein Modul finden, das den nötigen Datentyp (eventuell Ihr globales Datenobjekt) implementiert. Nur wenn kein Modul auffindbar ist, sollten Sie selber programmieren.

Nach diesen Vorbereitungen müssen Sie nur die eingesammelten Programmbausteine zusammenstecken. Achten Sie dabei darauf, daß die einzelnen Namen (von Objekten, Datentypen, Operationen) aus den richtigen Modulen geholt werden (am besten ohne use) und die Operationen mit den richtigen Parametern versehen werden (Anzahl, Datentyp, Modus).

Übung: Entwerfen und implementieren Sie auf diese Weise das menügesteuerte Programm Nikolaus, das wartenden Kindern Geschenke aus seinem Sack verteilt. Die Namen der Kinder und die Geschenke listen Sie im Programm als Werte eines Aufzählungstyps auf. Der Bediener des Programms soll wählen, wann der Nikolaus ein Geschenk einkauft (und es in sein Sack legt), wann ein Kind bei ihm ankommt (und sich in die Warteschlange einreiht) und wann er das am längsten wartende Kind beschenkt. Das Geschenk soll über eine Auswahlliste ausgesucht werden; wenn der Nikolaus es nicht (mehr) in seinem Sack hat, muß er es über eine geeignete Meldung ablehnen.

Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de

Leitseite des Autors