Python 3 - Lernen und professionell anwenden

747

Kapitel 27

Modellieren mit Kellern, Schlangen

und Graphen

Es gibt eine Reihe von »nützlichen« Datenstrukturen, die für viele Problemstellungen ver-

wendet werden können. Dazu gehören Stacks (Stapel, Keller), Queues (Schlangen) und Dar-

stellungen von Graphen. In diesem Kapitel geht es darum, wie man diese Datenstrukturen,

zusammen mit ihren typischen Operationen, als Python-Klassen implementiert und bei

Problemlösungen anwendet.

27.1 Stack (Keller, Stapel)

Abstrakter Datentyp

Ein abstrakter Datentyp (ADT) ist (allein) über Operationen definiert, die man mit seinen

Objekten ausführen kann. Die interne Struktur der Objekte – die Attribute – ist nach außen

hin völlig unsichtbar. Es handelt sich um eine restriktive Form einer Klasse, in der das

Geheimnisprinzip in besonders strenger Weise realisiert wird. Während in einer »norma-

len« Klasse über

setAttribut()- und getAttribut()-Methoden der (kontrollierte) Zugriff

auf einzelne Attribute möglich ist, ist bei einem ADT der direkte Zugriff grundsätzlich nicht

gestattet. Ja, die Umwelt weiß nicht einmal, welche Attribute die Klasse besitzt.

Die Idee des Stacks

Ein Beispiel für einen abstrakten Datentyp ist ein Stack. Das Wort bedeutet im Deutschen

so viel wie Stapel. Dennoch hat sich hierzulande auch die Bezeichnung Keller eingebürgert.

Wie Sie gleich sehen werden, ist der Begriff Stapel eigentlich anschaulicher.

Das Prinzip eines Stacks ist aus vielen Alltagssituationen bekannt. Betrachten wir einige

Beispiele (siehe Abbildung 27.1).

쐽 Ein Stapel von Tellern in Ihrem Küchenschrank erlaubt nur zwei Zugriffsmöglichkeiten.

Man kann (beim Ausräumen der Spülmaschine) einzelne Teller oben auf den Stapel

legen und (beim Tischdecken) Teller oben vom Stapel nehmen. Nicht unterstützt wird

der direkte Zugriff auf weiter unten liegende Teller. Es ist z.B. ziemlich schwierig, den

untersten Teller herauszuziehen. Der Teller, den Sie als letzten aus der Spülmaschine

genommen und auf den Stapel gelegt haben, nehmen Sie beim nächsten Tischdecken

als ersten wieder heraus. Man nennt dieses Prinzip last in first out oder kurz LIFO. Ein

Problem im Zusammenhang mit dem LIFO-Prinzip bei Tellerstapeln ist übrigens, dass

die oberen Teller viel häufiger benutzt werden als die unteren. Vielleicht haben Sie in

Ihrem Schrank sogar einen Teller, der noch niemals zum Einsatz gekommen ist.

Kapitel 27

Modellieren mit Kellern, Schlangen und Graphen

748

Abb. 27.1: Stacks im Alltag: Tellerstapel und Papiere auf dem Schreibtisch

쐽 Auf jedem Schreibtisch sammelt sich im Laufe der Zeit (mindestens) ein Stapel von

Papieren an: Notizzettel, Briefe, Kontoauszüge etc. Ein augenfälliges Merkmal eines sol-

chen Zettelstapels ist, dass Sie nur den oberen lesen können. Die darunter liegenden sind

verdeckt. Wenn Sie nach einer Notiz suchen, müssen Sie nacheinander von oben die

Papiere lesen, wegnehmen und z.B. auf einen zweiten Stapel legen, bis Sie das benötigte

Dokument gefunden haben. Sie können auch nicht feststellen, wie viele Papiere auf

einem Stapel liegen. Denn es kann ja sein, dass unter einem großen Blatt ein kleiner

Notizzettel verborgen ist. Das Einzige, was man mit einem Blick testen kann, ist, ob der

Stapel leer ist. Übrigens: Auch ein leerer Stapel (ohne ein einziges Element) ist ein Stapel.

Denn Sie haben auf Ihrem Schreibtisch vermutlich gewohnheitsmäßig eine Stelle (z.B.

neben dem Monitor oder neben dem Telefon), an der Sie alle Zettel ablegen, bevor Sie sie

abheften oder bearbeiten. Noch etwas: Indem Sie eine Stelle bestimmen, an der Sie Noti-

zen ablegen, haben Sie bereits einen Stapel generiert – auch wenn er zunächst leer ist.

Die Beispiele haben alle Merkmale eines Stacks illustriert. Wir abstrahieren und fassen

zusammen: Mit einem Stack lassen sich genau nachfolgende Operationen ausführen. Nach

dem Doppelpunkt steht jeweils die gebräuchliche Operationsbezeichnung.

쐽 Neuen (leeren) Stapel erzeugen: Stack()

쐽

Das oberste Element des Stacks entfernen: pop()

쐽

Auf den Stack ein neues Element legen: push()

쐽

Das oberste Element des Stacks lesen: top()

쐽

Testen, ob der Stack leer ist: empty()

Die Klasse Stack mit Python implementieren

Das folgende Skript enthält eine Klasse, die einen Stack implementiert, und ein kleines

Hauptprogramm, das ein

Stack-Objekt verwendet. Das Skript liest eine Zeichenkette ein

und gibt die enthaltenen Zeichen in umgekehrter Reihenfolge wieder aus.

Skript:

# stacktext.py

class Stack:

de f _ _in i t__( s elf ) : #1

self.__content = []

push()

pop()

top()