Datenspeicherung und Datenstrukturen

Stacks: Last In - First Out

Die erste Datenstruktur mit der man in seinem Programmierer-Leben Bekanntschaft macht, sind wohl die Felder mit wahlfreiem Zugriff, wie sie Einleitung: BASIC
Anhang: BasicBasic bereithält. Als nächstes kommt in aller Regel der STACK.

Stacks sind DATENSTAPEL, und diese Bezeichnung deutet an, wie sie funktionieren: Auf den, wie auch immer realisierten Stapel kann man Daten ablegen, um sie zu einem späteren Zeitpunkt wieder herunterzunehmen. Dabei ist der Zugriff immer auf das oberste Element des Stapels beschränkt.

Das Datum, das man zuletzt auf dem Stapel abgelegt hat, muss als erstes wieder heruntergenommen werden. Daher rührt auch die andere Bezeichnung, die für Stacks gebräuchlich ist:

LIFO-Speicher = Last In - First Out,

oder auf deutsch: Zuletzt hinein, zuerst heraus. Ganz besonders die verschiedenen Unterprogrammtechniken profitieren davon. So können in Stacks die Rücksprungs-Adressen für Die CPU Z80: Unterprogramm-AufrufeUnterprogramm-Aufrufe gespeichert, Argumente an Die Fließkomma-Routinen: FunktionenFunktionen (also: Grundlagen: UnterprogrammeUnterprogramme) übergeben und von diesen wieder übernommen und lokale Variablenbereiche realisiert werden.

Ein Stack als FLR-Array

Jede Die ICs im Überblick: Die CPU Z80
Das Innenleben der CPC-Rechner: Die CPU Z80
Die Anschlussbelegungen der wichtigsten ICs im CPC: Die CPU Z80CPU verfügt über solch einen Stapel. Bei der Die ICs im Überblick: Die CPU Z80
Das Innenleben der CPC-Rechner: Die CPU Z80
Die Anschlussbelegungen der wichtigsten ICs im CPC: Die CPU Z80Z80 können darauf normalerweise nur 2-Byte-Worte (Datenbreite: WordsWords) abgelegt werden. Alle im Stapel enthaltenen Elemente liegen direkt hintereinander. Es ist also ein Datenspeicherung und Datenstrukturen: ArraysArray aus fixed length Datenspeicherung und Datenstrukturen: Recordsrecords. Nur die Lage der Stapelspitze ist dem Prozessor bekannt. Der Stapelboden (Base), also die Speicheradresse des letzten Stapel-Elements wäre zwar auch ganz interessant, ist aber nicht so wichtig. Es ist dem Prozessor also jederzeit möglich, mehr Worte vom Stack zu lesen, als er vorher drauf abgelegt hat. Kommt so etwas tatsächlich einmal vor, kann man ziemlich sicher sein, dass im Programm ein Der Linien-Algorithmus: Fehler 3Fehler steckt.

Das laufende Programm muss sich den verfügbaren Speicherbereich aufteilen und dabei dem Stack einen Speicherbereich reservieren, der für den maximalen Bedarf, der irgendwo im Programm entstehen kann, ausreicht. Denn dem Prozessor ist nicht nur unbekannt, wo der Stapel anfängt, er weiß auch nicht, wie hoch er höchstens werden darf.

Das einzige, was der Prozessor kann, ist Daten drauflegen und wieder runterholen. Die Stelle, an der er das tut, die Stapelspitze, wird durch ein speziell dafür vorgesehenes Doppelregister, den 'Stackpointer' = SP adressiert.

Der Stapel der Die ICs im Überblick: Die CPU Z80
Das Innenleben der CPC-Rechner: Die CPU Z80
Die Anschlussbelegungen der wichtigsten ICs im CPC: Die CPU Z80Z80 hat dabei die interessante Eigenschaft, nach unten zu wachsen. Jedesmal, wenn ein neues Wort auf dem Stapel abgelegt wird, wird der Stackpointer um zwei Adressen erniedrigt. Nimmt man umgekehrt ein Datum wieder weg, wird der Stackpointer um zwei Adressen heraufgesetzt. Der Stackpointer zeigt dabei immer auf das unterste Datentypen: Bytes
Datenbreite: BytesByte (LSB=least signifcant Datentypen: Bytes
Datenbreite: BytesByte) des letzten, im Stapel enthaltenen Wortes.

Die wichtigsten Die Fließkomma-Routinen: OperationenOperationen, die den Stapel wachsen lassen, sind:

1. Die CPU Z80: Unterprogramm-AufrufeUnterprogramm-Aufrufe (Maschinencode über HIMEM: CALLCALL) und
2. Register-Speicherbefehle (PUSH).

Umgekehrt nehmen die folgenden Befehle wieder Werte vom Stapel herunter:

1. Unterprogramm-Rücksprung (RET) und
2. Register-Ladebefehle (POP).

Die genaue Z80-Relocalisitor: FunktionsweiseFunktionsweise des Stapels bei der Unterprogramm-Behandlung wird erst bei den Grundlagen: ProgrammstrukturenProgrammstrukturen behandelt.

Mit den Befehlen PUSH und POP können Register-Inhalte kurzzeitig gerettet (PUSH) und wieder restauriert werden (POP). Beispielsweise vor und nach einem Die CPU Z80: Unterprogramm-AufrufeUnterprogramm-Aufruf, der wichtige Die Tonausgabe: Das Kontrollregister (Reg. 7)
Die Tonausgabe: Die möglichen Hüllkurvenformen (Reg. 13)Register verändern könnte.

Das folgende Beispiel zeigt die Errichtung des Maschinenstapels und einige Aktionen darauf. Zuerst als Assembler-Programm und dann in den Grafiken die zugehörigen Darstellungen des Stapels selbst:

10  LD   SP,#C000  ; Stapelspitze neu setzen. Annahme: Der Stapel soll jetzt neu
                   ; und leer sein. Stapelboden ist also &C000.
20  LD   HL,#1234  ; HL-Register mit &1234 laden.
30  PUSH HL        ; &1234 auf dem Stapel ablegen.
40  LD   DE,#5678  ; DE-Register mit &5678 laden.
50  PUSH DE        ; &5678 auf dem Stapel ablegen.
60  POP  BC        ; &5678 vom Stapel holen und in's BC-Register laden.
70  POP  DE        ; &1234 vom Stapel holen und in's DE-Register laden.
80  POP  HL        ; Unterschreitung des Stapelbodens. Wert in HL unbekannt.

Adresse     LD SP,#C000    PUSH HL    PUSH DE     POP BC     POP DE     POP HL
--------------------------------------------------------------------------------
&C002   ->         &??        &??        &??        &??        &??  SP -> &??
&C001   ->         &??        &??        &??        &??        &??        &??
&C000   ->   SP -> &??        &??        &??        &??  SP -> &??        &??
&BFFF   ->         &??        &12        &12        &12        &??        &??
&BFFE   ->         &??  SP -> &34        &34  SP -> &34        &??        &??
&BFFD   ->         &??        &??        &56        &??        &??        &??
&BFFC   ->         &??        &??  SP -> &78        &??        &??        &??
&BFFB   ->         &??        &??        &??        &??        &??        &??

                                        _____
                             _____     |_____|     _____
&C000 __________._____._____|_____|____|_____|____|_____|____._____.____. ??  ._
                                                                        |_____|

Mit einem FLR-Array kann man auch sehr leicht einen Software-Stack (beispielsweise für Übergabe von Argumenten und Ergebnissen: FORTH:FORTH) realisieren. Die folgenden Assemblerprogramme zeigen eine mögliche Variante. Dieser Stack wächst nach oben, und der Stackpointer zeigt jeweils auf das erste freie Datentypen: Bytes
Datenbreite: BytesByte über der Stapelspitze:

STACKP: DEFW #0000          ; Speicher für den Software-Stackpointer
;
; PUSH    Eingabe: DE=Wert
;
STORE:  LD   HL,(STACKP)    ; Stackpointer holen
        LD   (HL),LOW KERNEL JUMPBLOCK: 000E:  LOW PCBC INSTRUCTION
LOW KERNEL JUMPBLOCK: 001E:  LOW PCHL INSTRUCTIONE         ;
        INC  HL             ; DE 'pushen':   LD (HL),DE mit postincrement
        LD   (HL),D         ;
        INC  HL             ;
        LD   (STACKP),HL    ; neuen Wert für den Stackp. wieder speichern
        RET
;
; POP     Ausgabe: DE=Wert
;
RECALL: LD   HL,(STACKP)    ; Stackpointer holen
        DEC  HL             ;
        LD   D,(HL)         ; DE 'poppen':   LD DE,(HL) mit predecrement
        DEC  HL             ;
        LD   LOW KERNEL JUMPBLOCK: 000E:  LOW PCBC INSTRUCTION
LOW KERNEL JUMPBLOCK: 001E:  LOW PCHL INSTRUCTIONE,(HL)         ;
        LD   (STACKP),HL    ; neuen Wert für den Stackp. zurückspeichern
        RET

Ein Stack als verkettete Liste

Verkettete Trees: ListenListen sind für Stacks eigentlich besonders gut geeignet, weil ja immer nur auf den ersten Datenspeicherung und Datenstrukturen: RecordsRecord zugegriffen wird. Außerdem beanspruchen leere Stacks mit dieser Methode keinen Speicherplatz. Ein neuer Datensatz wird auf dem Stack abgelegt, indem er an erster Position eingehangelt wird. Um ihn wieder herunterzunehmen, muss man ihn aus der Kette wieder ausklinken.

Solche Datenspeicherung und Datenstrukturen: ChainsChains haben dabei sogar den Vorteil, dass der Stapelboden immer markiert ist, weil man in den Pointer des letzten Datenspeicherung und Datenstrukturen: RecordsRecords des Stapels ja ein NIL eintragen kann. Ein maximal verfügbarer Bereich kann auch nicht überschritten werden, weil die Datenspeicherung und Datenstrukturen: RecordsRecords ja in keinen reservierten Bereich kopiert werden, sondern an dem Platz belassen werden, an dem sie bereits stehen. Nur ihre Pointer werden umgebogen.

Die folgende Grafik demonstriert das 'Pushen' und 'Poppen' in einer linked Trees: ListenList:

Stack leer      Push Record1     Push Record2     Pop Record2      Pop Record1
-------------   ---------------  ---------------  ---------------  -------------

SP -> NIL       SP    NIL <-+    SP    NIL <--+   SP    NIL <-+    SP -> NIL
                |           |    |            |   |           |
                |           |    |            |   |           |
   Pointer      |  Pointer  |    +->Pointer-+ |   |  Pointer  |       Pointer
   Record2      |  Record2  |       Record2 | |   |  Record2  |       Record2
                |           |               | |   |           |
                |           |    +----------+ |   |           |
                |           |    |            |   |           |
   Pointer      +->Pointer--+    +->Pointer---+   +->Pointer--+       Pointer
   Record1         Record1          Record1          Record1          Record1

Eine mögliche Realisierung eines Linked-List-Stapels in Maschinencode zeigt das folgende Programm. Es ist dabei völlig uninteressant, wie lang die einzelnen Datenspeicherung und Datenstrukturen: RecordsRecords sind und was sie enthalten. Wichtig ist nur, dass sie alle mit einem 'Pointer' anfangen:

STACKP: DEFW #0000        ; Speicher für den Stackpointer
;
; PUSH: Eingabe: HL zeigt auf das LSB des Pointers des zu pushenden Datenspeicherung und Datenstrukturen: RecordsRecords.
; --------------------------------------------------------------------------
STORE:  LD   DE,(STACKP)  ; Zeiger auf bisherigen ersten Datenspeicherung und Datenstrukturen: RecordsRecord nach DE holen.
;
        LD   (STACKP),HL  ; Zeiger auf neuen ersten Datenspeicherung und Datenstrukturen: RecordsRecord abspeichern.
;
        LD   (HL),LOW KERNEL JUMPBLOCK: 000E:  LOW PCBC INSTRUCTION
LOW KERNEL JUMPBLOCK: 001E:  LOW PCHL INSTRUCTIONE       ; Adresse des bisherigen ersten und nun zweiten
        INC  HL           ;   Datenspeicherung und Datenstrukturen: RecordsRecords in den Pointer des neuen ersten Datenspeicherung und Datenstrukturen: RecordsRecords
        LD   (HL),D       ;   eintragen.
        RET
;
;
; POP: Ausgabe: HL zeigt auf das LSB des Pointers des gepoppten Datenspeicherung und Datenstrukturen: RecordsRecords.
; ----------------------------------------------------------------------
RECALL: LD   HL,(STACKP)  ; Zeiger auf bisherigen ersten Pointer nach HL holen.
;
        LD   LOW KERNEL JUMPBLOCK: 000E:  LOW PCBC INSTRUCTION
LOW KERNEL JUMPBLOCK: 001E:  LOW PCHL INSTRUCTIONE,(HL)       ; Zeiger auf bisherigen zweiten und nun ersten
        INC  HL           ; Pointer nach DE holen.
        LD   D,(HL)
        DEC  HL           ; HL aber nicht verändern!
;
        LD   (STACKP),DE  ; Bisherigen zweiten Pointer als ersten eintragen.
        RET