Package de.pakad.adt

Class RingBufferDyn<T>

java.lang.Object
de.pakad.adt.RingBufferDyn<T>
Type Parameters:
T - Typ der gespeicherten Elemente
All Implemented Interfaces:
Queue<T>
public class RingBufferDyn<T> extends Object implements Queue<T>
RingBufferDyn implementiert eine generische FIFO-Warteschlange (Queue) mithilfe eines Ringpuffers (zirkulärer Speicher) mit dynamisch wachsendem Array.

Die Elemente werden in einem Array gespeichert, das logisch zyklisch interpretiert wird. Ein Index head zeigt auf das erste Element (Kopf der Queue), und count speichert die aktuelle Anzahl enthaltener Elemente.

Im Gegensatz zu RingBuffer besitzt diese Implementierung keine feste Kapazitätsgrenze: Ist der Puffer voll, wird das interne Array automatisch vergrößert (typischerweise verdoppelt). Dabei werden die Elemente in FIFO-Reihenfolge in ein neues Array kopiert, sodass head anschließend wieder auf 0 gesetzt werden kann.

Java-Version: 17 oder höher

Author:
Karsten Brodmann (kb@punkt-akademie.de)

  • Constructor Summary

    Constructors
    Constructor
    Description
    RingBufferDyn()
    Erzeugt einen neuen RingBufferDyn mit einer Standardkapazität von 10.
    RingBufferDyn(int initialCapacity)
    Erzeugt einen neuen RingBufferDyn mit der angegebenen Anfangskapazität.

  • Method Summary

    Modifier and Type
    Method
    Description
    T
    dequeue()
    Entfernt das erste Element der Queue und liefert dessen Wert zurück.
    boolean
    empty()
    Prüft, ob die Queue leer ist.
    void
    enqueue(T obj)
    Fügt ein Element am Ende der Queue ein.
    T
    front()
    Liefert das erste Element der Queue, ohne es zu entfernen.
    boolean
    full()
    Prüft, ob der Ringpuffer aktuell vollständig belegt ist.
    int
    size()
    Liefert die Anzahl der in der Queue gespeicherten Elemente.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • RingBufferDyn

      public RingBufferDyn()
      Erzeugt einen neuen RingBufferDyn mit einer Standardkapazität von 10.

    • RingBufferDyn

      public RingBufferDyn(int initialCapacity) throws IllegalArgumentException
      Erzeugt einen neuen RingBufferDyn mit der angegebenen Anfangskapazität.

      Die Kapazität ist nach der Erzeugung nicht fix, sondern kann bei Bedarf automatisch wachsen. Als Mindestkapazität wird 10 gefordert, um kleine Arrays (und häufige Reallokationen) zu vermeiden.

      Parameters:
      initialCapacity - Anfangskapazität (mindestens 10)
      Throws:
      IllegalArgumentException - wenn initialCapacity < 10 ist

  • Method Details

    • empty

      public boolean empty()
      Prüft, ob die Queue leer ist.
      Specified by:
      empty in interface Queue<T>
      Returns:
      true, wenn keine Elemente gespeichert sind, sonst false

    • full

      public boolean full()
      Prüft, ob der Ringpuffer aktuell vollständig belegt ist.

      Hinweis: Bei RingBufferDyn ist „voll“ kein Fehlerzustand, sondern löst beim nächsten enqueue eine Vergrößerung aus.

      Returns:
      true, wenn count == capacity gilt, sonst false

    • size

      public int size()
      Liefert die Anzahl der in der Queue gespeicherten Elemente.
      Returns:
      Anzahl der Elemente

    • enqueue

      public void enqueue(T obj)
      Fügt ein Element am Ende der Queue ein.

      Ist das interne Array voll, wird es automatisch vergrößert. Die Einfügeposition ergibt sich aus (head + count) % capacity.

      Laufzeit:

      • amortisiert O(1) (durch gelegentliche Verdopplung)
      • im Vergrößerungsfall O(n) (Kopieren von n Elementen)
      Specified by:
      enqueue in interface Queue<T>
      Parameters:
      obj - einzufügendes Element

    • front

      public T front()
      Liefert das erste Element der Queue, ohne es zu entfernen.

      Laufzeit: O(1)

      Specified by:
      front in interface Queue<T>
      Returns:
      erstes Element der Queue
      Throws:
      IndexOutOfBoundsException - wenn die Queue leer ist

    • dequeue

      public T dequeue()
      Entfernt das erste Element der Queue und liefert dessen Wert zurück.

      Nach dem Entfernen wird der Kopfindex zyklisch weitergeschaltet. Die Referenz auf das entfernte Element wird explizit gelöscht, um Speicherlecks zu vermeiden.

      Laufzeit: O(1)

      Specified by:
      dequeue in interface Queue<T>
      Returns:
      entferntes erstes Element der Queue
      Throws:
      IndexOutOfBoundsException - wenn die Queue leer ist