ADT Stack
Inhaltsverzeichnis
Definition
Ein Stack (auch Stapel oder Keller genannt) ist ein Stapelspeicher. Das heißt eine Folge von Elementen wird so organisiert, dass ein neues Element immer nur oben auf die Spitze des Stapels abgelegt bzw. immer nur das oberste Element des Stapels entfernt werden kann („Last-In-First-Out“ LIFO-Verfahren; deutsch zuletzt hinein – zuerst heraus). Es ist also nicht möglich, ein Element in der Mitte des Stapels anzusehen bzw. zu entfernen oder ein Element in der Mitte des Stacks einzufügen.
Funktionsweise
Anschaulich kann man einen Stack mit einem Stapel von Schüsseln vergleichen. Man kann immer nur eine neue Schüssel oben auf den Stapel legen oder eine von oben herunternehmen. Ein Hinzufügen oder Entfernen einer Schüssel in der Mitte des Stapels ist nicht möglich.
Der Stack gibt also die Informationen in entgegengesetzter Reihenfolge zur Aufnahme wieder zurück.
Die Operationen die hierzu verwendet werden sind:
Methoden
Methode | Beschreibung |
Pop() | Entfernt das oberste Element vom Stapel |
Push(Element) | Legt ein neues Element oben auf den Stapel |
TopOfStack : Element | Gibt das oberste Element des Stapels zurück |
Die folgende Grafik soll die Arbeitsweise eines Stacks veranschaulichen.
Realisierung anhand der Klasse TListe (Beispiel)
Nun soll mit Delphi eine Klasse TStack erstellt werden. Hierbei gibt es zwei Methoden, die vorgestellt werden sollen.
Bildung der Klasse TStack durch Spezialisierung
Bei der Klassenbildung durch Spezialisierung entsteht durch Vererbung eine speziellere Unterklasse (TStack) aus einer schon vorhandenen Oberklasse (TListe). Das Spezielle an der neuen Unterklasse ist, dass sie zusätzlich zu den Methoden der Oberklasse neue Methoden besitzt.
UML-Diagramm
Typdeklaration
type TStack = class(TListe)
Die Klasse TStack ist durch die Vererbung der Klasse TListe untergeordnet und besitzt alle Attribute und Methoden der Klasse TListe. Das Attribut FAktuell der Klasse TListe wird in der Klasse TStack immer als Zeiger auf das oberste Element des Stapels genutzt.
Methodendeklaration
Die Klasse TStack enthält Methoden, die es in der Klasse TListe nicht gibt." Jede Klassendefinition durch Vererbung ist eine Typerweiterung. Die Methoden der Oberklasse TListe bleiben daher in der Unterklasse TStack verfügbar, sodass es möglich ist, die unzulässigen Methoden weiterhin zu verwenden." (Objektorienterte Programmierung mit Delphi II; Klett , S.160)
Die unzulässigen, in der Klassendefinition fett geschriebenen Methoden müssen deshalb wirkungslos gemacht werden. Tatsächlich lautet also die Methodendeklaration:
public //Methoden constructor Create; override; procedure Append (Content: TContent); override; procedure ChangeContent (Content: TContent); override; procedure Delete; override; procedure First; override; procedure InsertBefore (Content: TContent); override; procedure InsertBehind (Content: TContent); override; procedure Last; override; procedure Next; override; procedure Pop; virtual procedure Push (Content: TContent); virtual function GetContent : TContent; override; function GetCount : integer; override; function IsEmpty : boolean; override function IsLast : boolean; override; function TopOfStack : TContent; virtual destructor Destroy; virtual;
Die folgende leere Methode Append ersetzt die gleichnamige Methode der Oberklasse TListe. Sie ist jedoch wirkungslos.
//-------- Append (public) --------------------------------------- procedure TStack.Append (Content: TContent); begin {leer} end;
Dieses Vorgehen ist jedoch bei Funktionsaufrufen wenig hilfreich da eine „leere“ Funktion standardmäßig den Wert „true“ zurückgibt. Alternativ könnte man diese Methoden so überschreiben, dass die Programmausführung beim Methodenaufruf durch
- eine geeignete Fehlermeldung in einem modalen Fenster,
- eine Endlosschleife, die die weitere Ausführung des Programms anhält
- eine Systemunterbrechung (Exeption)
unterbrochen wird.
Nähere Erläuterungen zu den benötigten Methoden
Damit unser Stack arbeiten kann, müssen wir also nur die Methoden
- Pop
- Push
- TopOfStack
programmieren.
Methode | Delphi-Quelltext | Erläuterung |
Push |
procedure TStack.Push (Content: TContent); var NewElement : TElement; begin NewElement := TElement.Create; NewElement.SetContent(Content); if FRoot = nil then begin FRoot := NewElement; end else begin NewElement.SetNext(FAktuell); end; FTop := NewElement; end; |
Bei dieser Methode wird das neue Element vor den schon vorhandenen Elementen eingefügt (Prinzip InsertBefore von TListe). Zuerst wird ein neues Element erstellt und sein Inhalt gesetzt. Dann wird geprüft, ob der Stack leer ist. Ist dies der Fall, ist das neue Element auch das erste Element des Stacks (Root-Element). |
Pop |
procedure TStack.Pop; var NewTop : TElement; begin if not IsEmpty then begin if FRoot = FAktuell then begin FreeandNil(FAktuell); FRoot := FAktuell; end else begin NewTop := FAktuell.GetNext; FreeandNil(FAktuell); FAktuell := NewTop; end; end; end; |
Zuerst wird geprüft, ob der Stack nicht leer ist, wenn ja wir wird getestet, ob der Stack nur ein Element beinhaltet. Sollten beide Bedingungen erfüllt sein, wird dieses Element gelöscht. FRoot und FTop sind dann unbesetzt (NIL). Wenn sich mehrere Elemente im Stack befinden, wird als erstes das neue oberste Element bestimmt (aus der Erklärung zu Pop folgt, dass es das Nachfolgerelement ist) und in der Variable „NewTop“ gespeichert. Danach wird das oberste Element gelöscht und das neue oberste Element aus „NewTop“ als oberstes Element definiert. |
GetCount |
function TStack.GetCount : integer; var Save : TElement; Count : integer; begin if not IsEmpty then begin Save := FTop; Count := 1; while not (FTop = FRoot) do begin FTop := FTop.GetNext; inc(Count); end; FTop := Save; Result := Count; end else Result := 0; end; |
Diese Funktion gibt die Anzahl der im Stack befindlichen Elemente zurück.
br/>
Zuerst wird geprüft, ob der Stack leer ist. Wenn ja, enthält er 0 Elemente, ansonsten werden die Elemente gezählt. Diesen Fall hätte man auch im Hauptprogramm behandeln können. Doch damit unsere Klasse „universell“ einsetzbar ist, behandeln wir alle Einzellfälle innerhalb der Klasse.
Da FTop in der While-Schleife als Laufvariable genutzt und deshalb innerhalb der Schleife verändert wird, muss deren ursprünglicher Wert in einer Hilfsvariablen gespeichert und am Ende mit deren Hilfe zurückgesetzt werden. |
TopOfStack |
function TStack.TopOfStack : TContent; begin Result := FAktuell.GetContent; end; |
Diese Methode ersetzt die Methode „GetContent“ der Klasse TListe. Man hätte auch „GetContent“ wie links beschrieben umschreiben können, doch da wir „TopOfStack“ als spezielle Stack-Methode eingeführt haben, ist es sinnvoll sie auch neu zu programmieren. “TopOfStack“ führt die Methode „GetContent“ der Klasse TElement für das oberste Element aus und gibt deren Wert als Ergebnis zurück. |
An dieser Stelle möchte ich auf das Programm-Beispiel TStackAusTListe hinweisen, da die ausführliche Kommentierung der Stack-Unit (mTStack2.pas) in diesem Programm sehr hilfreich sein könnte.
Das Programm-Beispiel TStackAusTdoppeltverketteteListe ist nicht kommentiert.
Programm-Beispiele
- Bei diesem Programm habe ich den ADT Stack von einem ADT lineare Liste abgeleitet: Media:ADT_Stack_aus_ADTListe_-D07.zip
Der Quelltext der Stack Unit ist hier ausführlich kommentiert.
- Bei diesem Programm habe ich den ADT Stack von einem ADT doppeltverkettete Liste abgeleitet: Media:ADT_Stack_aus_dADTListe_-D07.zip
Bildung der Klasse TStack durch Generalisierung/Abstraktion
Im Gegensatz zur Klassenbildung durch Spezialisierung wird nun keine neue Unterklasse erstellt, sondern die gemeinsamen Eigenschaften zweier Klassen in einer neuen Oberklasse zusammengeführt. Dieses Vorgehen bezeichnet man als Klassenbildung durch Generalisierung / Abstraktion.
Bei diesem Vorgehen werden Methoden die dem Benutzer einer Unterklasse zur Verfügung stehen sollen als public implementiert. Methoden, die dem Programmierer, jedoch nicht dem Benutzer, der Unterklasse zur Verfügung stehen sollen, werden hingegen als protected implementiert.
Es stellt sich also heraus, dass diese Art der Klassenbildung bei der Erstellung der Klasse TStack wesentlich geschickter und besser ist, da man auf der einen Seite den Zugriff für den Benutzer einschränken, auf der anderen Seite aber dem Entwickler alle Möglichkeiten offen lassen kann.
In der professionellen Informatik erfolgt die Klassenbildung der Klasse TStack auch über Abstraktion.
UML-Diagramm
Typdeklaration
type TStack = class(TListenstruktur)
Methodendeklaration
public //Methoden Push (Element); virtual; Pop ; virtual; TopOfStack ; virtual;
Über den Befehl inherited kann der Entwickler auf alle Methoden der Oberklasse zugreifen. Der Benutzer kann nur die öffentlichen Methoden verwenden. Der Delphi-Quelltext für unsere Klasse TStack könnte dann wie folgt aussehen:
UNIT mTStack; interface uses mTListenverwaltung, mTElement; type TStack = class(TListenverwaltung) public //Methoden procedure Push (Content: TContent); virtual; function Pop ; virtual; function TopOfStack : TContent; virtual; end; implementation //+---------------------------------------------------------------- //| TStack: Methodendefinition //+---------------------------------------------------------------- //-------- Push (public) ------------------------------------------ procedure TStack.Push (Content: TContent); begin inherited InsertBefore (Content); end; //-------- Pop (public) ------------------------------------------- function TStack.Pop; begin inherited Delete; end; //-------- Top (public) ------------------------------------------- function TStack.TopOfStack : TContent; begin Top:= inherited GetContent; end; end.
Quellen
- http://lernen.bildung.hessen.de/informatik/delphi/listen
- http://www.wikipedia.de
- http://www.u-helmich.de/inf/BlueJ/kurs121/seite15/seite15-stack.html
- Objektorienterte Programmierung mit Delphi II; Klett