Package de.pakad.adt

Class PriorityQueueWithPrio<T>

java.lang.Object
de.pakad.adt.PriorityQueueWithPrio<T>
Type Parameters:
T - Typ der gespeicherten Elemente
All Implemented Interfaces:
Queue<T>
public class PriorityQueueWithPrio<T> extends Object implements Queue<T>
PriorityQueueWithPrio implementiert eine Prioritätswarteschlange (Queue), bei der die Priorität der Elemente explizit beim Einfügen angegeben wird.

Die Reihenfolge der Abarbeitung richtet sich primär nach der Priorität der Elemente und sekundär nach der Einfügereihenfolge (FIFO bei gleicher Priorität).

Intern wird ein binärer Heap verwendet, dessen Ordnung durch einen Comparator festgelegt wird.

Java-Version: 17 oder höher

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

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    PriorityQueueWithPrio.Order
    Definiert die Prioritätsordnung der Queue.

  • Constructor Summary

    Constructors
    Constructor
    Description
    PriorityQueueWithPrio(int initialCapacity)
    Erzeugt eine leere Prioritätswarteschlange mit der angegebenen Anfangskapazität.
    PriorityQueueWithPrio(PriorityQueueWithPrio.Order order, int initialCapacity)
    Erzeugt eine leere Prioritätswarteschlange mit der angegebenen Prioritätsordnung und Anfangskapazität.

  • Method Summary

    Modifier and Type
    Method
    Description
    T
    dequeue()
    Entfernt das Element mit der höchsten Priorität und liefert dessen Wert zurück.
    boolean
    empty()
    Prüft, ob die Prioritätswarteschlange leer ist.
    void
    enqueue(T obj)
    Fügt ein Element mit der Standardpriorität 0 in die Prioritätswarteschlange ein.
    void
    enqueue(T value, int priority)
    Fügt ein Element mit der angegebenen Priorität in die Prioritätswarteschlange ein.
    T
    front()
    Liefert das Element mit der höchsten Priorität, ohne es zu entfernen.
    int
    size()
    Liefert die Anzahl der in der Prioritätswarteschlange gespeicherten Elemente.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • PriorityQueueWithPrio

      public PriorityQueueWithPrio(int initialCapacity)
      Erzeugt eine leere Prioritätswarteschlange mit der angegebenen Anfangskapazität.

      Es gilt die Standardordnung PriorityQueueWithPrio.Order.MIN_PRIORITY_FIRST.

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

    • PriorityQueueWithPrio

      public PriorityQueueWithPrio(PriorityQueueWithPrio.Order order, int initialCapacity)
      Erzeugt eine leere Prioritätswarteschlange mit der angegebenen Prioritätsordnung und Anfangskapazität.
      Parameters:
      order - Prioritätsordnung
      initialCapacity - Anfangskapazität (mindestens 10)
      Throws:
      IllegalArgumentException - wenn initialCapacity < 10 ist

  • Method Details

    • enqueue

      public void enqueue(T value, int priority)
      Fügt ein Element mit der angegebenen Priorität in die Prioritätswarteschlange ein.

      Laufzeit: O(log n)

      Parameters:
      value - einzufügendes Element
      priority - Priorität des Elements
      Throws:
      NullPointerException - wenn value == null ist

    • enqueue

      public void enqueue(T obj)
      Fügt ein Element mit der Standardpriorität 0 in die Prioritätswarteschlange ein.

      Hinweis: Diese Methode dient der Kompatibilität mit dem Queue-Interface. Für eine sinnvolle Nutzung der Prioritätswarteschlange sollte bevorzugt enqueue(Object, int) verwendet werden.

      Laufzeit: O(log n)

      Specified by:
      enqueue in interface Queue<T>
      Parameters:
      obj - einzufügendes Element

    • front

      public T front()
      Liefert das Element mit der höchsten Priorität, ohne es zu entfernen.

      Laufzeit: O(1)

      Specified by:
      front in interface Queue<T>
      Returns:
      Element mit der höchsten Priorität
      Throws:
      NoSuchElementException - wenn die Queue leer ist

    • dequeue

      public T dequeue()
      Entfernt das Element mit der höchsten Priorität und liefert dessen Wert zurück.

      Laufzeit: O(log n)

      Specified by:
      dequeue in interface Queue<T>
      Returns:
      entferntes Element mit der höchsten Priorität
      Throws:
      NoSuchElementException - wenn die Queue leer ist

    • empty

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

    • size

      public int size()
      Liefert die Anzahl der in der Prioritätswarteschlange gespeicherten Elemente.
      Returns:
      Anzahl der Elemente