File d'attente

Pour la plupart des gens, le mot "file d'attente" évoque très peu d'associations agréables. Mais aujourd'hui, nous parlons de files d'attente différentes - les files d'attente Java. En Java, une file d'attente est tout ce qui hérite de l' interface Queue , qui à son tour étend l' interface Collection . Cela signifie que les files d'attente peuvent être traitées comme des collections.

Les files d'attente en Java prennent en charge deux principes de fonctionnement : FIFO et LIFO .

Le principe FIFO (First In, First Out) régit une file d'attente régulière — le premier élément ajouté à la file d'attente est le premier à en sortir.

Le principe LIFO (Last In, First Out) décrit le comportement d'une pile — le dernier élément ajouté à la file d'attente est le premier à la quitter. Par exemple, voici comment vous travaillez avec un jeu de cartes : vous retirez les cartes du dessus une par une jusqu'à ce que vous atteigniez le bas du jeu.

La hiérarchie des files d'attente en Java ressemble à ceci :

Ici, vous pouvez voir que Queue a 3 classes d'implémentation : LinkedList , ArrayDeque et PriorityQueue . LinkedList et ArrayDeque héritent directement non pas de Queue , mais de Deque .

Deque est une interface qui a été ajoutée dans Java 6. Elle comprend plusieurs méthodes utiles pour les files d'attente et permet à une file d'attente de fonctionner comme une file d'attente à double extrémité (ou bidirectionnelle). Cela signifie qu'il peut êtreFIFOetLIFO.

L'un des deux descendants de l' interface Deque est ArrayDeque . Il prend en charge une file d'attente à double extrémité qui vous permet d'insérer et de supprimer des éléments des deux extrémités. C'est aussi un tableau dynamique dont la taille augmente automatiquement.

Il existe également une classe PriorityQueue , qui est un descendant direct de Queue : elle se comporte différemment des classes qui implémentent Deque .

PriorityQueue est une file d'attente prioritaire qui organise les éléments selon leur ordre naturel par défaut. Ici, le tri utilise lesinterfaces Comparable et Comparator . Le principe est le même qu'avec TreeSet ou TreeMap — des classes qui utilisent l' interface Comparable et ont leur propre ordre de tri.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Si vous exécutez cet exemple, voici ce que vous verrez dans la console :

Comme nous travaillons avec des files d'attente et non avec des collections régulières, nous devons supprimer les éléments de la liste. Pour ce faire, nous utilisons cette construction :

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

L' interface Deque hérite des méthodes Queue et ajoute plusieurs de ses propres méthodes intéressantes :

Voyons maintenant quelques-unes de ces méthodes dans la pratique.

Commençons par ajouter un élément à une file d'attente :

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
  
        System.out.println(deque);
    

Maintenant, récupérons les valeurs d'une file d'attente :

	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The first element is: "+ deque.getFirst());
                          
        System.out.println("The last element is: " + deque.getLast());
                          
    }
    

Ce code affiche le premier et le dernier élément de la file d'attente.

         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);
    

En exécutant ce code, nous obtenons :

La différence entre pop() et poll() est que pop() lèvera une NoSuchElementException si la liste est une liste vide, mais poll() renverra null .

Considérons maintenant les méthodes pollFirst() et pollLast() .

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);
    

Les deux méthodes renvoient et suppriment une valeur de la file d'attente.

Voici un exemple d'utilisation des méthodes peekFirst() et peekLast() :

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);
    

Les deux méthodes renvoient le premier/dernier élément de la file d'attente et ne les suppriment pas. Si la file d'attente est vide, null sera retourné.

Bien joué! Aujourd'hui, nous avons appris à travailler avec des files d'attente en Java. Vous savez maintenant comment les utiliser dans la pratique.