Algorithmen und Programmierung II

Die Lösung der Aufgaben und die Abgabe der Lösungen erfolgt in Zweiergruppen!

Hinweis: Benutze die Ressourcen der ALP2 Webseite.

Aufgabe 1 (4 P.)

Welche Vor- und Nachteile hat die Speicherung von Datenelementen mit einer Reihung (=array) gegenüber der mit einer Liste?

Aufgabe 2 (8+4 = 12 P.)

1. Implementiere einen Stapel für Zeichenketten in Java. Die Daten sollen als Reihung (= array) gespeichert werden. Die Zeichenketten werden als Datentyp "String" gespeichert. Das folgende Klassengerüst gibt die zu implementierenden Methoden vor.

   public class StringStack {
   
     // ... (add needed fields here)
   
     /**
      * Constructor.
      * Parameter n defines the stack's capacity, the max No of Objects which can
      * stored in this stack.
      */
     public StringStack(int capacity) {
       // ...
     }
   
     /**
      * Removes the top element from this stack and returns it.
      * 
      */
     public String pop() {
       // ...
     }
   
     /**
      * Puts the given parameter on top of this stack.
      * 
      */
     public void push(String element) {
       // ...
     }

     /**
      * Returns true if the stack is full i.e. the number of elements in the stack 
     *  has reached the maximum capacity of the stack. Otherwise returns false.
      * 
      */
     public boolean isFull() {
       // ...
     }

     /**
      * Returns true if the stack contains no element, otherwise returns false. 
      * 
      */
     public boolean isEmpty() {
       // ...
     }  
   }

2. Schreibe ein Java Programm das ein leeren Stapel erzeugt, und ihn mit den drei Zeichenketten "Freie", "Universität", und "Berlin" füllt. Anschließend soll das Programm jede Zeichenkette aus dem Stapel entfernen und am Bildschirm ausgeben bis der Stapel wieder leer ist. Hinweis: Der "ALP2Wrapper" kann hierfür verwendet werden. 

Aufgabe 3 ( 8+4 = 12 P.)

Beim Stapel spricht man auch von einer LIFO für Last In First Out, da (analog zum Tellerstapel) das nächste aus der Datenstruktur zu entfernende Element immer das zuletzt eingefügte ist. Im Gegensatz dazu wird bei einer Warteschlange oder Queue (FIFO für First In First Out) immer das älteste Element ausgegeben/entfernt. Die Implementierung einer Queue kann nun ebenfalls auf einer Liste oder einer Reihung aufsetzten.

1. Implementiere eine generische d.h. Datentyp-unabhängige Warteschlange, bei der die Elemente in einem Array gespeichert werden. Das folgende Klassengerüst gibt die zu implementierenden Methoden  vor.

   public class Queue {
   
     // ... (add needed fields here)
   
     /**
      * Constructor.
      * Parameter n defines the queue's capacity, the max No of Objects which can
      * stored in this queue.
      */
     public Queue(int capacity) {
       // ...
     }
   
     /**
      * Removes the first element from this queue and returns it.   
      */
     public Object pop(){
       // ...
     }
   
     /**
      * Puts the given parameter at the end of this queue.
      * 
      */
     public void push(Object object)  {
       // ...
     }

   /**
      * Returns true if the queue is full i.e. the number of elements in the queue 
     *  has reached the maximum capacity of the queue. Otherwise returns false.
      * 
      */
     public boolean isFull() {
       // ...
     }

     /**
      * Returns true if the queue contains no element, otherwise returns false. 
      * 
      */
     public boolean isEmpty() {
       // ...
     }  
   }

2. Schreibe ein Java Programm das eine leere Warteschlange erzeugt, die drei Zeichenketten "Freie", "Universität", und "Berlin" darin einfügt. Anschließend soll das Programm jede Zeichenkette aus der Warteschlange entfernen und am Bildschirm ausgeben solange bis die Warteschlange wieder leer ist. Hinweis: Der "ALP2Wrapper" kann hierfür verwendet werden. 

03.06.2002