Le Tutoriel de Java PriorityQueue

PriorityQueue
Examples

1. PriorityQueue

PriorityQueue est une classe qui implémente l'interface de Queue, donc elle possède toutes les caractéristiques d'une file d'attente et prend en charge toutes les opérations de Collection facultatives. Cependant, contrairement à une file d'attente normale, les éléments d'une PriorityQueue sont triés par ordre croissant en fonction de leur ordre naturel ou selon un Comparator fourni (selon le constructeur utilisé), donc lorsqu'un nouvel élément est inséré dans PriorityQueue, il peut ne pas se situer à la dernière position.

Le Tutoriel de Java Queue

Les caractéristiques héritées de Queue:

Les éléments dupliqués sont autorisés, mais ce n'est pas le cas pour les éléments null.

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable

PriorityQueue est une file d'attente illimitée (unbounded). Les éléments sont triés par ordre croissant et les éléments dupliqués sont autorisés.

En règle générale, PriorityQueue gère un tableau d'objets (Object[]) pour stocker ses éléments. La longueur de ce tableau est supérieure au nombre d'éléments de la file d'attente. Cependant, le tableau sera remplacé par un autre tableau de plus grande longueur si nécessaire.

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)

Le constructeur PriorityQueue(int initialCapacity) crée un objet PriorityQueue avec un tableau interne de taille initialCapacity. Dans ce cas, tous les éléments de PriorityQueue doivent être de type Comparable pour se comparer entre eux, et les éléments null ne sont pas autorisés.
Le constructeur PriorityQueue(Comparator) crée un objet PriorityQueue dont la taille par défaut du tableau interne est de 11. En même temps, il est attribué d'un Comparator pour comparer les éléments entre eux.

PriorityQueue est une file d'attente asynchrone, vous ne devez donc pas l'utiliser dans un environnement multithreading, utiliser plutôt la classe thread-safe PriorityBlockingQueue.

Le Tutoriel de Java PriorityBlockingQueue

// Methods inherited from Collection:

Iterator<E> iterator()
default Spliterator<E> spliterator()

Iterator obtenu à partir de PriorityQueue prend en charge toutes les méthodes facultatives.
Iterator (ou Spliterator) obtenu à partir de PriorityQueue ne garantit pas qu'il traversera les éléments dans l'ordre de priorité. Si vous souhaitez parcourir les éléments par ordre de priorité, veuillez utiliser Arrays.sort(priorityQueue.toArray()).

Queue
Deque
ConcurrentLinkedQueue
BlockingDeque
BlockingQueue
TransferQueue
ArrayDeque
ConcurrentLinkedDeque
LinkedList
ArrayBlockingQueue
DelayQueue
LinkedBlockingQueue
LinkedBlockingDeque
PriorityBlockingQueue
SynchronousQueue
LinkedTransferQueue

2. Examples

String est un type de données auto-comparable, car il implémente une interface Comparable. Il n'est donc pas nécessaire de fournir un Comparator pour PriorityQueue<String>.

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

Par exemple : La classe Customer avec fullName, les propriétés des loyaltyPoints (Nom complet, points accumulés lors de l'achat). Les clients avec des loyaltyPoints plus élevés auront une priorité plus élevée.

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

Par exemple : Pour les éléments qui ne sont pas auto-comparables, vous devez fournir un Comparator à PriorityQueue.

Comparer et trier en Java

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

Si vous souhaitez parcourir tous les éléments d'une PriorityQueue sans les supprimer, vous pouvez utiliser Iterator ou Spliterator, mais ils ne garantissent pas l'ordre de priorité des éléments. Dans ce cas, vous devez utiliser Arrays.sort(priorityQueue.toArray()) ou Arrays.sort(priorityQueue.toArray(),comparator).

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

En règle générale, en plus des caractéristiques susmentionnées, PriorityQueue dispose de toutes les caractéristiques d'une Queue. Les méthodes de Queue et les exemples associés sont mentionnés dans l'article suivant :

Le Tutoriel de Java Queue

Le Tutoriel de Java PriorityQueue

1. PriorityQueue

2. Examples

Tutoriels de Java Collections Framework

Tutoriels de Java Collections Framework

Articles les plus récents