File d'attente prioritaire Java

Dans ce didacticiel, nous allons découvrir la classe PriorityQueue du framework de collections Java à l'aide d'exemples.

Le PriorityQueue fournit la fonctionnalité de la structure de données de tas.

Il implémente l'interface Queue.

Contrairement aux files d'attente normales, les éléments de la file d'attente prioritaire sont récupérés dans un ordre trié.

Supposons que nous voulions récupérer les éléments dans l'ordre croissant. Dans ce cas, la tête de file prioritaire sera le plus petit élément. Une fois cet élément récupéré, le plus petit élément suivant sera la tête de la file d'attente.

Il est important de noter que les éléments d'une file prioritaire peuvent ne pas être triés. Cependant, les éléments sont toujours récupérés dans l'ordre trié.

Création d'une file d'attente prioritaire

Afin de créer une file d'attente prioritaire, nous devons importer le java.util.PriorityQueue forfait. Une fois le package importé, voici comment créer une file d'attente prioritaire en Java.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Ici, nous avons créé une file d'attente prioritaire sans aucun argument. Dans ce cas, la tête de la file d'attente prioritaire est le plus petit élément de la file d'attente. Et les éléments sont supprimés par ordre croissant de la file d'attente.

Cependant, nous pouvons personnaliser l'ordre des éléments à l'aide du Comparator interface. Nous en apprendrons plus tard dans ce didacticiel.

Méthodes de PriorityQueue

Le PriorityQueue La classe fournit l'implémentation de toutes les méthodes présentes dans le Queue interface.

Insérer des éléments dans PriorityQueue

add() - Insère l'élément spécifié dans la file d'attente. Si la file d'attente est pleine, elle lève une exception.
offer() - Insère l'élément spécifié dans la file d'attente. Si la file d'attente est pleine, elle renvoie false .

Par exemple,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        // Using the add() method
        numbers.add(4);
        numbers.add(2);
        System.out.println("PriorityQueue: " + numbers);

        // Using the offer() method
        numbers.offer(1);
        System.out.println("Updated PriorityQueue: " + numbers);
    }
}

Sortie

PriorityQueue: [2, 4]
Updated PriorityQueue: [1, 4, 2]

Ici, nous avons créé une file d'attente prioritaire nommée numbers . Nous avons inséré 4 et 2 dans la file d'attente.

Bien que 4 soit inséré avant 2, la tête de la file d'attente est 2. C'est parce que la tête de la file d'attente prioritaire est le plus petit élément de la file d'attente.

Nous avons ensuite inséré 1 dans la file d'attente. La file d'attente est maintenant réorganisée pour stocker le plus petit élément 1 en tête de file d'attente.

Accéder aux éléments PriorityQueue

Pour accéder aux éléments d'une file d'attente prioritaire, nous pouvons utiliser le peek() méthode. Cette méthode renvoie la tête de la file d'attente. Par exemple,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the peek() method
        int number = numbers.peek();
        System.out.println("Accessed Element: " + number);
    }
}

Sortie

PriorityQueue: [1, 4, 2]
Accessed Element: 1

Supprimer les éléments PriorityQueue

remove() - supprime l'élément spécifié de la file d'attente
poll() - renvoie et supprime la tête de la file d'attente

Par exemple,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the remove() method
        boolean result = numbers.remove(2);
        System.out.println("Is the element 2 removed? " + result);

        // Using the poll() method
        int number = numbers.poll();
        System.out.println("Removed Element Using poll(): " + number);
    }
}

Sortie

PriorityQueue: [1, 4, 2]
Is the element 2 removed? true
Removed Element Using poll(): 1

Itération sur une PriorityQueue

Pour parcourir les éléments d'une file d'attente prioritaire, nous pouvons utiliser le iterator() méthode. Pour utiliser cette méthode, nous devons importer le java.util.Iterator forfait. Par exemple,

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

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.print("PriorityQueue using iterator(): ");

        //Using the iterator() method
        Iterator<Integer> iterate = numbers.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

Sortie

PriorityQueue using iterator(): 1, 4, 2,

Autres méthodes PriorityQueue

Méthodes	Descriptions
`contains(element)`	Recherche la file d'attente prioritaire pour l'élément spécifié. Si l'élément est trouvé, il renvoie `true` , sinon il renvoie `false` .
`size()`	Renvoie la longueur de la file d'attente prioritaire.
`toArray()`	Convertit une file d'attente prioritaire en tableau et la renvoie.

Comparateur de file d'attente prioritaire

Dans tous les exemples ci-dessus, les éléments de la file d'attente prioritaire sont récupérés dans l'ordre naturel (ordre croissant). Cependant, nous pouvons personnaliser cette commande.

Pour cela, nous devons créer notre propre classe comparateur qui implémente le Comparator interface. Par exemple,

import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        numbers.add(3);
        System.out.print("PriorityQueue: " + numbers);
    }
}

class CustomComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer number1, Integer number2) {
        int value =  number1.compareTo(number2);
        // elements are sorted in reverse order
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}

Sortie

PriorityQueue: [4, 3, 1, 2]

Dans l'exemple ci-dessus, nous avons créé une file d'attente prioritaire passant CustomComparator classe comme argument.

Le CustomComparator la classe implémente le Comparator interface.

Nous remplaçons alors le compare() méthode. La méthode fait maintenant en sorte que la tête de l'élément soit le plus grand nombre.

Pour en savoir plus sur le comparateur, visitez Java Comparator.

Interface de file d'attente Java Interface Java Deque

Java