DynamicArrayQueue

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.