codestory

Die Anleitung zu Java PriorityQueue

  1. PriorityQueue
  2. Examples

1. PriorityQueue

PriorityQueue ist eine Klasse, die die Interface Queue implementiert, also alle Merkmale einer Warteschlange hat und alle optionalen Operation von Collection unterstützt. Im Gegensatz zu einer regulären Warteschlange werden die Elemente einer PriorityQueue jedoch in aufsteigender Reihenfolge basierend auf ihrer natürlichen Reihenfolge oder nach einem bereitgestellten Comparator (je nach verwendetem Konstruktor).Deshalb wenn ein neues Element zu PriorityQueue hinzugefügt wird, kann es in die letzte Stellung platzieren.
Von Queue übernommene Merkmale:
  • Doppelte Elemente sind zulässig, aber die Elemente null sind nicht zulässig.
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable
PriorityQueue ist eine unbegrenzte Warteschlange (unbounded). Die Elemente werden in aufsteigende Reihenfolge sortiert und die doppelten Elemente sind erlaubt.
Grundsätzlich verwaltet PriorityQueue ein Array von Objekten (Object[]), um seine Elemente zu speichern. Die Länge dieses Arrays ist größer als die Anzahl der Elemente der Warteschlange. Das Array wird jedoch bei Bedarf durch ein anderes Array mit größerer Länge ersetzt.
PriorityQueue constructors
PriorityQueue()    

PriorityQueue​(int initialCapacity)    

PriorityQueue​(int initialCapacity, Comparator<? super E> comparator)    

PriorityQueue​(Collection<? extends E> c)    

PriorityQueue​(Comparator<? super E> comparator)    

PriorityQueue​(PriorityQueue<? extends E> c)    

PriorityQueue​(SortedSet<? extends E> c)
  • Der Constructor PriorityQueue(int initialCapacity) erstellt ein Objekt PriorityQueue mit einem internen Array in die Größe von initialCapacity. In diesem Fall müssen alle Elemente von PriorityQueue vom Typ Comparable sein, um sich selbst vergleichen zu können, und das Element null sind nicht zulässig.
  • Der Constructor PriorityQueue(Comparator) erstellt ein Objekt PriorityQueue mit der standardmäßigen internen Array-Größe von 11. Gleichzeitig wird ihm ein Comparator zum Vergleichen von Elementen bereitgestellt.
PriorityQueue ist eine asynchrone Warteschlange, daher sollten Sie sie nicht in einer Umgebung Multithreading verwenden, sondern stattdessen die threadsichere Klasse (thread-safe) PriorityBlockingQueue.
// Methods inherited from Collection:

Iterator<E> iterator()
default Spliterator<E> spliterator()
  • Der von PriorityQueue erhaltene Iterator unterstützt alle optionalen Methoden
  • Der von PriorityQueue erhaltene Iterator (oder Spliterator) garantiert nicht, dass er die Elemente in der Prioritätsreihenfolge durchläuft. Wenn Sie die Elemente in der Reihenfolge ihrer Priorität durchlaufen möchten, sollten Sie Arrays.sort(priorityQueue.toArray()) verwenden.

2. Examples

String ist ein selbstvergleichbarer Datentyp, da er die Interface Comparable implementiert. Es ist also nicht erforderlich, einen Comparator für PriorityQueue<String> bereitzustellen.
PriorityQueueEx1.java
package org.o7planning.priorityqueue.ex;

import java.util.PriorityQueue;

public class PriorityQueueEx1 {

    public static void main(String[] args) {  
        PriorityQueue<String> queue = new PriorityQueue<>();

        queue.add("F");
        queue.add("D");
        queue.add("B");
        queue.add("A");
        queue.add("C");

        String s = null;
        
        // Retrieves and removes the head of this queue
        while((s = queue.poll())!= null)  {
            System.out.println(s);
        }
    }
}
Output:
A
B
C
D
F
Zum Beispiel: Die Klasse Customer mit Property fullName, loyaltyPoints (Vollständiger Name, gesammelte Punkte beim Kauf). Die Kunden mit höheren loyaltyPoints erhalten eine höhere Priorität.
Customer.java
package org.o7planning.beans;

public class Customer implements Comparable<Customer> {
    private String fullName;
    private int loyaltyPoints;

    public Customer(String fullName, int pointOfPurchase) { //
        this.fullName = fullName;
        this.loyaltyPoints = pointOfPurchase;
    }

    public String getFullName() {
        return fullName;
    }

    public int getLoyaltyPoints() {
        return loyaltyPoints;
    }

    @Override
    public int compareTo(Customer other) {
        if (other == null) {
            return -1; // this < other
        }
        int delta = this.loyaltyPoints - other.loyaltyPoints;
        if (delta != 0) {
            return - delta;
        }  
        return this.fullName.compareTo(other.fullName);
    }
}
PriorityQueueEx2.java
package org.o7planning.priorityqueue.ex;

import java.util.PriorityQueue;

import org.o7planning.beans.Customer;

public class PriorityQueueEx2 {

    public static void main(String[] args) {
        Customer tom = new Customer("Tom", 200);
        Customer jerry = new Customer("Jerry", 50);
        Customer donald = new Customer("Donald", 300);
        Customer mickey = new Customer("Mickey", 30);
        Customer daffy = new Customer("Daffy", 500);
        
        PriorityQueue<Customer> queue = new PriorityQueue<>();
        
        queue.add(tom);
        queue.add(jerry);
        queue.add(donald);
        queue.add(mickey);
        queue.add(daffy);
        
        Customer currentCustomer = null;
        
        while((currentCustomer = queue.poll())!= null) { // Retrieves and removes
            System.out.println("--- Serving customer: " + currentCustomer.getFullName() + " ---");
            System.out.println("   >> Loyalty Points: " + currentCustomer.getLoyaltyPoints());
            System.out.println();
        }
    }
}
Output:
--- Serving customer: Daffy ---
   >> Loyalty Points: 500

--- Serving customer: Donald ---
   >> Loyalty Points: 300

--- Serving customer: Tom ---
   >> Loyalty Points: 200

--- Serving customer: Jerry ---
   >> Loyalty Points: 50

--- Serving customer: Mickey ---
   >> Loyalty Points: 30
Beispiel: Für Elemente, die nicht selbstvergleichbar sind, müssen Sie einen Comparator für die PriorityQueue bereitstellen.
PriorityQueueEx3.java
package org.o7planning.priorityqueue.ex;

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueEx3 {

    public static void main(String[] args) {

        Employee tom = new Employee("Tom", 2000);
        Employee jerry = new Employee("Jerry", 500);
        Employee donald = new Employee("Donald", 3000);
        Employee mickey = new Employee("Mickey", 2000);
        Employee daffy = new Employee("Daffy", 5000);

        PriorityQueue<Employee> queue = new PriorityQueue<>(new EmployeeComparator());

        queue.add(tom);
        queue.add(jerry);
        queue.add(donald);
        queue.add(mickey);
        queue.add(daffy);

        Employee currentEmployee = null;

        while ((currentEmployee = queue.poll()) != null) { // Retrieves and removes
            System.out.println("--- Serving employee: " + currentEmployee.getFullName() + " ---");
            System.out.println("   >> Salary: " + currentEmployee.getSalary());
            System.out.println();
        }
    }
}

class Employee {
    private String fullName;
    private int salary;

    public Employee(String fullName, int salary) {
        this.fullName = fullName;
        this.salary = salary;
    }

    public String getFullName() {
        return fullName;
    }

    public int getSalary() {
        return salary;
    }
}

class EmployeeComparator implements Comparator<Employee> {

    @Override
    public int compare(Employee o1, Employee o2) {
        if (o1 == o2) {
            return 0;
        }
        if (o1 == null) {
            return -1; // o1 < o2
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        int s = o1.getSalary() - o2.getSalary();
        if (s != 0) {
            return s;
        }
        return o1.getFullName().compareTo(o2.getFullName());
    }
}
Output:
--- Serving employee: Jerry ---
   >> Salary: 500

--- Serving employee: Mickey ---
   >> Salary: 2000

--- Serving employee: Tom ---
   >> Salary: 2000

--- Serving employee: Donald ---
   >> Salary: 3000

--- Serving employee: Daffy ---
   >> Salary: 5000
Wenn Sie alle Elemente einer PriorityQueue durchlaufen möchten, ohne sie zu entfernen, können Sie Iterator oder Spliterator verwenden, aber sie garantieren nicht die Prioritätsreihenfolge der Elemente. In diesem Fall sollten Sie Arrays.sort(priorityQueue.toArray()) oder Arrays.sort(priorityQueue.toArray(),comparator) verwenden.
PriorityQueueEx4.java
package org.o7planning.priorityqueue.ex;

import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;

public class PriorityQueueEx4 {

    public static void main(String[] args) {

        PriorityQueue<String> queue = new PriorityQueue<>();

        queue.add("F");
        queue.add("D");
        queue.add("B");
        queue.add("A");
        queue.add("C");

        System.out.println("--- Using Iterator: ---");
        
        Iterator<String> ite = queue.iterator();
        
        while(ite.hasNext()) {
            String e = ite.next();
            System.out.println(e);
        }
        System.out.println("--- Using Arrays.sort(queue.toArray()): ----");
        
        String[] array = new String[queue.size()];
        queue.toArray(array);
        
        Arrays.sort(array);
        
        for(String e: array) {
            System.out.println(e);
        }
    }
}
Output:
--- Using Iterator: ---
A
B
D
F
C
--- Using Arrays.sort(queue.toArray()): ----
A
B
C
D
F
Grundsätzlich besitzt PriorityQueue neben den oben genannten Eigenschaften alle Eigenschaften einer Queue. Die Methoden und verwandte Beispiele über Queue werden im folgenden Artikel erwähnt:

Die Anleitungen Java Collections Framework

Show More

Neueste Artikel

Show More