ADT Stack

Aus Informatik
Wechseln zu: Navigation, Suche

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.

Ein Stapel (Stack)


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.
Arbeitsweise eines Stacks

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

Die Klasse TStack wurde von der Klasse TListe abgeleitet


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).
Sollte der Stack nicht leer sein, wird das neue Element vor das oberste Element eingefügt (es wird der Nachfolger vom neuen Element).
Schließlich wird das neue Element als das oberste Element definiert.

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.

Ist der Stack nicht leer, befindet sich mindestens ein Element im Stack. Folglich ist der Wert der Zählvariable „Count“ mindestens 1.

Nun wird geprüft, ob sich noch mehr Elemente im Stack befinden. Dazu läuft der Zeiger (FTop) von der Spitze des Stacks bis zum Ursprung (von links nach rechts). Solange der Wert der Laufvariablen nicht mit dem der Variable FRoot übereinstimmt, wandert sie um eins nach rechts und erhöht die Zählvariable „Count“ um 1. Ist der Zeiger am Ende angelangt, wird der Wert von „Count“ als Ergebnis zurückgegeben.

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

Der Quelltext der Stack Unit ist hier ausführlich kommentiert.


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

UML-Diagramm23.jpg

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

Abgerufen von „http://info-wsf.de/index.php?title=ADT_Stack&oldid=8051“