ADT Stack
Wie bereits in der Einleitung angedeutet, wollen wir uns nun mit dem wichtigsten abstrankten Datentyp näher beschäftigen, dem ADT Stack. Aber auch die anderen gängigen ADTs werden auf dieser Seite kurz vorgestellt, nämlich der ADT Queue (Schlange), der ADT List (Liste) und schließlich der ADT Binary search tree (binärer Suchbaum).
Der Stack ist einer der bekanntesten Abstrakten Datentypen. Im Deutschen spricht man oft auch von einem Stapel oder einem Stapelspeicher. Man kann dabei durchaus an einen Tellerstapel denken:
Ein Stapel Teller
Photo: Ulrich Helmich 2019, Lizenz: siehe Seitenende.
Der ADT Stack wird durch folgende Operationen definiert:
- Init(): Erzeugt einen leeren Stack.
- Push(x): Das Element x wird hinzugefügt.
- Pop(): Das zuletzt hinzugefügte Element wird entfernt.
- Top(): Der Wert des zuletzt hinzugefügten Elementes wird zurückgeliefert.
- Empty(): Falls der Stack leer ist, wird TRUE zurückgeliefert, sonst FALSE.
Diese fünf Operationen beschreiben die Arbeitsweise eines Stacks vollständig. Bei der Definition des ADT werden nur die Operationen angegeben. Wie die Operationen intern arbeiten oder wie sie implementiert werden, ist dabei völlig uninteressant. Spontan würde man einen solchen Stack in Java sicherlich mit Hilfe eines Arrays implementieren, aber auch völlig andere Möglichkeiten wären denkbar. Hier tritt wieder das Prinzip der Datenkapselung in den Vordergrund.
ADT Queue / Schlange
Ein weiteres wichtiges Beispiel für einen Abstrakten Datentypen ist die Queue oder Schlange. Ein Beispiel für eine Queue im Alltag ist die Warteschlange vor einer Supermarktkasse. Wer sich zuerst anstellt, wird auch zuerst bedient. Hier die vollständige Definition dieses ADTs:
- Init(): Erzeugt eine leere Queue.
- Enqueue(x): Das Element x wird hinzugefügt.
- Dequeue(): Das zuerst hinzugefügte Element wird entfernt.
- Front(): Der Wert des zuerst hinzugefügten Elementes wird zurückgeliefert.
- Empty(): Falls die Queue leer ist, wird TRUE zurückgeliefert, sonst FALSE.
Beispiele für Schlangen finden sich im Alltagsleben jede Menge, weiter oben hatten wir schon die Schlange vor einer Supermarktkasse erwähnt. Ein anderes Beispiel ist, wenn in einer Arztpraxis Zettel mit Nummern an die Wartenden verteilt werden. Wer zuerst gekommen ist, bekommt die Nummer 1, der Nächste die Nummer 2 und so weiter. Aufgerufen wird dann - wenn kein Notfall vorliegt - zuerst die Nummer 1, dann die Nummer 2 und so weiter. Auch die Druckerwarteschlange sollte jedem PC-User bekannt sein. Der erste Druckauftrag wird auch zuerst gedruckt.
ADT List / Liste
Ein drittes Beispiel für einen linearen ADT ist die Liste. Hier die (unvollständige) Definition der Operationen des ADT List aus der englischen Wikipedia
Implementation of the list data structure may provide some of the following operations:
- a constructor for creating an empty list;
- an operation for testing whether or not a list is empty;
- an operation for prepending an entity to a list (prepending = vorne einfügen)
- an operation for appending an entity to a list (appending = hinten einfügen)
- an operation for determining the first component (or the "head") of a list
Interessant an dieser Definition ist die Tatsache, dass noch nicht einmal die Bezeichnungen der Operationen festgelegt werden, es wird lediglich beschreiben, was die Operationen können sollen.
Listen finden sich zum Beispiel auf dem Bildschirm eines Medienspielers, der eine Liste von Musikstücken oder Filmen anzeigt. Mit den Cursortasten der Fernbedienung kann man zum Anfang oder zum Ende der Liste springen sowie sich nach oben und unten durch die Liste durcharbeiten.
Gerade im Zentralabitur NRW spielen Listen eine enorm wichtige Rolle. Allerdings ist die NRW-Liste kein ADT, sondern eine Java-Klasse mit übertrieben vielen Methoden.
ADT Binary search tree / Binärer Suchbaum
Das vierte Beispiel steht für einen nicht-linearen ADT, nämlich für den binären Suchbaum, den wir bereits in der Folge 12.3 kurz kennengelernt haben, als es um schnelle Suchalgorithmen ging, und mit dem wir uns auch noch ausführlich beschäftigen werden. Wenn man hier im Internet sucht, findet man viele verschiedene Operationen für den binären Suchbaum. Hier ein Beispiel:
- Init(): Erzeugt einen leeren Suchbaum
- Insert(x): Das Element x wird hinzugefügt.
- Delete(x): Das Element x wird entfernt.
- Find(x): Das Element x wird gesucht
- FindMax(): Das größte Element wird gesucht und zurückgeliefert
- FindMin(): Das kleinste Element wird gesucht und zurückgeliefert
Bäume, vor allem binäre Suchbäume gibt es überall dort, wo viele Daten systematisch verwaltet werden müssen. Vor allem das Suchen in großen Datenmengen wird durch solche Suchbäume schlagartig vereinfacht.
Dies war eine kleine Übersicht über vier wichtige abstrakte Datentypen. Es gibt viele andere ADTs, aber für den Informatikunterricht in NRW sind diese vier ADTs die wichtigsten. Im Folgenden werden wir uns mit jedem einzelnen dieser vier ADTs näher beschäftigen, dabei beginnen wir mit dem ADT Stack.
Seitenanfang -
Weiter mit dem ADT Stack...