Algorithmen und Programmierung II

Aufgabe 1 (6 P.)

In der Vorlesung wurde ein Stack mit Hilfe einer Liste implementiert. Man kann statt der Liste aber auch ein Array zum Abspeichern der Daten verwenden.

1. Implementiere einen Stack mit Hilfe von Arrays. Das folgende Schema gibt die zu implementierenden Methoden und den Konstruktor sowie die zu definierenden Exceptions vor.

   public class Stack {
   
     // ... (add needed fields here)
   
     /**
      * Constructor.
      * Parameter n defines the stack's capacity, the max No of Objects which can
      * stored in this stack.
      */
     public Stack(int n) {
       // ...
     }
   
     /**
      * Removes the top element from this stack and returns it.
      * Throws a StackUnderflowException iff this Stack is empty.
      */
     public Object pop() throws StackUnderflowException {
       // ...
     }
   
     /**
      * Puts the given parameter on top of this stack.
      * Throws a StackOverflowException iff this Stack is already full
      * (i.e. there are capacity elements in this stack, where capacity was
      * defined in the constructor call).
      */
     public void push(Object object) throws StackOverflowException {
       // ...
     }
   
     /**
      * A small testing routine which constructs a stack and does a few push and
      * pop operations, printing the results.
      */
      public static void main(String[] argv) {
        // ...
     }
   }
   

2. Welche Vor- und Nachteile hat die Implemenations eines Stacks mit einem Array gegenüber der mit einer Liste?

Aufgabe 2 (6 P.)

Beim Stack spricht man auch von einer LIFO für Last In First Out, da (analog zum Tellerstapel) das nächste aus der Datenstruktur zu entfernende Objekt 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 einem Array aufsetzten.

Implementiere eine Queue, bei der die Elemente in einem Array gespeichert werden:

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 n) {
    // ...
  }

  /**
   * Removes the first element from this queue and returns it.
   * Throws a QueueUnderflowException iff this Queue is empty.
   */
  public Object pop() throws QueueUnderflowException {
    // ...
  }

  /**
   * Puts the given parameter at the end of this queue.
   * Throws a QueueOverflowException iff the Queue is already full
   * (i.e. there are capacity elements in this queue, where capacity was
   * defined in the constructor call).
   */
  public void push(Object object) throws QueueOverflowException {
    // ...
  }

  /**
   * A small testing routine which constructs a queue and does a few push
   * and pop operations, printing the results.
   */
   public static void main(String[] argv) {
     // ...
  }
}

Aufgabe 3 (4 P.)

Schreibe eine Klasse mit einer rekursiven Java-Methode

public static String getBinaryString(int n)

welche den String der Dualdarstellung des Parameter ausgibt, z.B. "-1011" bei dem Aufruf getBinaryString(-11). Schreibe dazu auch eine main-Routine, die getBinaryString mit (mindestens) den Testwerten -16384, -54, -27, -7, 0, 1, 7, 27, 54, 16383 testet und die Werte auf der Kommandozeile ausgibt.