Folge 14

Abstrakte Datentypen

14.1 Datentypen und Datenstrukturen

Eine kurze Internet-Recherche zeigt sofort, dass es keinen richtigen Konsens gibt über die Verwendung der Begriffe „Datentyp“ und „Datenstruktur“. Wertet man jedoch mehrere Internetquellen und Fachbücher systematisch aus, so kristallisiert sich ein rein statistischer Konsenz heraus. Aber Vorsicht - nicht immer hat die Mehrheit Recht.

Nach diesem statistischen Konsenz versteht man unter einem Datentypen einen elementaren physikalischen Speicherplatz für einfache Daten. In der Sprache Java gehören dann int, float, double, char, byte und boolean (ich habe bestimmt noch was vergessen) zu den Datentypen.

Ein recht einfaches Kriterium für einen Datentyp ist, dass man die Zahl der Bits angeben kann, aus denen er besteht. Eine int-Zahl besteht zum Beispiel aus 16 Bit, während eine byte-Zahl aus nur 8 bit besteht.

Eine Datenstruktur ist dagegen aus einfachen Datentypen zusammengesetzt. Als einfachste Datenstruktur wird der Array angesehen, der aus endlich vielen Elementen des gleichen Datentyps besteht. Andere Datenstrukturen sind einfach oder doppelt verkettete dynamische Listen, dynamische Binärbäume etc.

Persönliche Meinung von mir: Stacks, Queues, Dictionarys etc. sind für mich keine Datenstrukturen, sondern Abstrakte Datentypen (siehe unten). Ich schreibe dies nur, weil in der Wikipedia die Begriffe Stack, Queue etc. im Artikel über Datenstrukturen genannt werden.

14.2 Der Abstrakte Datentyp Stack

Bei einer Datenstruktur wird genau angegeben, wie sie zu implementieren ist. Eine dynamische Liste beispielsweise besteht aus Knoten mit je einer Wert-Eigenschaft und einem Nachfolger auf den nächsten Knoten. Bei einer doppelt verketteten dynamische Liste hat darüber hinaus jeder Knoten auch noch einen Zeiger auf das Vorgängerelement.

Ein Abstrakter Datentyp (ADT) ist dagegen völlig anderes organisiert. Es werden überhaupt keine Vorschriften gemacht, aus welchen Datentypen oder Datenstrukturen der ADT zusammengesetzt ist oder wie die Elemente des ADT physikalisch im Arbeitsspeicher organisiert sein müssen. Das alles ist völlig egal! Wichtig ist nur, dass die Operationen des ADT zuverlässig implementiert werden.

Machen wir uns dies am Beispiel des wohl bekanntesten Abstrakten Datentyps klar. Wir definieren den ADT Stack ausschließlich über seine Operationen:

14.3 Arbeitsweise eines Stacks

Ein Stack arbeitet nach dem LIFO-Prinzip: Last in, first out. Das Element, das zuletzt eingefügt wurde, wird auch als erstes wieder entfernt. Ein anschauliches Beispiel für einen solchen Stack ist ein Tellerstapel in der Kantine. Die Studenten legen ihre benutzten Teller oben auf den Stapel. Der volle Stapel wird in die Küche gefahren und dann von oben her wieder abgebaut (von unten her wäre auch nicht ratsam bei Porzellantellern).

Veranschaulichen wir uns die Arbeitsweise der Stack-Operationen:

Nach Aufruf der Init()-Operation ist der Stack zwar vorhanden, aber er enthält noch keine Elemente.

Nach Aufruf von Push(12) enthält der Stack genau ein Element, nämlich die Zahl 12.

Nach Aufruf von Push(8) sind schon zwei Elemente im Stack enthalten. Die 8 wurde zuletzt zugefügt, befindet sich also oben im Stack.

Wenn Pop() aufgerufen wird, wird die 8 wieder entfernt - sie war ja die zuletzt zugefügte Zahl.

Nach Push(15) besteht der Stack wieder aus zwei Elementen. Die 15 wurde zuletzt gepusht, also findet sie sich oben im Stack wieder.

Nach Push(13) besteht der Stack sogar aus drei Elementen. Und wieder ist die zuletzt gepushte Zahl ganz oben im Stack.

Beispiele für Stacks im Alltag:

- Tellerstapel in der Kantine
- Tabletten in einer röhrenförmigen Verpackung
- Mülltonne (das, was man zuletzt weggeworfen hat, liegt noch oben)

1. Datentypen und Datenstrukturen
2. Der Abstrakte Datentyp Stack
3. Arbeitsweise eines Stacks
4. Implementierung einer Stack-Klasse
5. Der ADT Stack im NRW-Zentralabitur
6. Aufgaben mit der Klasse Stack
7. Der ADT Queue
8. Der ADT Dictionary
9. Abstrakte Datentypen
10. Der ADT Stack - eine axiomatische Sicht
11. Der ADT Lineare Liste

14.4 Implementierung einer Stack-Klasse

Schritt 1 - Erzeugen der Klasse Stack

Starten Sie BlueJ, legen Sie ein neues Projekt an und erzeugen Sie dann die Klasse Stack. Entfernen Sie alle überflüssigen Kommentare. Anschließend müsste Ihr Quelltext so aussehen:

public class Stack
{
   public Stack()
   {
   }
}

Zugegeben, damit können wir noch nicht viel anfangen, aber immerhin ist es schon einmal ein Anfang. Jede große Klasse fängt einmal klein an.

Schritt 2 - Die Attribute / Initialisierung

Wir wollen die int-Zahlen, die der Stack verwalten soll, in einem Array speichern. Also müssen wir ein entsprechendes Attribut anlegen. Ein Array muss immer eine bestimmte Größe haben, die anschließend nicht mehr überschritten werden darf, weil es sonst einen Laufzeitfehler gibt. Diese Größe müssen wir im Konstruktor festlegen. Außerdem müssen wir darüber Buch führen, wie viele Zahlen sich tatsächlich in dem Stack befinden. Also benötigen wir eine Art Zähler.

public class Stack 
{ 
   private int[] liste;
   private int max;

   public Stack() 
   { 
      liste = new int[100];
      max = 0;
   } 
}

Schritt 3 - Die Methode empty()

Wir fangen mit dieser Methode an, weil es die einfachste ist. Wann ist der Stack leer? Ganz einfach: Der Stack ist genau dann leer, wenn er 0 Elemente enthält. Also schreiben wir:

public boolean empty()
{
   return max == 0;
}

Und das funktioniert fehlerfrei. Die sondierende Methode empty() liefert einen boolean-Wert zurück, also entweder TRUE oder FALSE. Also muss hinter der return-Anweisung ein Ausdruck stehen, der einen dieser beiden Werte annimmt. Und genau dies ist bei dem Vergleich max == 0 der Fall. Entweder ist max == 0, dann wird der Wert TRUE zurück gegeben, oder es gilt max <> 0, dann wird der Wert FALSE zurück geliefert.

Schritt 4 - Die Methode top()

Diese Methode ist schon etwas komplizierter. Angenommen, der Stack enthält bereits drei Elemente, dann sieht er vielleicht so aus:

Ach so, das ist ja die "abstrakte" Darstellung ohne Rücksichtnahme auf eine konkrete Implementierung durch eine Datenstruktur. Also müssen wir uns jetzt den Array vorstellen, und - wie Sie alle wissen - liegt ein Array ja stets quer. Also müssen wir neu zeichnen:

Einen Arrray mit 100 Elementen konnte ich hier schlecht zeichnen, also habe ich der Einfachheit halber einen Array mit nur 10 Elementen skizziert. Die ersten drei Elemente (Index 0, 1 und 2) speichern jetzt den Stack, der ja aus drei Zahlen besteht. Die restlichen sieben Arrayelemente sind leer bzw. enthalten den Wert 0, der bei der Initialisierung eines int-Arrays ja automatisch in die Arrayelemente geschrieben wird.

Das Attribut max hat im Augenblick den Wert 3, da ja drei Stackelemente vorhanden sind.

Das "oberste" Element dieser drei Stackelemente ist die 9, die Zahl also, die sich in dem Array an Position 2 befindet, also an Position max - 1.

Pushen wir nun die Zahl 7 auf den Stack. Zunächst die übliche Darstellung:

Und jetzt wieder der Array:

Das Attribut max hat jetzt den Wert 4 (es sind ja jetzt vier Elemente im Stack), und das oberste Element befindet sich an Position 3 (max - 1) und hat den Wert 7.

Wie bekommen wir stets den Wert des obersten Elementes zurück? Ganz einfach, indem wir den Wert des Arrayelementes mit dem Index max - 1 zurück liefern. Damit ist die Implementation von top() eigentlich klar:

public int top()
{
   if (!empty())
      return liste[max-1];
   else
      return -1;
}

Zunächst wird kontrolliert, ob der Stack nicht eventuell leer ist. Ein leerer Stack hat nämlich kein top-Element, kann also auch keinen Wert zurück liefern. Wenn der Stack mindestens ein Element enthält, wird der Wert des obersten Elementes (mit dem Index max-1) zurück geliefert.

Was aber, wenn der Stack leer ist. Was soll dann zurück geliefert werden? Hier gehen die Meinungen der einzelnen Stack-Implementeure auseinander. Ich persönlich bevorzuge die oben abgedruckte Methode, einfach eine definierte Fehler-Nummer, hier also -1, zurück zu geben. Andere Implementeure machen es wie folgt:

public int top()
{
   if (!empty())
      return liste[max-1];
    else
      throw new RuntimeException
          ("Stack ist leer!");
}

Hier lassen wir also einen Laufzeitfehler zu, wenn jemand die Methode top() aufruf, obwohl der Stack leer ist. Das Programm bricht ab, und man landet in dem BlueJ-Quelltext, wobei die Zeile, die den Fehler verursacht hat, gelb markiert ist. In Rot erscheint unten im BlueJ-Fenster dann die Fehlermeldung "Stack ist leer!". Wir haben uns hier also eine eigene Laufzeitfehlermeldung gebastelt, und das alles mit der recht einfachen throw new RuntimeException()-Anweisung.

Ich persönlich finde diese Methode aber recht barbarisch, sie kommt noch aus den Zeiten der harten C-Programmierung und spiegelt die Meinung vieler hartgesottener Programmierer wider: "...ist doch nicht mein Problem, wenn jemand die top-Methode aufruft, obwohl der Stack leer ist". Ich denke, eine Methode sollte sich heutzutage etwas "gesitteter" verhalten und nicht gleich das ganze Programm zum Absturz bringen, wenn sie mal aus Versehen aufgerufen wird. Kein Wunder, wenn ganze Betriebssysteme dauernd abstürzen, wenn die Routinen auf diese Weise programmiert worden sind.

Schritt 5 - Die Methode push()

Kommen wir jetzt zur kompliziertesten Methode des Stacks. Betrachten wir dazu noch einmal die letzte Abbildung des Arrays:

Wir wollen jetzt die Zahl 13 auf den Stack pushen. Wie müssen wir vorgehen?

Da der Array noch Platz für weitere Elemente bietet (das müssen wir natürlich überprüfen!), können wir einfach das Attribut max erhöhen, hier also von 4 auf 5, und dann schreiben wir in das Element liste[max-1] den neuen Wert hinein:

public void push(int x)
{
   if (max < 10)
   {
      max++;
      liste[max-1] = x;
   }
}

Hier noch einmal ein weiteres Fallbeispiel: Der Stack enthält jetzt neun Elemente:

Max hat den Wert 9, da ja neun Elemente enthalten sind. Also liefert die Abfrage max < 10 den Wert TRUE, da ja 9 bekanntlich kleiner als 10 ist. Somit wird max um Eins erhöht und bekommt jetzt den Wert 10. Anschließend wird in das Arrayelement mit dem Index 10-1 = 9 der neue Wert hineingeschrieben, zum Beispiel die 6.

Jetzt hat max den Wert 10. Wird erneut gespusht, so liefert die Abfrage max < 10 den Wert false, den 10 ist nicht kleiner als 10. Also wird max nicht weiter erhöht, und es wird auch kein neuer Wert mehr in den Array hinein geschrieben. Es passiert gar nichts. Es wird auch keine Laufzeitfehlermeldung produziert, die den Programmablauf stören würde.

Eine alternative Implementation von push könnte so aussehen:

public void push(int x)
{
   if (max < 10)
   {
      liste[max] = x;
      max++;
   }
}

Sehen Sie den Unterschied? Hier wird - nach der Überprüfung, ob der Array voll ist - der neue Wert direkt in das Element liste[max] geschrieben. Da max noch nicht inkrementiert wurde, muss jetzt auch nicht der Wert 1 von max abgezogen werden, um den Index zu erhalten. Ich finde, diese Implementierung sieht schöner aus als die erste.

Schritt 6: Die Methode pop()

Kommen wir schließlich zur letzten Methode, pop(). Diese ist wieder recht einfach zu implementieren. Schauen wir uns ein Fallbeispiel an:

Das Attribut max hat den Wert 4, und nach dem Ausführen des pop()-Befehls muss es den Wert 3 haben. Also schreiben wir doch einfach:

public void pop()
{
   if (!empty()) max--;
}

Wenn der Stack bereits leer ist, dürfen wir max natürlich nicht dekrementieren. Nach der Ausführung des pop()-Befehls steht immer noch der Wert 7 in dem Arrayelement mit dem Index 3.

Nur interessiert dies keinen, da max den Wert 3 gespeichert hat und nicht den Wert 4. Daher gilt offiziell die 9 (Index max-1) als oberstes Stackelement. Wird nun erneut der push()-Befehl aufgerufen, so wird die neue Zahl in das Arrayelement mit dem Index 3 geschrieben, die 7 wird also überschrieben.

Zusammenfassung

Hier noch einmal alle Methoden zusammengefasst:

14.5 Der ADT Stack im NRW-Zentralabitur

siehe: Die Klasse Stack nach den offiziellen Vorgaben

14.6 Aufgaben mit der Klasse Stack

siehe: Die Klasse Stack nach den offiziellen Vorgaben

Es ist durchaus möglich, dass Sie im Zentralabitur eine arraybasierte Stack-Klasse selbst programmieren müssen; das sollte für Sie nach dem Studium dieser Seite überhaupt kein Problem sein. Es könnte aber auch sein, dass Sie den Stack als Werkzeug einsetzen müssen, um andere Datentypen wie zum Beispiel eine Queue zu implementieren, oder dass Sie eine Methode schreiben müssen, mit der man einen Stack s1 in einen zweiten Stack s2 hineinkopieren kann. Solche und ähnliche Aufgaben finden Sie in der Buchversion des Lehrgangs, die Lösungen zu allen Übungen der Folge 14 finden Sie in dem Lehrerband, der bereits erhältlich ist (als PDF-Dokument)

14.7 Der ADT Queue

Eine Schlange oder Queue arbeitet nach dem FIFO-Prinzip: First in, first out. Das Element, das zuerst eingefügt wurde, wird auch als erstes wieder entfernt. Ein anschauliches Beispiel für eine solche Schlange ist der Einkauf in einem Supermarkt, und zwar in zweifacher Hinsicht:

Wenn Sie Ihren Einkauf beendet haben und zahlen wollen, stellen Sie sich hinten an die Warteschlange an. Der Kunde, der sich als erster angestellt hat, wird auch als erster bedient. Der letzte Kunde wird zuletzt bedient.

Jetzt sind Sie endlich dran. Sie legen all die Waren, die Sie eingekauft haben, auf das Transportband. Auch hier handelt es sich um eine Schlange. Die Tomatensuppe, die sie zuerst auf das Band gelegt haben, wird von der Kassiererin auch als erstes in die Kasse eingetippt. Und die Ware, die Sie zuletzt auf das Band gelegt haben, wird auch als letzte registriert.

Wir wollen jetzt etwas verallgemeinern:

Veranschaulichen wir uns die Arbeitsweise der Queue-Operationen:

Lösungshinweise:

Es hat sich als sinnvoll erwiesen, etwas mehr Arbeit in die Umsetzung der push()-Methode des QStacks zu investieren. Wenn Sie die push()-Methode korrekt programmieren, ist die Implementierung der pop()- und top()-Methode ein Kinderspiel. Passen Sie bei push() jedoch nicht auf, kann es sogar unmöglich werden, die pop()-Methode zu implementieren.

Am Besten, Sie machen sich das alles erst mal mit Bleistift und Papier klar!

Die komplette Lösung entnehmen Sie bitte dem Lehrerband, den Sie bei von mir erhalten können.

14.8 Der ADT Dictionary

Ein Dictionary oder Lexikon ist normalerweise ein Speicher für Strings oder komplexere Datensätze. Hier die allgemeine Definition des ADT Dictionary:

Sie sehen, das hier überhaupt keine Angaben gemacht werden, wie und wo die hinzugefügten Elemente im Lexikon gespeichert werden oder ob die Elemente innerhalb des Lexikons irgendwie sortiert werden.

Das lässt Ihnen natürlich bei der folgenden Übung einige Freiheiten; jedenfalls dann, wenn Sie die leichtere Alternative wählen.

14.9 Abstrakte Datentypen

siehe bitte Abschnitt für Abiturienten

14.10 Der ADT Stack - eine axiomatische Sicht

siehe bitte Abschnitt für Abiturienten

14.11 Der ADT Lineare Liste

Verschiedene Definitionen des ADT Lineare Liste - eine Sammlung

und weiter mit Folge 17 - Zeigerstrukturen

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 15. April 2006 und um zwei Aufgaben ergänzt am 20. Oktober 2008.

Völlig neu erstellt am 22. Oktober 2009 in den Herbstferien.