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 :
John
Andrew
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 :
void addFirst(E obj) | Ajoute l' élément obj au début de la file d'attente |
void addLast(Å obj) | Ajoute l' élément obj à la fin de la file d'attente |
E getFirst() | Renvoie le premier élément de la file d'attente |
E getLast() | Renvoie le dernier élément de la file d'attente |
boolean offerFirst(E obj) | Ajoute l' élément obj au début de la file d'attente et renvoie true si l'élément est ajouté. Sinon, renvoie false . |
booléen offreLast(E obj) | Ajoute l' élément obj à la fin de la file d'attente et renvoie true si l'élément est ajouté. Sinon, renvoie false . |
E pop() | Obtient le premier élément de la file d'attente et le supprime |
void push(E obj) | Ajoute l' élément obj au début de la file d'attente |
E peekFirst() | Renvoie (mais ne supprime pas) le premier élément de la file d'attente |
E peekLast() | Renvoie (mais ne supprime pas) le dernier élément de la file d'attente |
E pollFirst() | Renvoie et supprime le premier élément de la file d'attente. Renvoie null s'il n'y a pas d'éléments. |
E pollLast() | Renvoie et supprime le dernier élément de la file d'attente. Renvoie null s'il n'y a pas d'éléments. |
E supprimerDernier() | Renvoie et supprime le premier élément de la file d'attente. Lève une exception s'il n'y a aucun élément. |
E supprimerPremier() | Renvoie et supprime le dernier élément de la file d'attente. Lève une exception s'il n'y a aucun élément. |
booléen removeFirstOccurrence(Object obj) | Supprime la première occurrence de obj de la file d'attente |
booléen removeLastOccurrence(Object obj) | Supprime la dernière occurrence de obj de la file d'attente |
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.
Le dernier élément est : Ananas
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 :
Pomme Orange
[Ananas, Citron]
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);
Citron
[Pomme, Ananas]
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);
Le dernier élément est : Oliver
[John, Rob, Greg, Max, Oliver]
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.
GO TO FULL VERSION