Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Apprendre Structure de Données de File en Java | Structures de Données Avancées en Java
Structures de Données Java

bookStructure de Données de File en Java

Commençons par une Queue. Imaginez une file d'attente dans un magasin lors d'une vente. Il y a 10 personnes ; la première personne est plus proche des portes du magasin que les autres, et la dixième personne est la plus éloignée. Lorsque la première personne entre dans le magasin, elle quitte la file d'attente, ce qui fait avancer toute la file d'une personne. La Queue en Java fonctionne selon un principe très similaire.

De cette manière, il est possible d’implémenter divers programmes où la logique de file d’attente est bien pensée. Par exemple, la mise en place d’un tableau avec des plans et des tâches.

Mais d'abord, examinons les méthodes de base pour travailler avec une Queue.

Queue est une interface dont hérite la classe LinkedList, que vous connaissez déjà, donc nous utiliserons cette implémentation.

Ainsi, vous utilisez l’interface comme type de l’objet, mais l’implémentation de l’objet sera LinkedList car il s’agit d’une implémentation spécifique de cet objet. (Rappelez-vous qu’il n’est pas possible de créer des objets à partir d’une interface).

Exemple :

Example.java

Example.java

copy

              
1234

            
// `LinkedList` as implementation of the `List` interface:
List<T> list = new LinkedList<>(); 
// `LinkedList` as implementation of the `Queue` interface:
Queue<T> queue = new LinkedList<>();

De cette manière, il est possible de rendre l’application très flexible en utilisant différentes implémentations de la même interface.

Mais revenons aux méthodes de manipulation de Queue.

Méthodes

Quelques méthodes clés de l’interface Queue sont :

  • add(element): ajoute un élément à la file, lève une exception si l’opération n’est pas possible ;
  • offer(element): ajoute un élément à la file, retourne true en cas de succès ou false sinon.

Il est possible de constater que ces méthodes réalisent essentiellement la même opération. Cependant, la différence principale réside dans la sécurité de la méthode offer. En cas d’ajout incorrect d’un élément, la méthode offer ne lèvera pas d’exception et n’interrompra pas l’exécution du programme.

Cependant, cette fonctionnalité n’est pas d’un grand intérêt pour le moment, car une Queue classique n’est pas limitée. Il existe toutefois une structure appelée BlockingQueue, qui impose une limitation sur le nombre d’éléments ; dans ce cas, ces méthodes présenteront une différence notable.

Examinons un exemple :

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.add("One");
        queue.add("Two");
        queue.add("Three");
        System.out.println("Queue: " + queue);
    }
}

Comme vous pouvez le constater, lors de l'utilisation de la méthode add() et en essayant d'ajouter un élément qui ne rentre pas dans la file d'attente, le programme génère une erreur, interrompant l'exécution de manière inattendue.

Essayons la même opération mais avec une méthode plus sûre — offer() :

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
    }
}

Comme vous pouvez le constater, l’élément n’a pas été ajouté à la file, mais aucune exception n’a été levée non plus. On peut donc considérer que l’erreur a été gérée de manière élégante.

Vous pouvez gérer les exceptions différemment en utilisant une structure comme try-catch, mais nous en parlerons plus tard.

Méthodes de suppression

  • remove() : supprime et retourne l’élément au début de la file, en levant une exception si la file est vide ;
  • poll() : supprime et retourne l’élément au début de la file, retourne null si la file est vide.

Ces méthodes remplissent exactement la fonction comme si la première personne dans la file entrait dans le magasin et quittait la file. C’est ici que le principe FIFO (First In, First Out) entre en jeu. Autrement dit, l’élément qui a été ajouté en premier à la file sera le premier à être supprimé.

Ici, vous pouvez également observer la différence entre ces deux méthodes. La méthode poll() est utilisée plus fréquemment que la méthode remove() car elle est plus sûre et ne lève pas d’exceptions.

Voyons un exemple :

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.remove();
        queue.remove();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Comme vous pouvez le constater, le programme génère une NoSuchElementException car nous essayons de retirer un élément d'une file vide.

Pour éviter une telle exception, il est préférable d'utiliser la méthode poll() :

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.poll();
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

À présent, nous avons retiré un élément de la file de manière sécurisée, et aucune exception n'a été levée lorsque nous avons tenté de retirer un élément d'une liste vide.

La fonctionnalité de retour de poll() par null peut être utilisée, par exemple, dans une boucle while().

Examinons un exemple :

Main.java

Main.java

copy

              
1234567891011121314151617181920

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.poll() != null) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

De cette manière, il est possible de supprimer tous les éléments de la file en utilisant une boucle.

Il est important de noter que le premier élément entré dans la file est celui qui est supprimé ! Par exemple, dans le cas de l'exemple ci-dessus, l'élément avec la donnée "One" a été supprimé en premier.

Le principe FIFO est illustré ci-dessous :

Main.java

Main.java

copy

              
123456789101112131415161718

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);         
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Nous pouvons passer aux méthodes qui renvoient le premier et le dernier éléments :

  • element() : renvoie, sans supprimer, l’élément au début de la file, lève une exception si la file est vide ;
  • peek() : renvoie, sans supprimer, l’élément au début de la file, retourne null si la file est vide.

L’utilisation de la méthode peek() constitue une approche plus fiable et sûre, car elle permet d’éviter les exceptions potentielles.

Voyons un exemple d’utilisation :

Main.java

Main.java

copy

              
12345678910111213141516

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
        System.out.println("The first element in the queue: " + queue.peek());
        System.out.println("Queue after the `peek()` method: " + queue);
    }
}

Il est possible de combiner cette méthode avec d’autres méthodes de file.

Si une file contient cinq éléments et qu’il est nécessaire de supprimer tous les éléments jusqu’au quatrième (inclus), examinons l’implémentation d’une telle opération :

Main.java

Main.java

copy

              
123456789101112131415161718192021

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (!queue.peek().equals("Four")) {
            queue.poll();
        }
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Vous avez utilisé une boucle avec une condition basée sur la méthode peek().

Il est possible d’optimiser considérablement cette boucle en utilisant la méthode contains(). Cette méthode retourne true si l’élément spécifié est présent dans la file et false s’il ne l’est pas.

Améliorons le code ci-dessus :

Main.java

Main.java

copy

              
1234567891011121314151617181920

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.contains("Four")) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

Ici, nous définissons une seule condition pour la boucle while. Nous avons réussi à supprimer tous les éléments jusqu'à et y compris l'élément "Four".

1. Qu'est-ce qu'une Queue en Java ?

2. Quelle interface représente une Queue dans le Java Collections Framework ?

3. Quel est le but de la méthode offer() dans l’interface Queue ?

4. Que fait la méthode poll() dans l’interface Queue ?

5. Quelle classe du package java.util.concurrent de Java représente une file bloquante bornée ?

6. Que se passe-t-il si vous essayez d’ajouter un élément à une file d’attente pleine en utilisant la méthode add() ?

question mark

Qu'est-ce qu'une Queue en Java ?

Select the correct answer

question mark

Quelle interface représente une Queue dans le Java Collections Framework ?

Select the correct answer

question mark

Quel est le but de la méthode offer() dans l’interface Queue ?

Select the correct answer

question mark

Que fait la méthode poll() dans l’interface Queue ?

Select the correct answer

question mark

Quelle classe du package java.util.concurrent de Java représente une file bloquante bornée ?

Select the correct answer

question mark

Que se passe-t-il si vous essayez d’ajouter un élément à une file d’attente pleine en utilisant la méthode add() ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 2. Chapitre 1

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

bookStructure de Données de File en Java

Glissez pour afficher le menu

Commençons par une Queue. Imaginez une file d'attente dans un magasin lors d'une vente. Il y a 10 personnes ; la première personne est plus proche des portes du magasin que les autres, et la dixième personne est la plus éloignée. Lorsque la première personne entre dans le magasin, elle quitte la file d'attente, ce qui fait avancer toute la file d'une personne. La Queue en Java fonctionne selon un principe très similaire.

De cette manière, il est possible d’implémenter divers programmes où la logique de file d’attente est bien pensée. Par exemple, la mise en place d’un tableau avec des plans et des tâches.

Mais d'abord, examinons les méthodes de base pour travailler avec une Queue.

Queue est une interface dont hérite la classe LinkedList, que vous connaissez déjà, donc nous utiliserons cette implémentation.

Ainsi, vous utilisez l’interface comme type de l’objet, mais l’implémentation de l’objet sera LinkedList car il s’agit d’une implémentation spécifique de cet objet. (Rappelez-vous qu’il n’est pas possible de créer des objets à partir d’une interface).

Exemple :

Example.java

Example.java

copy

              
1234

            
// `LinkedList` as implementation of the `List` interface:
List<T> list = new LinkedList<>(); 
// `LinkedList` as implementation of the `Queue` interface:
Queue<T> queue = new LinkedList<>();

De cette manière, il est possible de rendre l’application très flexible en utilisant différentes implémentations de la même interface.

Mais revenons aux méthodes de manipulation de Queue.

Méthodes

Quelques méthodes clés de l’interface Queue sont :

  • add(element): ajoute un élément à la file, lève une exception si l’opération n’est pas possible ;
  • offer(element): ajoute un élément à la file, retourne true en cas de succès ou false sinon.

Il est possible de constater que ces méthodes réalisent essentiellement la même opération. Cependant, la différence principale réside dans la sécurité de la méthode offer. En cas d’ajout incorrect d’un élément, la méthode offer ne lèvera pas d’exception et n’interrompra pas l’exécution du programme.

Cependant, cette fonctionnalité n’est pas d’un grand intérêt pour le moment, car une Queue classique n’est pas limitée. Il existe toutefois une structure appelée BlockingQueue, qui impose une limitation sur le nombre d’éléments ; dans ce cas, ces méthodes présenteront une différence notable.

Examinons un exemple :

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.add("One");
        queue.add("Two");
        queue.add("Three");
        System.out.println("Queue: " + queue);
    }
}

Comme vous pouvez le constater, lors de l'utilisation de la méthode add() et en essayant d'ajouter un élément qui ne rentre pas dans la file d'attente, le programme génère une erreur, interrompant l'exécution de manière inattendue.

Essayons la même opération mais avec une méthode plus sûre — offer() :

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
    }
}

Comme vous pouvez le constater, l’élément n’a pas été ajouté à la file, mais aucune exception n’a été levée non plus. On peut donc considérer que l’erreur a été gérée de manière élégante.

Vous pouvez gérer les exceptions différemment en utilisant une structure comme try-catch, mais nous en parlerons plus tard.

Méthodes de suppression

  • remove() : supprime et retourne l’élément au début de la file, en levant une exception si la file est vide ;
  • poll() : supprime et retourne l’élément au début de la file, retourne null si la file est vide.

Ces méthodes remplissent exactement la fonction comme si la première personne dans la file entrait dans le magasin et quittait la file. C’est ici que le principe FIFO (First In, First Out) entre en jeu. Autrement dit, l’élément qui a été ajouté en premier à la file sera le premier à être supprimé.

Ici, vous pouvez également observer la différence entre ces deux méthodes. La méthode poll() est utilisée plus fréquemment que la méthode remove() car elle est plus sûre et ne lève pas d’exceptions.

Voyons un exemple :

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.remove();
        queue.remove();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Comme vous pouvez le constater, le programme génère une NoSuchElementException car nous essayons de retirer un élément d'une file vide.

Pour éviter une telle exception, il est préférable d'utiliser la méthode poll() :

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.poll();
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

À présent, nous avons retiré un élément de la file de manière sécurisée, et aucune exception n'a été levée lorsque nous avons tenté de retirer un élément d'une liste vide.

La fonctionnalité de retour de poll() par null peut être utilisée, par exemple, dans une boucle while().

Examinons un exemple :

Main.java

Main.java

copy

              
1234567891011121314151617181920

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.poll() != null) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

De cette manière, il est possible de supprimer tous les éléments de la file en utilisant une boucle.

Il est important de noter que le premier élément entré dans la file est celui qui est supprimé ! Par exemple, dans le cas de l'exemple ci-dessus, l'élément avec la donnée "One" a été supprimé en premier.

Le principe FIFO est illustré ci-dessous :

Main.java

Main.java

copy

              
123456789101112131415161718

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);         
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Nous pouvons passer aux méthodes qui renvoient le premier et le dernier éléments :

  • element() : renvoie, sans supprimer, l’élément au début de la file, lève une exception si la file est vide ;
  • peek() : renvoie, sans supprimer, l’élément au début de la file, retourne null si la file est vide.

L’utilisation de la méthode peek() constitue une approche plus fiable et sûre, car elle permet d’éviter les exceptions potentielles.

Voyons un exemple d’utilisation :

Main.java

Main.java

copy

              
12345678910111213141516

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
        System.out.println("The first element in the queue: " + queue.peek());
        System.out.println("Queue after the `peek()` method: " + queue);
    }
}

Il est possible de combiner cette méthode avec d’autres méthodes de file.

Si une file contient cinq éléments et qu’il est nécessaire de supprimer tous les éléments jusqu’au quatrième (inclus), examinons l’implémentation d’une telle opération :

Main.java

Main.java

copy

              
123456789101112131415161718192021

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (!queue.peek().equals("Four")) {
            queue.poll();
        }
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Vous avez utilisé une boucle avec une condition basée sur la méthode peek().

Il est possible d’optimiser considérablement cette boucle en utilisant la méthode contains(). Cette méthode retourne true si l’élément spécifié est présent dans la file et false s’il ne l’est pas.

Améliorons le code ci-dessus :

Main.java

Main.java

copy

              
1234567891011121314151617181920

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.contains("Four")) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

Ici, nous définissons une seule condition pour la boucle while. Nous avons réussi à supprimer tous les éléments jusqu'à et y compris l'élément "Four".

1. Qu'est-ce qu'une Queue en Java ?

2. Quelle interface représente une Queue dans le Java Collections Framework ?

3. Quel est le but de la méthode offer() dans l’interface Queue ?

4. Que fait la méthode poll() dans l’interface Queue ?

5. Quelle classe du package java.util.concurrent de Java représente une file bloquante bornée ?

6. Que se passe-t-il si vous essayez d’ajouter un élément à une file d’attente pleine en utilisant la méthode add() ?

question mark

Qu'est-ce qu'une Queue en Java ?

Select the correct answer

question mark

Quelle interface représente une Queue dans le Java Collections Framework ?

Select the correct answer

question mark

Quel est le but de la méthode offer() dans l’interface Queue ?

Select the correct answer

question mark

Que fait la méthode poll() dans l’interface Queue ?

Select the correct answer

question mark

Quelle classe du package java.util.concurrent de Java représente une file bloquante bornée ?

Select the correct answer

question mark

Que se passe-t-il si vous essayez d’ajouter un élément à une file d’attente pleine en utilisant la méthode add() ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 2. Chapitre 1
some-alt