Stack für beliebige Daten

[d3g]

Stacks für beliebige Daten konstruieren

1. Wozu?
Stacks sind sehr praktische Datenstrukturen, mit ihnen lassen sich viele Datenspeicherungs-Probleme relativ einfach lösen. Man braucht sie immer dann, wenn das zuletzt gespeicherte Element wieder als erstes gebraucht wird, z.B. bei Backtrackings in der Rekursion.

2. Das Prinzip
Das Prinzip des Stacks, den ich hier konstruieren werde, ist das einer doppelt verketteten Liste. Das bedeutet, dass von einem Ausgangspunkt aus ein Pointer auf das erste Element einer Kette zeigt. Dieses Element zeigt wiederum auf das nächste Element der Kette. Das geht so weiter bis zu letzten Element, dieses zeigt dann auf nil, also praktisch nirgedwohin.
Gleich verhält es sich auch andersherum: Das letzte Element zeigt auf das vorletze, welches auf das vorvorletze zeigt, und so weiter bis zum ersten Element, das auf nil (also nirgendwohin) zeigt.

Code:

.______________          _________        _________
|    TStack    |        |  TData  |      |  TData  |
|______________|        |_________|      |_________|     _____
|              |        |         |      |         |    |     |
|  Push()      |  /---->|  Succ -------->|  Succ ------>| nil |
|  Pop()       |  |     |  Pred   |<------- Pred   |    |_____|
|              |  |     |____|____|      |_________|
|  FFirstItem ----/          |        _____
|              |             |       |     |
|______________|             \------>| nil |
                                     |_____|

Das Hinzufügen und entfernen von Elementen in einer solchen Liste ist einfach. Beim Hinzufügen wid schlicht und einfach der Pointer des letzen Elements auf das neue gebogen und im neuen Element der Successor auf nil und der Predecessor auf das alte letzte Element gesetzt. Beim Löschen setzt man einfach den Pointer des vorletzten Elements auf nil. Ähnlich einfach wäre das Hinzufügen und Entfernen von Elementen an beliebiger Position in der Kette, das ist für einen Stack aber nicht nötig (dieses Beispiel kann so aber einfach zu einem Queue oder zu einer vollwertigen Liste ausgebaut werden).

Die Pointer vom letzten Element zurück sind natürlich nicht nötig, aber da man beim Löschen das vorletzte Element benötigt und es sehr einfach ist, das letzte Element zu finden, kann man mit der Linie zurürck auch wieder einfach das vorletzte finden. Man könnte auch argumentieren, diese ganze Konstuktion sei nicht nötig, man könne doch genauso gut Arrays benutzen. Arrays haben nur ein Problem: sie sind sehr undynamisch. Statische Arrays sowieso, weil diese an eine maximale Anzahl Elemente gebunden sind, für die der Speicher schon gleich zu Anfang reserviert werden muss und nicht einfach so viel Speicher verwendet wird wie nötig, sondern mehr oder (wenn die Elemente aufgebraucht sind) genausoviel. Dynamische Arrays sind da besser, sind aber erst ab Delphi 4 implementiert und außerdem sehr langsam. Eine verkettete Liste ist sehr schnell, da nur mit Pointern gearbeitet wird, was vom Prozessor (im Gegensatz zu dynamischen Arrays) nativ angeboten wird.

3. Push() und Pop()
Wie oben in der Skizze dargestellt, möchte ich für die Verwaltung der Liste und als Ausgangspunkt eine Klasse benutzen. Diese braucht einen Konstruktor, zwei Methoden zum Hinzufügen von Elementen (Push()) und zum Löschen derselben (Pop()). Außerdem wird ein Pointer als Ausgangspunkt für die Liste gebraucht. Außerdem braucht man selbstverständlich eine Datenstruktur für die zu speichernden Daten, ein Record mit den Daten und den Pointern für das nächste Element (Succ) und das vorgehende (Pred). Der Einfachheit halber sind im Beispiel die Daten ein einfacher Integer, man kann natürlich viel komplexere Sachen benutzen.

Delphi-Quellcode:

type
  PData = ^TData;
  TData = record
    Data: Integer;
    Pred, Succ: PData;
  end;

  TStack = class(TObject)
    public
      constructor Create();
      procedure Push(AItem: TData);
      function Pop(): PData;
    private
      FFirstItem: PData;
  end;

Um den Konstruktor der Klasse braucht man sich kaum zu kümmern, man mus nur sicherstellen, dass FFirstItem auf nil gestellt ist.

Delphi-Quellcode:

constructor TStack.Create();
begin
  inherited;
  FFirstItem := nil;
end;

Jetzt komme ich zum interessanteren Teil: Den Funktionen Push() und Pop(). Diese gestalten sich jedoch recht einfach, denn das letzte Element erreicht man mit einer einfachen while-Schleife. In diesem Element setzt man die Pointer so wie man es braucht und fertig. Fast - denn eine kleine Sonderbehandlung ist jeweils für das erste Element notwendig, da dessen Vorgänger ja der Ausgangspunkt und kein weiteres Element ist.

Delphi-Quellcode:

procedure TStack.Push(AItem: TData);
var
  LastItem: PData;
begin
  if (FFirstItem <> nil) then 
  begin
    LastItem := FFirstItem;
    while (LastItem^.Succ <> nil) do
      LastItem := LastItem^.Succ;
    LastItem^.Succ := @AItem;
    AItem.Succ := nil;
    AItem.Pred := LastItem;
  end else 
  begin
    FFirstItem := @AItem;
    AItem.Succ := nil;
    AItem.Pred := nil;
  end;
end;

function TStack.Pop(): PData;
var
  LastItem: PData;
begin
  Result := nil;
  if (FFirstItem <> nil) then 
  begin
    LastItem := FFirstItem;
    while (LastItem^.Succ <> nil) do
      LastItem := LastItem^.Succ;
    Result := LastItem;
    if (LastItem^.Pred <> nil) then
      LastItem^.Pred^.Succ := nil
    else
      FFirstItem := nil;
  end;
end;

4. Das Ende
Das ist alles - zum Schluss noch ein Anwendungsbeispiel:

Delphi-Quellcode:

program test;
uses
  stack;

var
  Data: TData;
  Stk: TStack;

begin
  Data.Data := 23 * 5 * 42;
  Stk := TStack.Create();
  try
    Stk.Push(Data);
    if (Stk.Pop()^.Data = Data.Data) then
      WriteLn('Success!')
    else
      WriteLn('Failure!');
  finally
    Stk.Free;
  end;
end.

Noch anzumerken wäre, dass man selbstverständlich auch Klassen statt Records als Datenstrukturen nehmen kann, allerdings wäre es dann sinnvoll, vor dem wortwörtlichen Unlinking eines Elements beim Löschen die Mehode Free() aufzurufen und einen Destruktor einzubauen, der alle noch übrigbleibenden Elemente freigibt.

Viel Spaß noch ,
d3g

[edit=flomei]Wir "räumen auf", daher Titel geändert... Mfg, flomei[/edit]