Schlange und Stapel (abstrakt)

In der Informatik stellen Schlangen und Stapel abstrakte Datentypen dar.

Eine Schlange ist eine lineare Verkettung von Datensätzen,
wobei gilt:
Ein Datensatz kann nur am Ende der Schlange angefügt
und am Anfang der Schlange entnommen werden.
Es gilt das Prinzip: First in First out     FiFo
Ein Stapel ist eine lineare Verkettung von Datensätzen,
wobei gilt:
Ein Datensatz kann nur am Ende des Stapels angefügt
und am Ende des Stapels entnommen werden.
Es gilt das Prinzip: Last in First out     LiFo

Die parallele und die seriellen Schnittstellen am Computer
arbeiten nach dem Schlangenprinzip. Vom Computer zum
Drucker, von der Maus bzw. Tastatur zum Computer 
werden die Daten durch die Schnittstellen geschickt und
dort gepuffert.
Die rekursiven Aufrufe eines Unterprogramms werden in
einem Stack nach dem Stapelprinzip registriert. So wird
immer nur das im Stack ganz oben liegende, also zuletzt
geöffnete Unterprogramm geschlossen und dessen
Registrierung aus dem Stack entfernt.

Sollen die abstrakten Datentypen Schlange und Stapel in Programmen verwendet werden, müssen sie durch in der Programmiersprache
vorhandene Datentypen ersetzt werden.
Die Programmiersprache PASCAL bietet dazu die Datentypen ZEIGER (Pointer) oder FELD (Array).
Der Datentyp Zeiger hat den Vorteil, daß sich auch große Datenmengen damit bearbeiten lassen.
Außerdem muß die Größe der Datenmenge vor dem Programmstart nicht feststehen. Es wird also kein Arbeitsspeicher sinnlos reserviert.
Der Datentyp Feld dagegen läßt sich leichter programmieren.


Die Arbeit mit Schlange oder Stapel läßt sich in 3 Grundaufgaben zerlegen.

1.  Initialisieren der Schlange bzw. des Stapels
2. Anhängen eines Datensatzes
3  Abhängen eines Datensatzes


Inhaltsverzeichnis      nächste Seite