0Pricing
Java Academy · Leçon

Opérations sur une deque : pile et file

Utilisez LinkedList comme une deque pour implémenter le comportement d’une pile (push/pop) et d’une file (offer/poll).

Opérations sur une deque : pile et file est une leçon Java Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Java Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Java Academy comprend 4 leçons au total.

Deque : file à double extrémité

Une deque, ou file à double extrémité, permet d'insérer et de supprimer des éléments aux deux extrémités. L'interface Deque de Java est implémentée par LinkedList et ArrayDeque.

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

ArrayDeque ou LinkedList comme deque

ArrayDeque est généralement préférable à LinkedList comme deque :

  • Pas de surcoût lié à un nœud pour chaque élément
  • Meilleure localité du cache
  • Opérations de pile ou de file légèrement plus rapides

Choisissez LinkedList uniquement si vous avez également besoin de l'interface List.

Opérations de pile avec une deque

Utilisez push (addFirst) et pop (removeFirst) pour simuler une pile LIFO. Évitez la classe Stack historique : elle est synchronisée et obsolète.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

Opérations de file avec une deque

Utilisez offer (addLast) et poll (removeFirst) pour simuler une file FIFO. offer renvoie false en cas d'échec ; add lève une exception.

Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");

System.out.println(queue.poll());  // task1
System.out.println(queue.poll());  // task2
System.out.println(queue.size());  // 1

Tableau de référence des méthodes de deque

Deque fournit deux familles de méthodes : l'une lève des exceptions, l'autre renvoie des valeurs spéciales :

  • addFirst/addLast contre offerFirst/offerLast
  • removeFirst/removeLast contre pollFirst/pollLast
  • getFirst/getLast contre peekFirst/peekLast

Préférez la famille offer/poll/peek pour éviter les exceptions lorsque les deques sont vides.

Exemple concret : annuler et rétablir avec deux piles

Un cas d'utilisation classique d'une deque : l'historique des annulations est une pile. Le rétablissement utilise une autre pile.

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

Vérifier un palindrome avec une deque

Les deques rendent la vérification des palindromes élégante : comparez simultanément les caractères des deux extrémités.

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

BFS avec une file

La recherche en largeur utilise une file. ArrayDeque est le choix standard pour BFS en programmation compétitive et pour le parcours de graphes.

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

DFS avec une pile

La recherche en profondeur utilise une pile. Là encore, préférez ArrayDeque à la classe Stack historique.

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

Deque limitée avec vérification de la taille

ArrayDeque augmente dynamiquement de taille, mais vous pouvez imposer manuellement une capacité pour simuler un tampon de taille limitée :

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

Remarques sur les performances

ArrayDeque utilise un tableau circulaire qui double de taille lorsqu'il est plein. Le coût amorti de toutes les opérations est O(1). Elle est plus performante que LinkedList dans la plupart des tests de performance grâce à l'efficacité du cache. Ne synchronisez jamais manuellement : utilisez ConcurrentLinkedDeque ou une file bloquante pour la concurrence.

Vérification rapide

Quelle classe devez-vous préférer à la classe Stack historique pour les opérations LIFO ?

Récapitulatif : opérations sur une deque

Points essentiels :

  • Deque permet des insertions et suppressions en O(1) aux deux extrémités
  • ArrayDeque est préférable à LinkedList pour une utilisation exclusive comme pile ou comme file
  • push/pop → pile LIFO ; offer/poll → file FIFO
  • Utilisations classiques : annuler/rétablir, BFS/DFS, fenêtre glissante et vérification de palindrome
  • Évitez les classes Stack et Queue historiques

Questions Fréquemment Posées

La leçon « Opérations sur une deque : pile et file » est-elle gratuite ?

Oui — le texte complet de « Opérations sur une deque : pile et file » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Java Academy, passe à CoddyKit PRO. Le cours Java Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Opérations sur une deque : pile et file » ?

Utilisez LinkedList comme une deque pour implémenter le comportement d’une pile (push/pop) et d’une file (offer/poll). Tu pratiques Java Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Java Academy ?

Aucune expérience préalable n'est requise. Java Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.

Combien de temps prend la leçon « Opérations sur une deque : pile et file » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Java Academy ?

Oui. Chaque leçon Java Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Fonctionnement interne de LinkedList
  2. Opérations sur une deque : pile et file
  3. LinkedList et ArrayList : compromis
  4. PriorityQueue pour le traitement ordonné
← Retour à Java Academy