In der Warteschlange kann nur auf das zuerst, in einem Stapel oder Keller auf das zuletzt eingetragene Element zugegriffen werden. Um ein bestimmtes Element zu erreichen, müssen alle Elemente, die nach diesem eingetragen wurden, entfernt werden.
Die Schnittstelle des Stapels sieht der der Warteschlange praktisch gleich aus; hinter den einzelnen Operationen verbergen sich aber andere Funktionalitäten:
generic type TElement is private; package GStapel is type TStapel is limited private; -- ensures Leer procedure Entleeren (Stapel: out TStapel); -- ensures Leer -- ein neues Element wird oben auf den Stapel gelegt: procedure Eintragen (Stapel: in out TStapel; Element: in TElement); -- requires not Voll; ensures not Leer and Lesen = Element; raises: EStapel_voll: exception; function Lesen (Stapel: TStapel) return TElement; -- das jüngste (oberste) Element im Stapel wird ausgegeben -- requires not Leer; ensures not Voll; raises: EStapel_leer: exception; procedure Entfernen (Stapel: in out TStapel); -- das jüngste (oberste) Element wird aus dem Stapel entfernt -- requires not Leer; ensures not Voll; raises EStapel_leer; function Leer (Stapel: TStapel) return Boolean; function Voll (Stapel: TStapel) return Boolean; ... -- Persistenzoperationen, Kopieren und Gleichheit wie üblich; kein Iterator private ... end GStapel;
Mit Hilfe der Zusicherungen der Operation Eintragen kann ausgedrückt werden, daß das nächste Lesen das gerade eingetragene (jüngste) Element liefert.
Es sei bemerkt, daß viele Stapel-Implementierungen die beiden Operationen Lesen und Entfernen in einer Operation vereinigen, etwa:
procedure Austragen (Stapel: in out TStapel; Element: out TElement);
Dies ist zwar möglich, widerspricht aber der eingeführten Philosophie der Trennung von Informatoren und Mutatoren. Die Operation Austragen liefert nämlich Information über den aktuellen Zustand des Stapels, verändert ihn aber auch gleichzeitig. Überlegungen aus dem Software Engineering sprechen sich für die klare Trennung aus.
Eine Eigenschaft von Paketschablonen der obigen Art ist, daß sie für einen beliebigen (nicht-eingeschränkten) Datentyp ausgeprägt werden können. Man kann GStapel z.B. für den Datentyp TEimer ausprägen; dann können Eimer gestapelt werden.
package MEimer_Stapel is new GStapel (TElement => MEimer.TEimer); Eimer_Stapel: MEimer_Stapel.TStapel;
Nicht alle Paketschablonen können für einen beliebigen Datentyp ausgeprägt werden. Ein Beispiel dafür ist die Paketschablone Enumeration_IO, die nur diskrete Datentypen (wie Aufzählungstypen) bedient. Welche Ausprägungstypen in Frage kommen, ist auch aus der formalen Schnittstelle des Pakets ersichtlich:
generic TElement is limited private; -- für jeden Datentyp ausprägbar
In diesem Paket wird keine Eigenschaft des Ausprägungstyps ausgenutzt, jeder Datentyp ist geeignet. Wenn Objekte vom Ausprägungstyp im Paketrumpf kopiert oder miteinander verglichen werden, ist ein limited private Datentyp nicht zulässig:
generic TElement is private; -- nur für nicht eingeschränkte Datentypen ausprägbar
Das Beispiel aus der Schnittstelle von Text_IO im LRM 14.3.10, sowie die Paketschablone GAufz_EA legt dem Ausprägungstyp weitere Einschränkungen auf:
generic type Enum is (<>); -- nur für diskrete Typen ausprägbar package Text_IO is ... -- package GAufz_EA genauso
Hier wird im Paketrumpf ausgenutzt, daß die Objekte geordnet sind, sie können z.B. mit "<" miteinander verglichen werden oder ihre Attributfunktion Succ aufgerufen werden. Daher muß der Ausprägungstyp ein Aufzählungstyp oder (wie im Kapitel 10. eingeführt) ein Ganzzahltyp sein.
Übung: Implementieren Sie ein Modul für die Umwandlung eines streng geklammerten Ausdrucks in Postfixnotation. Der geklammerte Ausdruck
(((a+b)*c)-(d/(e+f)))
wird in den Postfix-Ausdruck
ab+c*def+/-
übersetzt. Hier stehen also immer die Operanden vor dem Operator.
Der Algorithmus liest den Ausdruck Zeichen für Zeichen ein und gibt das Ergebnis Zeichen für Zeichen aus. Er arbeitet mit einem Stapel. Folgende Fälle werden müssen unterschieden werden:
Ausdruckende: Stapel soll leer sein (sonst fehlerhafter Ausdruck)
Ihr Modul soll 5 Prozeduren exportieren, die die obigen Fälle behandeln. Dank der strengen Klammerung (jeder Operator wird mit einem Klammerpaar umgeben) ist der Algorithmus einfach: jeweils wie oben beschrieben. Interessant ist jedoch die Modulstruktur.
Das Modul soll sein Gedächtnis in einem importierten ADO-Modul (also nicht im modulinternen Objekt) speichern. Ihr ADO-Stapelmodul soll diesmal mit Hilfe der ADT-Modulschablone GStapel implementiert werden. Programmieren Sie eine konsequente Ausnahmebehandlung. Entwickeln Sie einen Dialogtesttreiber, über dessen Menüpunkte der Ausdruck eingeben wird:
1. Bemerkung: Wenn die Ausdrücke - wie üblich - nicht streng geklammert sind, d.h. nicht jeder Operator hat ein entsprechendes Klammerpaar, müssen die Prioritäten der Operatoren berücksichtigt werden. Der Algorithmus wird dadurch etwas komplexer: Die Ankunft eines Operators bewirkt (wie eine schließende Klammer) die Austragung aller Operatoren höherer Priorität aus dem Stapel. Erlauben wir jedoch das Weglassen von Klammern nur bei Operatoren gleicher Priorität (etwa für a+b-c, nicht aber für a+b*c, funktioniert der Algorithmus unverändert. In diesem Fall wird der Ausdruck von links nach rechts (wie üblich) ausgewertet.
Bei diesem Algorithmus kommt der Vorteil der getrennten Operationen Lesen und Entfernen aus dem Stapel zum Vorteil: Der jüngste Operator muß ausgelesen werden, um seine Priorität zu ermitteln; wenn sie zu niedrig ist, bleibt er jedoch im Stapel.
2. Bemerkung: Ein Ausdruck in Präfixnotation enthält seine Operatoren vor den Operanden. Ein sehr ähnlicher Algorithmus erzeugt den Präfix-Ausdruck: Die Behandlung des Objekts und des Operators wird vertauscht:
So wird der obige geklammerte Ausdruck in den Präfix-Ausdruck
+ba*c-/+fed
übersetzt. Hier stehen also immer die Operanden nach dem Operator, wobei die Operanden vertauscht werden (der rechte steht vorne). Bei seiteneffektfreien Ausdrücken verursacht dies keine Probleme.
Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de
Leitseite des Autors