ADT Schlange = Queue
Eine Datenstruktur zur Zwischenablage von Datenwerten,
bei der die Werte in der gleichen Reihenfolge entnommen werden,
in der sie eingetragen wurden (First-In-First-Out, FIFO),
nennen wir eine (Warte-)Schlange oder Queue.
Eine Schlange hat einen Schwanz, an den wir mittels der
Operation enqueue Datenelemente anhängen,
und einen Kopf, wo wir das aktuell erste Element first(q)
mit der Operation dequeue abholen können;
übrig bleibt rest(q).
Die algebraische Modellierung ist etwas mühsam
und benötigt die Hilfsfunktionen first und rest
vor allem wegen einiger Unvollkommenheiten der üblichen
mathematischen Notation.
ADT Queues(T) IS
SORTS:
queue, T, boolean, cardinal
OPERATIONS:
newqueue: 
queue
enqueue: T 
queue queue
isempty: queue boolean
length: queue 
cardinal
dequeue: queue T queue
first: queue T
rest: queue queue
RULES:
isempty(newqueue) = true
isempty(enqueue(x, q)) = false
length(newqueue) = 0
length(enqueue(x, q)) = length(q) + 1
dequeue(q) = <first(q), rest(q)>
first(enqueue(x, q)) = IF isempty(q) THEN x ELSE first(q)
rest(enqueue(x, q)) = IF isempty(q) THEN newqueue
ELSE enqueue(x, rest(q))
END Queues.
Wir besprechen einige Realisierungen im Einzelnen;
man macht dabei leicht Fehler, weil es nicht nur den Sonderfall
der leeren Schlange zu berücksichtigen gilt,
sondern auch den Fall einer einelementigen Schlange,
bei der Kopf und Schwanz identisch sind.
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36