Queues mit dynamisch allokierten Arrays
Die Klasse DynamicArrayQueue soll analog zu ArrayStack (siehe Videos) ein Array als interne Datenstruktur verwenden. Da es sich um eine Queue handelt, soll aber das FIFO-Prinzip, nicht das LIFO Prinzip, umgesetzt werden.
- Implementieren Sie die Klasse DynamicArrayQueue. Verwenden Sie dynamische Allokation, um Überläufe zu vermeiden. Das interne Array soll inital die Größe init_capacity besitzen und bei Bedarf dynamisch um einen Faktor resize_factor erweitert werden. Tipp: Mit java.lang.System.arraycopy() kann man Werte zwischen Arrays kopieren.
- Verwenden Sie zwei Variablen start und end, die auf das erste und letzte Element der Queue zeigen. Ist die Queue leer, soll gelten start=end=-1.
- Geben Sie die Worst Case - Komplexität Ihrer Methoden push(), pop() und top() an.
package de.hsrm.ads;
import java.util.NoSuchElementException;
public class DynamicArrayQueue<T> {
T[] a;
int start,end;
public DynamicArrayQueue(int init_capacity,
double resize_factor) {
a = (T[]) new Object[init_capacity];
// FIXME: implement
}
public void push(T e) {
// FIXME: implement
}
public boolean isEmpty() {
// FIXME: implement
}
public T top() throws NoSuchElementException {
// FIXME: implement
}
public void pop() throws NoSuchElementException {
// FIXME: implement
}
}
Subato
