Nachdem ich schon die Verketteten Listen besprochen habe, möchte ich in diesem Artikel auf eine weitere grundlegende Datenstruktur eingehen, die jeder Programmierer kennen sollte: Den Stack, der auch Stapel bzw. Stapelspeicher genannt wird.
Was macht eigentlich ein Stack? Nun, er ist - wie auch die verkettete Liste - im Wesentlich eine Datenstruktur zum Speichern von Daten und zwar eine, die man sich am Besten wirklich wie einen Stapel von Dateneinheiten vorstellt.
Es ist ja i.d.R. so, dass man nur am oberen Ende eines Stapels etwas drauflegen oder entfernen kann ohne die Stabilität dieses Gebildes ernsthaft zu gefährden.
Genauso funktioniert auch ein Stack: Die Daten, die als letztes auf den Stapel gelangen, werden als erstes wieder davon entfernt. Dies entspricht also der LIFO Datenverarbeitung: Last In, First Out, im Gegensatz zu einer Queue, wo man FIFO hat.
Es hat sich eingebürgert, den üblichen Operationen mit Stacks bestimmte Namen zu geben: Push für das Ablegen eines Datums auf dem Stapel, Pop, um das oberste Element vom Stapel zu entfernen (und es zurückzugeben), Peek um das oberste Element nur "anzugucken" ohne es zu entfernen.
Als Implementierung werden wir eine Klasse schreiben, die eine verkettete Liste verwaltet, aber eben nur am Anfang einfügt und entfernt. Dabei werden wir wieder nur Integer-Variablen als Daten benutzen, wie wir es schon im Artikel über Verkettete Listen getan haben. Selbstverständlich sind auch Implementierungen für andere Datentypen denkbar. In C++ könnte man beispielsweise mit Hilfe eines Templates eine Stack-Klasse für jeden Datentyp programmieren, in Java könnte man einen Stack für den Typ object implementieren, der dann ja mit allen Variablen kompatibel wäre. (Obwohl es auch so genannte Generics in Java gibt, die mit den C++ Templates vergleichbar sind)
In C++ könnte unsere Klasse so aussehen:
\sourceon C++
// die Definition aus dem letzten Artikel
// für die verkettete Liste, die wir
// intern verwenden wollen.
typedef struct _Node *tpNode;
typedef struct _Node
{
int data;
tpNode next;
} tNode;
// Die eigentliche Stack-Klasse
class cStack
{
public:
cStack();
~cStack();
int Pop();
int Peek();
void Push(int data);
int Count();
private:
tpNode top;
int cnt;
};
\sourceoff
Wir haben hier also eine Klasse cStack, für die wir Konstruktor und Destruktor implementieren, wie es sich für eine Klasse gehört, die dynamische Speicherstrukturen verwaltet.
Wir werden die drei Operationen Pop, Push und Peek implementieren und, da sowas immer nützlich ist, eine Methode einbauen, die die aktuelle Anzahl von Elementen im Stack zurückliefert.
Nach Java portiert würde dies so aussehen:
\sourceon Java
// Auch hier die Definition aus
// dem letzten Artikel.
class cNode
{
public int data;
public cNode next;
}
class cStack
{
private cNode top;
private int cnt;
public cStack(){/* kommt gleich */}
public int Pop(){/* kommt gleich */}
public int Peek(){/* kommt gleich */}
public void Push(int data){/* kommt gleich */}
public int Count(){/* kommt gleich */}
}
\sourceoff
Diese Klasse funktioniert also analog zur C++ Klasse. Einziger Unterschied ist der fehlende Destruktor, den wir aber auch nicht brauchen werden, da sich ja der Garbage-Collector um alles kümmern wird.
Natürlich sind auch andere Implementierung einer Stack-Klasse denkbar. Man könnte z.B. auch Arrays statt verketteter Listen verwenden, wenn man den Stack für solche Daten entwirft, die weniger dynamische Programmierung benötigen.
Nun, wie implementieren wir das konkret? Durch die Vorarbeit aus dem Artikel über verkettete Listen ist das eigentlich ganz einfach, denn wir können direkt auf die dort implementierten Funktion zurückgreifen.
\sourceon C++
cStack::cStack
{
this->top = NULL;
this->cnt = 0;
}
cStack::~cStack
{
if(this->top != NULL)
{
DeleteList(&(this->top));
}
}
int cStack::Count()
{
return this->cnt;
}
\sourceoff
Bis hierhin ist der Code noch so gut wie selbsterklärend: Der Konstruktor cStack initialisiert die beiden lokalen Variablen mit den Standardwerten NULL bzw. 0, die einen leeren Stack repräsentieren sollen.
Der Destruktor ~cStack tut genau das, was man von ihm erwartet: Sofern es etwas zum Aufräumen gibt, räumt er auf. Sprich: er löscht die verkettete Liste, mit der wir den Stack implementieren.
Und die Methode Count ist am einfachsten von allen: Sie gibt schlicht die aktuelle Anzahl von Elementen im Stack zurück.
Widmen wir uns lieber dem spannenderen Teil: Der Implementation der Push-, Peek- und Pop-Operation:
\sourceon C++
// Push legt ein neues Element
// auf dem Stapel ab
void cStack::Push(int data)
{
tpNode pNewNode=new tNode();
if(pNewNode != NULL)
{
pNewNode->data = data;
pNewNode->next = this->top;
this->top = pNewNode;
this->cnt++;
}
else
{
stderr << "Fehler bei der Speicherreservierung";
}
}
\sourceoff
Auch hier kann man relativ schnell einsehen, was geschieht. Es wird mit Hilfe des new-Operators ein neues tNode-Objekt angelegt, das mit den neuen Daten gefüllt wird. Dann wird der next-Zeiger des neuen Objekts auf den top-Zeiger gesetzt. Das heißt, dass das bisherige oberste Element zum zweit-obersten Element wird, was ja auch genau das ist, was wir erreichen wollten mit der Push-Operation.
Schließlich wird noch der Zeiger für das oberste Element auf unseren neuen Knoten gesetzt und der Zähler um 1 erhöht.
Interessant ist vielleicht noch die if-Abfrage, die hier vorkommt. Wenn es - aus welchen Gründen auch immer - fehlschlagen sollte, neuen Speicher mit new zu reservieren, so wird der NULL-Zeiger zurückgegeben, statt eines gültigen Zeigers auf den neuen Speicher. Wir geben in diesem Fall also eine Fehlermeldung in den Standard-Fehler-Stream stderr aus.
Auf zur nächsten Hürde: Peek
\sourceon C++
// Peek gibt das oberste Element
// vom Stapel zurück, sofern der
// Stapel nichtleer ist.
int cStack::Peek()
{
if(this->top != NULL)
{
return this->top->data;
}
else
{
stderr << "Fehler: Stack ist leer";
return 0;
}
}
\sourceoff
Hier ist der Code wieder selbsterklärend: Wenn der top-Zeiger nicht NULL ist, wenn also ein Element im Stapel ist, dann werden genau dessen Daten zurückgegeben. Wenn der Stapel leer ist, so wird eine Fehlermeldung ausgegeben.
Interessanter wird es wieder bei der Pop-Operation:
\sourceon C++
// Pop gibt das oberste Element
// vom Stapel zurück und entfernt
// es vom Stapel, sofern der Stack
// nichtleer ist.
int cStack::Pop()
{
if(this->top != NULL)
{
tpNode p = this->top;
int ret = this->top->data;
this->top = this->top->next;
this->cnt--;
delete p;
return ret;
}
else
{
stderr << "Fehler: Stack ist leer";
return 0;
}
}
\sourceoff
Dies ist noch einmal eine gute Übung zum Umgang mit Zeigern: Wir speichern zunächst den alten top-Zeiger in der Variablen p, damit wir ihn später noch haben, wenn wir ihn löschen wollen.
Dann kopieren wir die Daten aus dem Element nach ret, dem zukünftigen Return-Wert. Danach setzen wir den top-Zeiger auf das zweit-oberste Element, denn das oberste wollen wir ja löschen.
Dann wird die Anzahl der Elemente korrigiert und die delete-Anweisung nimmt nun den eigentlichen Lösch-Vorgang vor. Schließlich und endlich springen wir durch Rückgabe der Daten des gerade entfernten Knotens zurück.
Auch hier haben wir natürlich eine Abfrage vorgeschalten, um zu prüfen, ob überhaupt etwas auf dem Stack liegt, was wir entfernen können.
Die Portierung nach anderen Sprachen wie Java ist aufgrund der Einfachheit wesentlich unkomplizierter als bei den verketteten Listen:
\sourceon Java
class cStack
{
cStack()
{
this.top = null;
this.cnt = 0;
}
/* Der Destruktor entfällt, da
Java einen Garbage-Collector
unterstützt.
*/
int Count()
{
return this.cnt;
}
void Push(int data)
{
cNode pNewNode=new cNode();
if(pNewNode != null)
{
pNewNode.data = data;
pNewNode.next = this.top;
this.top = pNewNode;
this.cnt++;
}
else
{
throw new OutOfMemoryError("Fehler bei der Speicherreservierung");
}
}
int Peek()
{
if(this.top != null)
{
return this.top.data;
}
else
{
throw new EmptyStackException("Fehler: Stack ist leer");
}
}
int Pop()
{
if(this.top != null)
{
int ret = this.top.data;
this.top = this.top.next;
this.cnt--;
return ret;
}
else
{
throw new EmptyStackException("Fehler: Stack ist leer");
}
}
}
\sourceoff
Okay schön. Jetzt haben wir eine funktionierende Stack-Klasse. Aber was genau machen wir damit? Wo werden Stacks verwendet?
Erstaunlicherweise lautet die Antwort: Direkt vor eurer Nase! Ja. Kein Scherz. In diesem Moment benutzt euer Computer - ganz egal, ob Mac oder PC, Linux oder Windows - einen wahrscheinlich nicht einmal sehr kleinen Stack.
Sehr viel wahrscheinlicher benutzt er sogar verdammt viele: Nämlich mindestens einen für jeden Thread, den euer Betriebssystem gerade ausführt.
Stacks sind Grundstrukturen der modernen Rechner-Architektur. Sie sind nicht nur in der theoretischen Informatik äußerst wichtig, sondern in beinahe jedem Prozessor direkt in die Hardware implementiert als eines der wichtigstens Kern-Elemente.
Bei jedem Aufruf einer Funktion bzw. eines Unterprogramms geschieht dabei folgendes: Der bisherige laufende Teil der Anwendung wird eingefroren: Alle Variablen werden auf einen Stack gespeichert und die Kontrolle wird an das Unterprogramm übergeben.
Dann wird die entsprechende Funktion ausgeführt (eventuell mit weiteren Funktionen, so dass der Stack während dessen weiter wächst).
Beim Rücksprung werden die Werte der lokalen Variablen aus dem Stack wieder hergestellt (der Stack schrumpft also wieder, wenn die Unterprogramme beendet sind) und die ursprüngliche Funktion wird weiter ausgeführt.
Man erkennt sofort das LIFO-Prinzip: Die Variablen, die als letzte auf den Stapel getan wurden, gehören zur zuletzt eingefrorenen Funktion. Da beim Rückweg die Funktionen in der umgekehrten Reihenfolge fortgesetzt werden, wie sie eingefroren wurde, muss der Stapel natürlich auch von oben nach unten geleert werden.
Das wollen wir kurz an einem Beispiel verdeutlichen. Wir betrachten dafür ganz diese sehr einfache rekursive Funktion
\sourceon C/C++/Java/eine von vielen anderen ähnlichen Sprachen
// factorial berechnet die Fakultät
// natürlicher Zahlen auf
// rekursive Weise.
int factorial(int n)
{
if(n < 2) return 1;
return n*factorial(n-1);
}
\sourceoff
Wenn wir aus einem Programm heraus nun z.B. factorial(3) aufrufen passiert nun folgendes:
1.) Die Werte der lokalen Variablen der aufrufenden Funktion werden auf den Stack gepackt. Zusammen mit der Speicheradresse, die das Kommando enthält, mit dem es nach dem Ende der Funktion factorial weitergehen soll, der so genannten Rücksprungadresse.
2.) Beim ersten Aufruf der Fakultäts-Funktion ist n=3. Die Abfrage n<2 wird daher zu false ausgewertet, also wird factorial(3-1) aufgrufen, das heißt es werden die Wert der lokalen Variablen (hier nur n=3) auf den Stack abgelegt und anschließend wird die Funktion ein zweites Mal aufgerufen.
3.) Es geht erneut eine Runde. Auch jetzt wird n<2 zu false ausgewertet, weil die lokale Variable n in dieser Rekursionsstufe den Wert 2 hat. Es wird also noch factorial(2-1) aufgerufen, nachdem dieser Wert auf dem Stack ebenfalls gespeichert wurde. Auch hier mit dabei: Die Rücksprungadresse, damit unser Programm den Faden nicht verliert auf dem Rückweg.
4.) Letzte Station auf dem Hinweg: n ist nun 1 und die Rekursion bricht hier ab, denn n<2 wird dieses Mal zu true ausgewertet und somit wird 1 zurückgegeben. Das wird auch mit dem Stack realisiert, denn es wird genau dieser Rückgabewert einfach mit auf den Stack getan und der Rücksprungcode ausgeführt.
5.) Wir sind zurück in der zweiten Rekursionsstufe angelangt. Auf dem Stack liegt der Rückgabewert das Aufrufs von factorial(1), also der Wert 1. Dieser wird in eine temporäre Variable geladen. Es befindet sich auch der Wert 2 auf dem Stack, nämlich genau der Wert, den n in dieser Stufe hat. n wird damit wieder belegt und wir können weiterrechnen. Es wird 2*1 berechnet und das Ergebnis zurückgegeben, d.h. wieder auf den Stack getan. Auch jetzt brauchen wir dringend die Rücksprungadresse, damit wir wissen, wo es lang geht.
6.) Back at the roots: Die erste Rekursionsstufe ist wieder erreicht. Hier stellen wir aus dem Stack den Wert n=3 wieder her und stellen fest, dass uns die zweite Stufe das Zwischenergebnis 2 da gelassen hat. Wir freuen uns, berechnen 3*2 und wissen somit, was 3! ist. Dieses tun wir erneut auf den Stack, denn dies ist unser Rückgabewert.
7.) Ein letztes Mal erfolgt der Rücksprung. Jetzt sind wir bereits aus der factorial-Funktion herausgesprungen und befinden uns wieder im ursprünglichen Unterprogramm. Glücklicherweise haben wir aber auf dem Weg hierher mit Hilfe unseres Stacks das Ergebnis der Berechnungen aus den Unterfunktionen herüberretten können und können es jetzt verwenden. Ab hier nimmt das Programm dann seinen weiteren Verlauf.
Grob kann man sich so jeden Funktionsaufruf mit Hilfe des Stacks vorstellen. In der Realität gibt es aber viele variierende Details (z.B. bei Funktionen mit variabler Argumentanzahl).
Wer sich für eine konkretere Beschreibung interessiert, kann ja einmal hier schauen:
Der Stack Frame auf Intel-Prozessoren
Wer einmal das Prinzip, das hinter diesen Funktionsaufrüfen mit Hilfe des Stacks verstanden hat, hat einen entscheidenden Vorteil, denn diese Technik ist ein mächtiges Werkzeug für Programmierer.
Theoretisch kann man z.B. jeden rekursiven Algorithmus in einen iterativen umwandeln, indem man die Stack-Operationen selbst implementiert, statt sie dem Compiler zu überlassen. In manchen Fällen ist das tatsächlich sinnvoll, das zu tun, da der Algorithmus möglicherweise Optimierungen in dieser Hinsicht zulässt, von denen der Compiler nichts weiß, nicht wissen kann oder wissen darf.
Eine zweite, wie ich finde, sehr interessante Anwendungen von Stacks, die wohl viele von uns ebenfalls kennen, sind Formelparser.
Jemand, der sich ein bisschen für die Technik interessiert, hat sich sicherlich schonmal gefragt, wie ein CAS oder der fed z.B. einen geschriebenen Ausdruck wie 3+sin(5*4-3/(4+1)) ausgewertet und was geschehen muss, um so einen natürlichen Ausdruck in eine für den Computer verwertbare Struktur zu bringen.
Ein sehr weit verbreiteter Ansatz dazu ist die Verwendung der Postfix-Notation, die auch Umgekehrte Polnische Notation (UPN) genannt wird. Sie ist sehr viel weniger intuitiv als die natürliche Schreibweise (die auch Infix-Notation genannt wird), denn sie wird so verwendet, dass man zuerst die beiden Operanden notiert und erst dann den Operator. Der Operator kommt also nach (daher Postfix) den Operanden und steht nicht wie gewohnt zwischen (daher Infix) ihnen.
Beispiele:
Infix
Postfix
3+5
3 5 +
3-5*7
3 5 7 * -
(3-5)*7
3 5 - 7 *
2/(4-5/7+3/(8*9))
2 4 5 7 / - 3 8 9 * / + /
Trotz der kontra-intuitiven Schreibung hat die UPN entscheidende Vorteile: Zum einen ist sind Klammern überflüssig. Vorrangregeln können komplett durch die Reihenfolge der Operanden und Operatoren geklärt werden.
Zum andere ist das numerische Auswerten eines Postfix-Ausdruck sehr, sehr einfach zu implementieren, und zwar mit Hilfe eines Stacks: Man geht die Inputdaten der Reihe nach durch und unterscheidet zwei Fälle: Man ist auf eine Zahl gestoßen oder man hat einen Operator vor sich. Im ersten Fall packt man einfach die Zahl auf den Stack oben drauf. Im zweiten Fall nimmt man sich soviele Operanden wieder vom Stack herunter, wie man für die Ausführung des Operators noch benötigt. Dann verrechnet man diese Operanden und tut das (Zwischen-)Ergebnis zurück auf den Stack.
So wird der Stack während der Abarbeitung der Eingabefolge größer und kleiner. Am Ende jedoch bleibt (bei korrekter Eingabe) nur eine einzige Zahl auf dem Stack zurück, nämlich das Ergebnis der zuletzt ausgeführten Rechnung. Und dieses ist dann auch das Endergebnis.
Algorithmisch könnte das z.B. so aussehen:
\sourceon Pseudocode
float eval_upn(upn_data input)
{
Stack s=new Stack();
foreach(dings in input)
{
if(dings is a number)
{
s.Push(dings);
}
else //dings ist ein Operator
{
do
{
parameterliste += s.Pop();
}while(noch nicht genügend Parameter);
// Beim Ausrechnen muss darauf geachtet
// werden, dass die Parameter in der
// umgekehrten Reihenfolge vom Stack
// gekommen sind, wie sie hinein getan
// wurden.
ergebnis=rechne(dings,parameterliste);
s.Push(ergebnis);
}
}
if(s.Count != 1) Fehler();
return s.Peek();
}
\sourceoff
Diese beiden Vorteile - Klammernfreiheit und stackbasierte Auswertung - machen die UPN für die technische Anwendung sehr interessant und in Zeiten, als die Chips noch nicht so ausgefeilt waren, wie sie es heute sind, waren UPN-basierte Taschenrechner deshalb keine Seltenheit, weil sie mit weniger Ressourcen auskamen und in ihrer Funktion keineswegs eingeschränkt waren.
Dieses Verfahren ist natürlich nicht nur auf die 4 Grundrechenarten beschränkt. Prinzipiell ist es möglich, beliebige Rechenoperationen, Funktion, Konstanten etc. hinzunehmen. Dazu muss man nur die Parameteranzahl entsprechend variieren (Konstanten sind dann als 0-stellige Funktionen zu interpretieren).
Auf Arndt Brünners Matheseiten findet man einen JavaScript-Taschenrechner für komplexe Zahlen, der genau das obige Prinzip verwendet und viele verschiedene Funktionen bietet.
So, das war der zweite Artikel der Algorithmen-AG. Ich hoffe, ich konnte euch die Datenstruktur Stack und zwei ihrer vielseitigen Anwendungsmöglichkeiten näher bringen. Man könnte sicher noch unzählige Beispiele finden, denn wie schon die verkettete Liste sind auch Stacks von großer Wichtigkeit und weit verbreitet in der Programmierung.
Seid gespannt auf weitere Artikel unserer AG.
\sourceon
stack.Push(Gockel);
stack.Push(mfg);
\sourceoff
\(\begingroup\)Was wäre, wenn du einfach, anstatt das Rad neu zu erfinden in C++ zum Beispiel den std::stack verwendet hättest?
Also
\sourceon
...
#include
...
typedef std::stack Stack;
...
Stack my_stack_;
....
my_stack_.push(12);
my_stack_.push(15.77);
my_stack_.push(33.78);
...
top_element = my_stack_.top()
my_stack_.pop(); //löscht oberstes Element
\sourceoff
oder so?\(\endgroup\)
\(\begingroup\)@Anonymous:
Und du hättest mit diesem Code verstanden, was ein Stack ist, wozu man ihn braucht und was diese Funktionen tun?
Der Artikel soll dem Leser Wissen vermitteln, nicht "das Rad neu erfinden". Ich bin mir durchaus bewusst, dass jede vernünftige Programmiersprache Stacks und ähnliche Grundstrukturen schon fertig zu Verfügung stellt.
Trotzdem sind Stacks und verkettete Listen z.B. in jeder Anfänger-Programmier-Vorlesung ein wichtiges und für die meisten Studenten völlig neues Thema, das Erklärungen bedarf. Und genau das sollte dieser Artikel bieten.
mfg Gockel.\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
\sourceon
stack.Push(Gockel);
stack.Push(mfg);
\sourceoff
Get link to this article
Comments
Dieser Artikel ist im Verzeichnis der 
