Sektion Angewandte Informationsverarbeitung

Übungen zu Programmieren II, Sommersemester 1996

Blatt 15, 15 Punkte

Abgabe: Donnerstag, den 23.05.1996

Aufgabe 19

• Implementieren Sie einen Stack (Kellerspeicher). Bei einer Struktur vom Typ Stack erfolgt der Zugriff nach dem Prinzip Last-In-First-Out (LIFO). Folgende Operationen sind für den Stack zur Verfügung zu stellen.

  a) Erzeugen eines leeren Stacks (Create)
  b) Hinzufügen eines Elements (Push)
  c) Entfernen eines Elements (Pop)
  d) Lesen des "obersten" Elements (Top)
  

  Realisieren Sie ein Modul Stack mit den o.g. Funktionen und einer Funktion IsEmpty. Das Modul sollte den Typ Stack zur Verfügung stellen (hidden type). In den Stack sollen Elemente vom Typ Item aus einem Modul Item eingestellt werden können. Die Implementierung ist also wieder unabhängig vom Typ der Elemente, die eingestellt werden.

  Der Erfolg der Funktionen Push, Pop und Top soll über eine Variable Done aus dem Modul Stack geprüft werden können.

• Implementieren Sie eine Queue (Warteschlange). Bei einer Struktur vom Typ Queue erfolgt der Zugriff nach dem Prinzip First-In-First-Out (FIFO). Folgende Operationen sind für die Queue zur Verfügung zu stellen:

  a) Erzeugen einer leeren Queue (Create)
  b) Hinzufügen eines Elements (Add)
  c) Entfernen eines Elements (Remove)
  

  Implementieren Sie analog zu Teilaufgabe a) ein Modul Queue, welches o.g. Funktionen, eine Funktion IsEmpty, sowie den Typ Queue und eine Variable Done zur Verfügung stellt.

• Implementieren Sie eine Queue als eine zirkulär verkettete Liste. Stellen Sie für die Queue die gleichen Funktionen wie in Teilaufgabe b) zur Verfügung.

Hinweis:
In den drei Teilaufgaben wird darüber hinaus eine Funktion Dispose benötigt, die den jeweils in Anspruch genommenen Speicherplatz vor Programmende wieder freigibt.