Vous utilisez une Queue lorsque les éléments sont ajoutés et supprimés dans un ordre spécifique. Vous pouvez imaginer une queue comme une file d’attente. Par exemple, lorsque vous voulez entrer dans un stade et que quelqu’un attend déjà en ligne, vous vous placez derrière cette personne. Et si vous êtes Britannique, vous vous mettez dans la queue derrière cette personne, ce qui rend cela vraiment facile à retenir ! C’est une file FIFO (premier entré, premier sorti).
Une Deque (queue à double extrémité), souvent prononcée “deck”, est différente d’une queue ordinaire en ce que vous pouvez insérer et supprimer des éléments à la fois depuis l’avant (tête) et l’arrière (queue). Imaginez : “Monsieur Martin Dupont, venez directement à l’avant ! Vous êtes le seul à bénéficier de ce traitement spécial. Tout le monde devra commencer par l’arrière de la file.”
Vous pouvez visualiser une queue à double extrémité comme illustré ci-dessous :
Avant (tête) ――→ [Médor] ―― [Spot] ―― [Belle] ←―― Arrière (queue)
Supposons que nous utilisions ceci comme une file FIFO. Médor est le premier, ce qui signifie qu’il est arrivé en premier. Belle est la dernière, ce qui signifie qu’elle est arrivée en dernier et qu’elle a le temps d’attente restant le plus long. Toutes les queues ont des exigences spécifiques pour ajouter et supprimer l’élément suivant. Au-delà de cela, elles offrent chacune des fonctionnalités différentes. Nous examinons les implémentations que vous devez connaître et les méthodes disponibles.
Comparaison des implémentations de Deque
Vous avez vu LinkedList plus tôt dans la section List. En plus d’être une liste, c’est une Deque. Le principal avantage de LinkedList est qu’elle implémente à la fois les interfaces List et Deque. Le compromis est qu’elle n’est pas aussi efficace qu’une queue “pure”. Vous pouvez utiliser la classe ArrayDeque si vous n’avez pas besoin des méthodes de List.
Travailler avec les méthodes Queue et Deque
L’interface Queue contient six méthodes, présentées dans le tableau suivant. Il y a trois types de fonctionnalités et des versions des méthodes qui lancent une exception ou utilisent le type de retour, comme null, pour toutes les informations. Nous avons mis en gras celles qui lancent une exception lorsque quelque chose ne va pas, comme essayer de lire à partir d’une Queue vide.
| Fonctionnalité | Méthodes |
|---|---|
| Ajouter à l’arrière | public boolean add(E e)public boolean offer(E e) |
| Lire depuis l’avant | public E element()public E peek() |
| Obtenir et supprimer depuis l’avant | public E remove()public E poll() |
Montrons un exemple simple de queue :
Queue<Integer> queue = new LinkedList<>();
queue.add(10);
queue.add(4);
System.out.println(queue.remove()); // 10
System.out.println(queue.peek()); // 4Les lignes d’ajout ajoutent des éléments à la queue. La ligne avec remove() demande au premier élément qui attend le plus longtemps de sortir de la queue. La ligne avec peek() vérifie la prochaine entrée dans la queue tout en la laissant en place.
Ensuite, nous passons à l’interface Deque. Comme l’interface Deque prend en charge les queues à double extrémité, elle hérite de toutes les méthodes de Queue et en ajoute d’autres pour qu’il soit clair si nous travaillons avec l’avant ou l’arrière de la queue. Le tableau suivant montre les méthodes lors de l’utilisation comme une queue à double extrémité.
| Fonctionnalité | Méthodes |
|---|---|
| Ajouter à l’avant | public void addFirst(E e)public boolean offerFirst(E e) |
| Ajouter à l’arrière | public void addLast(E e)public boolean offerLast(E e) |
| Lire depuis l’avant | public E getFirst()public E peekFirst() |
| Lire depuis l’arrière | public E getLast()public E peekLast() |
| Obtenir et supprimer depuis l’avant | public E removeFirst()public E pollFirst() |
| Obtenir et supprimer depuis l’arrière | public E removeLast()public E pollLast() |
Essayons un exemple qui fonctionne avec les deux extrémités de la queue :
Deque<Integer> deque = new LinkedList<>();
deque.offerFirst(10); // true
deque.offerLast(4); // true
deque.peekFirst(); // 10
deque.pollFirst(); // 10
deque.pollLast(); // 4
deque.pollFirst(); // null
deque.peekFirst(); // nullLes lignes d’ajout réussissent à ajouter un élément à l’avant et à l’arrière de la queue, respectivement. Certaines queues ont une taille limitée, ce qui provoquerait l’échec de l’offre d’un élément à la queue. La ligne suivante regarde le premier élément de la queue, mais ne le supprime pas. Les lignes suivantes suppriment les éléments de la queue, un de chaque extrémité. Cela donne une queue vide. Les dernières lignes essaient de regarder le premier élément de la queue, ce qui donne null.
Utiliser une Deque comme une pile
En plus des queues FIFO, il existe des queues LIFO (dernier entré, premier sorti), communément appelées piles (stacks). Imaginez une pile d’assiettes. Vous ajoutez toujours ou retirez toujours du haut de la pile pour éviter un désordre. Heureusement, nous pouvons utiliser les mêmes implémentations de queue à double extrémité. Des méthodes différentes sont utilisées pour plus de clarté, comme indiqué dans le tableau suivant.
| Fonctionnalité | Méthodes |
|---|---|
| Ajouter à l’avant/haut | public void push(E e) |
| Supprimer depuis l’avant/haut | public E pop() |
| Obtenir le premier élément | public E peek() |
Essayons un autre exemple en utilisant la Deque comme une pile :
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(4);
stack.peek(); // 4
stack.poll(); // 4
stack.poll(); // 10
stack.peek(); // nullLes lignes d’ajout placent avec succès un élément sur l’avant/haut de la pile. Le reste du code examine également l’avant.
Lors de l’utilisation d’une Deque, il est vraiment important de déterminer si elle est utilisée comme une queue FIFO, une pile LIFO ou une queue à double extrémité. Pour résumer, une queue FIFO est comme une file de personnes. Vous entrez par l’arrière et sortez par l’avant. Une pile LIFO est comme une pile d’assiettes. Vous mettez l’assiette sur le dessus et la retirez du dessus. Une queue à double extrémité utilise les deux extrémités.