Auf dieser Seite wollen wir uns einen Überblick über die - für den Schulunterricht - wichtigsten abstrakten Datentypen verschaffen. Wir beginnen mit dem ADT Stack.
ADT Stack
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: Public domain.
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.
Ein anderes Beispiel für eine Schlange: In einer Arztpraxis werden Zettel mit Nummern an die Wartenden verteilt. 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.
Wenn man an seinem Rechner sitzt und eine Reihe von Dokumenten drucken will, kommt die Drucker-Warteschlange ins Spiel: Der erste Auftrag wird auch zuerst gedruckt, dann der zweite Auftrag und so fort.
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 nichtlinearen ADT, nämlich für den binären Suchbaum. Wenn man 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...