Queue, Deque, Stack : travailler avec les files et les piles

1. Interface Queue : file classique (FIFO)

En programmation, comme dans la vie, il arrive qu’il ne suffise pas de stocker un ensemble d’éléments, mais qu’il faille gérer l’ordre de leur traitement. Imaginez une file au supermarché : plus on est proche du début, plus on est servi tôt. C’est le principe FIFO — « premier arrivé — premier servi ». En revanche, une pile d’assiettes dans un placard fonctionne selon le principe LIFO — « dernier arrivé — premier sorti ». En Java, ces principes correspondent à des collections : les files Queue, les files à deux extrémités Deque et les piles Stack.

Où c’est utilisé :

• Traitement des tâches dans l’ordre d’arrivée (file de tâches, impression de documents, traitement d’événements).
• Mise en œuvre de l’annulation des actions (undo/redo) — pile.
• Analyse d’expressions, parcours d’arbres et de graphes (parcours en largeur/profondeur) et bien d’autres.

Qu’est-ce qu’une file ?

Une file (Queue) est une collection basée sur le principe FIFO. Les éléments sont ajoutés à la fin et extraits du début. Comme au magasin : qui arrive en premier est servi en premier.

Méthodes de base de l’interface Queue

offer(e)

add(e)

poll()

remove()

peek()

element()

Vous aurez remarqué des paires de méthodes au comportement similaire. La différence est dans la « douceur » : offer, poll, peek renvoient une valeur spéciale en cas d’échec (généralement null ou false) et ne lancent pas d’exceptions, alors que add, remove, element lancent des exceptions dans les situations limites (file vide, parfois débordement).

Exemple : file de tâches

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Se brosser les dents");
        tasks.offer("Faire des exercices");
        tasks.offer("Boire un café");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // On prend une tâche depuis le début de la file
            System.out.println("J'exécute: " + task);
        }
    }
}

Sortie :

J'exécute: Se brosser les dents
J'exécute: Faire des exercices
J'exécute: Boire un café

Pourquoi utilise-t-on le plus souvent LinkedList ?

Une interface est un contrat, et il existe plusieurs implémentations. On utilise souvent LinkedList car elle ajoute/supprime rapidement aux deux extrémités. Cependant, une excellente alternative est ArrayDeque. Il existe aussi des variantes spécialisées : PriorityQueue (file par priorités), voir plus bas.

2. Interface Deque : file à deux extrémités

Deque (Double Ended Queue, « dek ») est une file où l’on peut ajouter et supprimer des éléments des deux côtés : depuis le début et depuis la fin. Comme un bus à deux portes : on peut entrer/sortir de n’importe quel côté.

Deque = un outil polyvalent : peut fonctionner comme une file (FIFO), comme une pile (LIFO) et comme un hybride.

Méthodes de base de l’interface Deque

addFirst(e)

queue.addFirst("A")

addLast(e)

queue.addLast("B")

removeFirst()

queue.removeFirst()

removeLast()

queue.removeLast()

peekFirst()

queue.peekFirst()

peekLast()

queue.peekLast()

offerFirst(e)

queue.offerFirst("C")

offerLast(e)

queue.offerLast("D")

Exemple : Deque en file et en pile

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Utiliser comme file (FIFO)
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("File (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // Utiliser comme pile (LIFO)
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("Pile (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

Sortie :

File (FIFO):
A
B
C
Pile (LIFO):
3
2
1

Pourquoi ArrayDeque ?

ArrayDeque est une implémentation Deque rapide et compacte basée sur un tableau. Pour une pile et une file, elle est généralement plus rapide et plus fiable que l’ancien Stack, et n’a pas de taille fixe (seule la mémoire la limite).

3. Stack : pile — dernier entré, premier sorti (LIFO)

Une pile suit le principe LIFO : on dépile l’élément du sommet en dernier ajouté. En programmation, une pile est utile pour l’historique des actions (undo), le parcours de structures récursives (arbres/graphes), l’évaluation d’expressions, etc.

Classe Stack (et pourquoi il vaut mieux l’éviter)

En Java, il existe la classe Stack, qui hérite de l’obsolète Vector. Aujourd’hui, elle n’est pas recommandée dans les nouveaux projets. Il est préférable d’utiliser Deque/ArrayDeque.

Méthodes de pile (Deque)

push(e)

pop()

peek()

Attention : dans Deque, ces opérations correspondent aux méthodes addFirst/removeFirst/peekFirst, mais pour la compatibilité il existe aussi les noms « pile » push/pop/peek.

Exemple : pile avec ArrayDeque

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Premier");
        stack.push("Deuxième");
        stack.push("Troisième");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Sortie :

Troisième
Deuxième
Premier

Pourquoi pas Stack ?

• Stack est synchronisée (plus lente) et hérite de l’obsolète Vector.
• ArrayDeque est souvent plus rapide et plus compacte, sans bloquer les threads.
• Si vous voyez Stack dans du nouveau code, c’est généralement un candidat au remplacement par ArrayDeque.

4. Quand utiliser quoi

LinkedList, ArrayDeque, PriorityQueue

ArrayDeque

ArrayDeque, LinkedList

Exemples de la vie courante :

• File à la banque — Queue.
• Historique des actions dans un éditeur — Stack.
• File de bus, entrée/sortie des deux côtés — Deque.

5. Exemples de code : implémenter une file et une pile dans une mini-application

Exemple 1 : file d’impression de documents

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("Document1.pdf");
        printQueue.offer("Document2.docx");
        printQueue.offer("Document3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("Impression en cours: " + doc);
        }
    }
}

Exemple 2 : pile d’annulation (undo)

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Insertion de texte");
        undoStack.push("Changement de couleur");
        undoStack.push("Suppression de l'image");

        System.out.println("Dernière action: " + undoStack.peek()); // Suppression de l'image

        while (!undoStack.isEmpty()) {
            System.out.println("Annulation: " + undoStack.pop());
        }
    }
}

Exemple 3 : file à deux extrémités

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("Extraction depuis le début: " + deque.removeFirst()); // C
        System.out.println("Extraction depuis la fin: " + deque.removeLast());   // D
        System.out.println("Restant: " + deque); // [A, B]
    }
}

6. Particularités d’implémentation et nuances

• ArrayDeque — l’implémentation de file/pile la plus rapide et polyvalente pour la plupart des tâches.
• LinkedList — implémente également Deque ; peut être utile, mais pour de courtes files elle est généralement plus lente que ArrayDeque.
• PriorityQueue — file par priorité : l’ordre est déterminé par la priorité (naturelle ou via un Comparator), ce n’est pas une file FIFO classique.
• Stack — obsolète, synchronisée ; dans les nouveaux projets, il est préférable d’utiliser ArrayDeque.
• Deque est pratique car elle permet de travailler à la fois avec le début et la fin de la structure, couvrant les scénarios de files et de piles avec une seule abstraction.

7. Erreurs typiques lors de l’utilisation des files et des piles

Erreur n°1 : utiliser Stack au lieu de Deque.
Beaucoup de débutants voient la classe Stack et la choisissent « par le nom ». Dans les projets modernes, on utilise à la place ArrayDeque (ou LinkedList) avec les méthodes push/pop.

Erreur n°2 : violer le principe de fonctionnement de la structure.
On essaie d’accéder aux éléments d’une file/pile par index, par exemple queue.get(0) ou stack.get(0). Cela ne se fait pas — utilisez les méthodes appropriées des files et piles (peek, poll, pop, etc.).

Erreur n°3 : utiliser remove()/element()/add() sans vérification.
Les méthodes remove, element, add peuvent lancer une exception si la structure est vide/pleine. Il est plus sûr d’utiliser les méthodes « douces » offer, poll, peek, qui renvoient des valeurs spéciales.

Erreur n°4 : utiliser ArrayDeque avec des éléments null.
ArrayDeque n’accepte pas null. Tenter d’ajouter null provoquera une NullPointerException.

Erreur n°5 : utiliser PriorityQueue comme une file ordinaire.
Dans PriorityQueue, l’ordre est défini par les priorités (naturelles ou via un Comparator). Pour un FIFO strict, utilisez ArrayDeque ou LinkedList.

Erreur n°6 : modifier la file/la pile pendant un parcours for-each.
Supprimer des éléments d’une collection pendant un for-each peut entraîner une ConcurrentModificationException. Pour supprimer, utilisez un itérateur ou les méthodes poll/pop dans une boucle, comme montré dans les exemples.

1

Mission

JAVA 25 SELF, niveau 27, leçon 2

Bloqué

Visualiser la prochaine tâche dans le système 💼

Visualiser la prochaine tâche dans le système 💼

Ouvrir

1

Mission

JAVA 25 SELF, niveau 27, leçon 2

Bloqué

Simulation du fonctionnement d'une imprimante et de l'historique des actions 🖨️🔄

Simulation du fonctionnement d'une imprimante et de l'historique des actions 🖨️🔄

Ouvrir