Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Stapel

Wir haben uns bisher auf die Strukturierung von Daten konzentriert, um Elemente nach Belieben einfügen, entfernen oder einen Zugriff auf sie ermöglichen zu können. In der Realität erweist es sich, daß es für viele Anwendungen ausreichend ist, verschiedene (recht erhebliche) Einschränkungen zu betrachten. Diese Einschränkungen beziehen sich auf den Zugriff auf die Datenstruktur. Solche Einschränkungen sind in zweierlei Hinsicht günstig: Erstens können sie das Programm, welches die Datenstruktur benutzt, von der Notwendigkeit befreien, sich mit ihren Details zu beschäftigen (zum Beispiel die Übersicht über die Verkettungen zu oder die Indizes von Elementen zu bewahren); zweitens ermöglichen sie einfachere und flexiblere Implementationen, da weniger Operationen unterstützt werden müssen.

Die wichtigste Datenstruktur mit beschränktem Zugriff ist der Stapel. Nur zwei Grundoperationen treten auf: Man kann ein Element auf dem Stapel ablegen (push) (d.h., man kann es am Anfang einfügen), und man kann ein Element entnehmen (pop) (d.h. vom Anfang entfernen). Ein Stapel funktioniert in gewissem Sinne ähnlich wie das Schubfach »Eingänge« eines vielbeschäftigten Beamten: Die Arbeit stapelt sich zu einem Stoß, und immer, wenn der Beamte Zeit findet, eine Arbeit zu erledigen, nimmt er sie von der Spitze des Stapels. Dies kann bedeuten, daß manches längere Zeit am Boden des Stapels liegenbleibt, doch wird es einem guten Beamten vermutlich gelingen, den Stapel hin und wieder ganz abzuarbeiten. Es zeigt sich, daß ein Programm manchmal in natürlicher Weise in dieser Form organisiert ist, indem manche Aufgaben aufgeschoben werden, während andere erledigt werden, und daß folglich der Stapel die grundlegende Datenstruktur für viele Algorithmen darstellt.

Wir werden in den nachfolgenden Kapiteln sehr viele Anwendungen von Stapeln kennenlernen. Als ein einführendes Beispiel wollen wir uns ansehen, wie Stapel bei der Auswertung arithmetischer Ausdrücke Verwendung finden. Es wird angenommen, daß der Wert eines einfachen arithmetischen Ausdrucks bestimmt werden soll, in dem Multiplikationen und Additionen von ganzen Zahlen vorkommen, wie etwa

5*(((9+8)*(4*6))+7).

Ein Stapel ist der ideale Mechanismus für die Speicherung von Zwischenergebnissen einer solchen Rechnung. Das obige Beispiel könnte mit den folgenden Aufrufen berechnet werden:

push(5);
push(9);
push(8);
push(pop+pop);
push(4);
push(6);
push(pop*pop);
push(pop*pop);
push(7);
push(pop+pop);
push(pop*pop);
writeln(pop);

Die Reihenfolge, in der die Operationen ausgeführt werden, wird durch die Klammern in dem Ausdruck und durch die Vereinbarung, daß wir von links nach rechts vorgehen, bestimmt. Auch andere Vereinbarungen sind möglich; im obigen Beispiel könnte etwa 4*6 vor 9+8 berechnet werden.

Manche Rechner und manche Sprachen für Berechnungen bauen ihre Berechnungsmethode ausdrücklich auf derartigen Stapel-Operationen auf: Für jede Operation werden die Parameter aus dem Stapel entnommen, und ihre Ergebnisse werden wieder im Stapel abgelegt. Wie wir in Kapitel 5 sehen werden, entstehen Stapel häufig auf implizite Weise, auch wenn sie nicht explizit verwendet werden.

Die grundlegenden Stapel-Operationen lassen sich unter Verwendung verketteter Listen leicht implementieren, etwa wie in der folgenden Implementierung:

    type link=^node;
         node= record key: integer; next: link end;
    var head,z: link;
    procedure stackinit;
      begin
      new(head); new(z);
      head^.next:=z; z^.next:=z
      end;
    procedure push(v: integer);
      var t: link;
      begin 
      new(t); 
      t^.key:=v; t^.next:=head^.next; 
      head^.next:=t 
      end;
    function pop: integer;
      var t: link;
      begin 
      t:=head^.next; 
      pop:=t^.key; 
      head^.next:=t^.next; 
      dispose(t) 
      end;
    function stackempty: boolean;
      begin stackempty:=(head^.next=z) end;

(Diese Implementation beinhaltet auch Code zur Initialisierung eines Stapels und zur Ausführung eines Tests, ob er leer ist.) In einer Anwendung, in der nur ein Stapel verwendet wird, können wir annehmen, daß die globale Variable head die Verkettung zum Stapel ist; anderenfalls können die Implementationen so modifiziert werden, daß ebenfalls eine Verkettung der Stapel hergestellt wird.

Die Reihenfolge der Berechnung im obigen Beispiel eines arithmetischen Ausdrucks erfordert, daß die Operanden vor dem Operator erscheinen, damit sie sich im Stapel befinden, wenn der Operator auftritt. Jeder arithmetische Ausdruck kann in dieser Weise umgeschrieben werden; das obige Beispiel entspricht dem Ausdruck

598+46**7+*.

Dies wird als umgekehrte polnische Notation (da sie von einem polnischen Logiker eingeführt wurde) oder Postfix-Notation bezeichnet. Der herkömmliche Weg der Schreibweise arithmetischer Ausdrücke wird Infix-Notation genannt. Eine interessante Eigenschaft der Postfix-Notation besteht darin, daß keine Klammern erforderlich sind; bei der Infix-Notation werden sie benötigt, um beispielsweise 5*(((9+8)*(4*6))+7) von ((5*9)+8)*((4*6)+7) zu unterscheiden. Das folgende Programm wandelt einen zulässigen, vollständig mit Klammern versehenen Infix-Ausdruck in einen Postfix-Ausduck um:

   
    stackinit; 
    repeat
      repeat read(c) until c<>' ';
      if c =')' then write(chr(pop));
      if c ='+' then push(ord(c));
      if c ='*' then push(ord(c));
      while (c>='0') and (c<='9') do
        begin write(c); read(c) end;
      if c<>'(' then write (' ');
    until eoln;

Die Argument werden einfach durchgereicht, da sie im Postfix-Ausdruck in der gleichen Reihenfolge erscheinen wie im Infix-Ausdruck. Ferner besagt jede rechte Klammer, daß beide Parameter für den letzten Operator ausgegeben worden sind, so daß der Operator selbst aus dem Stapel geholt und ausgegeben werden kann. (Dieses Programm führt keine Prüfung auf Fehler bei der Eingabe durch und erfordert Leerzeichen zwischen Operatoren, Klammern und Operanden.)

Der Hauptgrund für die Verwendung der Postfix-Notation besteht darin, daß die Berechnung, wie in dem folgenden Programm, in einer sehr einfachen Weise mit einem Stapel ausgeführt werden kann:

    stackinit; 
    repeat
      x:=0; 
      repeat read(c) until c<>' ';
      if c ='*' then x:=pop*pop;
      if c ='+' then x:=pop+pop;
      while (c>='0') and (c<='9') do
        begin x:=10*x+(ord(c)-ord('0')); read(c) end;
      push(x); 
    until eoln;
    writeln(pop);

Dieses Programm liest jeden beliebigen Postfix-Ausdruck, in dem Multiplikationen und Additionen von ganzen Zahlen auftreten, und gibt dann den Wert des Ausdrucks aus. Leerzeichen werden ignoriert, und die while-Schleife wandelt ganze Zahlen vom Zeichenformat in das Zahlenformat für die Berechnung um. Ansonsten ist die Arbeitsweise des Programms sehr einfach. Ganze Zahlen (Operanden) werden im Stapel abgelegt, und Multiplikation und Addition ersetzen die beiden obersten Elemente des Stapels durch das Ergebnis der Operation.

Wenn die maximale Größe eines Stapels im voraus angegeben werden kann, kann es zweckmäßig sein, wie in der folgenden Implementation anstelle einer verketteten Liste eine Darstellung in Form eines Feldes zu benutzen:

    const maxP=100;
    var stack: array[0..maxP] of integer; 
        p: integer;
    procedure push(v: integer);
      begin stack[p]:=v; p:=p+1 end;
    function pop: integer;
      begin p:=p-1; pop:=stack[p] end;
    procedure stackinit;
      begin p:=0 end;
    function stackempty: boolean;
      begin stackempty:=(p<=0) end;

Die Variable p ist eine globale Variable, die die Position des Stapelanfangs registriert. Dies ist eine sehr einfache Implementation, durch die die Verwendung von zusätzlichem Platz für Verkettungen vermieden wird; der Preis dafür ist die eventuelle Platzverschwendung durch die Bereitstellung von Raum für den Stapel maximaler Größe.

Abbildung 3.7 zeigt, wie sich ein exemplarischer Stapel in Folge der Reihe von push- und pop-Operationen verändert, die sich aus der Eingabefolge

A * S A * M * P * L * E S * T * * * A * C K * *

ergeben.

Das Auftreten eines Buchstaben in dieser Liste bedeutet »Ablegen« (des Buchstabens) (push); das Sternchen bedeutet »Entnehmen« (pop).

Abbildung 3.7
Abbildung 3.7 Dynamische Merkmale eines Stapels.

Dabei ist es typisch, daß für eine große Zahl von Operationen nur ein kleiner Stapel benötigt wird. Wenn man sicher ist, daß dies der Fall ist, so kann eine Felddarstellung verwendet werden. Andernfalls kann eine verkettete Liste dem Stapel die Möglichkeit geben, sich auf elegante Weise zu vergrößern und zu verkleinern, besonders dann, wenn es sich um eine von vielen solcher Datenstrukturen handelt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]