Rekursive Algorithmen
Speicherorganisation
Bei rekursiven Programmiertechniken spielt es eine Rolle, in welcher Art und Weise auf Daten zugegriffen werden kann.
Wenn ich den Programmcode (ein kleiner Ausschnitt aus dem Programm HANOI)
procedure LiesMirEineListeEin;
var
SL: TStringList;
begin
SL := TStringList.Create;
SL.Clear;
SL.Add ('Um die Auswahl der Scheiben');
SL.Add ('jetzt zu beenden,');
SL.Add ('klicken Sie bitte');
SL.Add ('den gewünschten Zielplatz');
SL.Add ('(Platz B oder Platz C)');
SL.Add ('an.');
Memo1.Lines := SL;
SL.Free;
end;
vor mir habe, muss ich nicht wissen, wie die Daten intern organisiert sind. Ich kann mich darauf verlassen, dass Delphi aus dem Code, den ich hier eingegeben habe, eine Liste erzeugt, die in ein Memo eingibt und die Liste danach freigibt.
In anderen Fällen – beispielsweise auch bei der Rekursion – ist es dagegen besser, wenn ich mir einige Gedanken darüber mache, was Delphi da im Inneren mit seinen Speichern alles treibt.
Zwei wichtige Organisationsprinzipien für Speicherdaten muss ich zum besseren Verständnis hier nennen:
1. Die Warteschlange (Queue)
Eine Warteschlange wird immer dann benötigt, wenn von einer Quelle Daten schneller gesendet werden, als sie von einem Empfänger verarbeitet werden können.
Der Tastaturpuffer beispielsweise ist eine Queue. Oft werden Zeichen schneller eingegeben, als der Computer sie verarbeiten kann. Würden die von der Tastatur gesendeten Zeichen nicht in einer Warteschlange eingereiht, so könnten eingegebene Zeichen verloren gehen.
Die Queue arbeitet nach dem Organisationsprinzip FirstInFirstOut (FIFO). Bei einer Warteschlange dürfen deshalb Daten NUR AM ENDE EINGEFÜGT UND AM ANFANG GELÖSCHT werden.
2. Der Kellerspeicher (Stack)
Bei der Abarbeitung eines kompilierten Programms enthält der Maschinencode bei Prozeduraufrufen Anweisungen zur Speicherung der Rücksprungadressen auf dem Programmstack. Das hat zur Folge, dass zuerst die innersten Prozeduren oder Funktionen abgearbeitet werden und danach erst die Methoden, die vorher aufgerufen wurden. Zuletzt wird als oberstes Programm das Hauptprogramm wieder aktiviert.
Wenn wir uns diese Arbeitsweise des Kellerspeichers (Programmstack) ansehen, können wir unschwer erkennen, dass der Stack seine Daten in anderer Weise organisiert wie die Queue.
Ein Stack ist ein Datenspeicher, der mit einem Bücherstapel verglichen werden kann. Es kann immer nur mit dem obersten Buch gearbeitet werden. Das Buch, das man zuletzt aufgelegt hat, muss auch als erstes entfernt werden. Will man an das unterste Buch, so müssen die darauf liegenden Bücher, beginnend mit dem obersten Buch, der Reihe nach entfernt werden.
Der Kellerspeicher arbeitet nach dem Organisationsprinzip LastInFirstOut (LIFO). Bei einem Kellerspeicher können deshalb Daten NUR AM ANFANG EINGEFÜGT UND AM ANFANG AUCH WIEDER GELÖSCHT werden.
Übrigens: Wollte man auf einer Queue oder auf einem Stack nur einzelne Zeichen verwalten, könnte man das auch mit Hilfe eines Strings oder einer Liste realisieren. Ist die Zugriffsordnung festgelegt, bedeutet das keinerlei Probleme.