Die abstrakten Datentypen Stack und PriorityQueue

Die abstrakten Datentypen Stack und PriorityQueue
Stack (auch Stapel oder Kellerspeicher)
(Quelle: Duden Informatik, Dudenverlag 1993)
Prinzip: Last in First out, LiFo („wer zuletzt kommt, darf als erster gehen“)
Definition: Eine Datenstruktur heißt Stapel, wenn Elemente nur an einem Ende, der Stapelspitze
(top), hinzugefügt oder entfernt werden können. Für Stapel sind die folgenden Operationen definiert:
1. Erzeugen eines leeren Stapels (4UBDLTUBQFMOFX4UBDL
)
2. Hinzufügen eines Elements (pusI
)
3. Prüfung, ob ein gegebener Stapel leer ist (emptZ
)
4. Inspizieren der Stapelspitze (QFFL
)
5. Entfernen vom Stapel und Rückgabe der Stapelspitze (poQ
)
Anwendungen:
Auswerten von Rechenausdrücken, syntaktische Analyse von Programmen, Bau von Übersetzern;
Undo, Aufrufen von Unterprogrammen, Tiefensuche in Graphen
PriorityQueue (Prioritätenwarteschlange)
(Quelle: Duden Informatik, Dudenverlag 1993)
Prinzip: Zugänge sortieren sich ein (klassisch: First in First out, FiFo, „wer zuerst kommt, malt zuerst“)
Definition: Eine Datenstruktur heißt Prioritätenschlange, wenn Elemente nur von einem Ende (Ende der
Schlange) eingefügt, sortiert werden und am anderen Ende (Kopf der Schlange) entfernt werden können.
Für Schlangen sind die folgenden fünf Operationen definiert:
1. Erzeugen einer leeren Schlange (1SJPSJUZ2VFVFTDIMBOHFOFX1SJPSJUZ2VFVF
)
2. Einfügen eines Elements in eine gegebene Schlange (BEE
)
3. Prüfung, ob die Schlange leer ist (is&mptZ
)
4. Inspizieren des Schlangenkopfes (QFFL
)
5. Entfernen und Rückgabe des Schlangenkopfes (QPMM
)
Anwendungen:
Druckaufträge (Druckerwarteschlange), Verwaltung von Prozessaufrufen im Betriebssystem,
Hardwareschnittstellen zur seriellen Ein-/Ausgabe (Pufferspeicher z.B. Tastatur)

Download Report