deque java deque implementation
Ce didacticiel fournit des explications détaillées sur Deque ou «file d'attente à deux extrémités» en Java. Vous découvrirez l'interface Deque, les méthodes API, l'implémentation, etc.:
La Deque ou «double queue» en Java est une structure de données dans laquelle nous pouvons insérer ou supprimer des éléments des deux extrémités. Le deque est une interface en Java appartenant au package java.util et implémente l'interface java.queue.
Nous pouvons implémenter deque sous forme de structure de pile (Last In, First Out) ou de file d'attente (first-in-first-out). Deque est plus rapide que Stack et / ou LinkedList. Deque est prononcé comme «deck» comme dans «deck of cards».
=> Cliquez ici pour voir de A à Z des didacticiels de formation Java ici.
Ce que vous apprendrez:
À propos de Java
Une collection deque typique ressemblera à celle ci-dessous:
implémentation d'une file d'attente prioritaire en java
Deque est principalement utilisé pour implémenter des structures de données de pile, de file d'attente ou de liste. Il peut également être utilisé pour implémenter des files d'attente prioritaires. Les fonctionnalités d'annulation ou d'historique principalement présentes dans les navigateurs Web peuvent être implémentées à l'aide de deques.
Interface Java Deque
Le diagramme ci-dessous montre la hiérarchie de la file d'attente double ou du deque. Comme indiqué dans le diagramme ci-dessous, l'interface Deque s'étend à l'interface Queue qui à son tour étend l'interface Collection.
Pour utiliser une interface deque dans notre programme, nous devons importer le package contenant la fonctionnalité deque en utilisant une instruction d'importation comme indiqué ci-dessous.
import java.util.deque; ou
import java.util.*; Comme le deque est une interface, nous avons besoin de classes concrètes pour implémenter la fonctionnalité de l'interface deque.
Les deux classes ci-dessous implémentent l'interface deque.
- ArrayDeque
- LinkedList
Par conséquent, nous pouvons créer des objets deque en utilisant ces deux classes comme indiqué ci-dessous:
Deque numdeque = new ArrayDeque (); Deque strDeque = new LinkedList (); Ainsi, une fois que les objets deque ci-dessus sont créés avec succès, ils peuvent utiliser la fonctionnalité de l'interface deque.
Vous trouverez ci-dessous quelques points importants à noter à propos de deque:
- L'interface Deque prend en charge les tableaux redimensionnables qui peuvent croître selon les besoins.
- Les array deques n'autorisent pas l'utilisation de valeurs Null.
- Deque ne prend pas en charge l'accès simultané par plus d'un thread.
- Deque n'est pas thread-safe sauf si une synchronisation externe est fournie.
ArrayDeque en Java
ArrayDeque appartient au package java.util. Il implémente l'interface deque. En interne, la classe ArrayDeque utilise un tableau redimensionnable dynamiquement qui augmente à mesure que le nombre d'éléments est augmenté.
Le diagramme ci-dessous montre la hiérarchie de la classe ArrayDeque:
Comme le montre le diagramme, la classe ArrayDeque hérite de la classe AbstractCollection et implémente l'interface Deque.
quel est un bon site pour regarder l'anime
Nous pouvons créer un objet deque en utilisant la classe ArrayDeque comme indiqué ci-dessous:
Deque deque_obj = new ArrayDeque (); et exemple
Le programme Java suivant montre un exemple simple pour mieux comprendre le deque. Ici, nous avons utilisé la classe ArrayDeque pour instancier l'interface deque. Nous venons d'ajouter quelques éléments à l'objet deque puis de les imprimer en utilisant une boucle forEach.
import java.util.*; public class Main { public static void main(String() args) { //Creat a Deque and add elements Deque cities_deque = new ArrayDeque(); cities_deque.add('Delhi'); cities_deque.add('Mumbai'); cities_deque.add('Bangaluru'); System.out.println('Deque Contents:'); //Traverse the Deque for (String str : cities_deque) { System.out.print(str + ' '); } } } Production:
L'API et les méthodes Java
Comme l'interface deque implémente une interface de file d'attente, elle prend en charge toutes les méthodes de l'interface de file d'attente. En outre, l'interface deque fournit les méthodes suivantes qui peuvent être utilisées pour effectuer diverses opérations avec l'objet deque.
Résumons ces méthodes dans le tableau ci-dessous.
| Méthode | Prototype de méthode | Description |
|---|---|---|
| getFirst | E getFirst () | Récupérez le premier élément du deque sans le supprimer. |
| ajouter | booléen ajouter (E e) | Ajoute l'élément e donné dans le deque (à la fin) sans violer les restrictions de capacité et retourne true en cas de succès. Lève IllegalStateException si aucun espace disponible dans le deque. |
| addFirst | void addFirst (E e) | Ajoute l'élément e donné au début de la file d'attente sans violer les restrictions de capacité. |
| addLast | void addLast (E e) | Ajoute l'élément e au dernier deque sans violer les restrictions de capacité. |
| contient | boolean contient (Object o) | Vérifie si le deque contient l'élément o donné. Renvoie vrai si oui. |
| descendingIterator | Itérateur descendantIterator () | Cette méthode retourne un itérateur d'ordre inverse pour le deque. |
| élément | Élément E () | Renvoie le premier élément ou tête du deque. Notez qu'il ne supprime pas l'élément. |
| getLast | E getLast () | Obtient le dernier élément du deque sans le supprimer. |
| itérateur | Itérateur itérateur () | Renvoie un itérateur standard sur les éléments du deque. |
| offre | offre booléenne (E e) | Ajoute l'élément e donné au deque (en tant que queue) sans violer les restrictions de capacité. Renvoie vrai en cas de succès et faux en cas d'échec. |
| offrePremier | offre booléennePremier (E e) | Insérez l'élément donné e à l'avant du deque sans violer les restrictions de capacité. |
| offreDernière | offre booléenneLast (E e) | Insérez l'élément donné e à la fin du deque sans violer les restrictions de capacité. |
| coup d'oeil | E coup d'oeil () | Renvoie la tête du deque (premier élément) ou null si une file d'attente est vide. ** ne supprime pas la tête |
| coup d'oeil | E coup d'oeil d'abord () | Renvoie le premier élément du deque sans le supprimer. Renvoie null si le deque est vide. |
| peekLast | E peekLast () | Récupère le dernier élément du deque sans le supprimer. Renvoie null si le deque est vide. |
| sondage | Sondage E () | Supprime et renvoie la tête du deque. Renvoie null si le deque est vide. |
| pollFirst | E pollFirst () | Renvoie et supprime le premier élément du deque. Renvoie null si le deque est vide. |
| sondageDernier | E pollDernier () | Renvoie et supprime le dernier élément du deque. Renvoie null si le deque est vide. |
| pop | E pop () | Pop l'élément de la pile qui est représenté à l'aide de deque. |
| pousser | vide poussé (E e) | Poussez l'élément donné e sur la pile représentée à l'aide de deque sans violer les restrictions de capacité. Renvoie true en cas de succès ou IllegalStateException si aucun espace n'est disponible sur deque. |
| supprimer | E supprimer () | Retirez et retournez la tête du deque. |
| supprimer | boolean remove (objet o) | Supprimez la première occurrence de l'élément o donné du deque. |
| supprimer d'abord | E removeFirst () | Retirez et renvoyez le premier élément du deque. |
| removeFirstOccurrence | booléen removeFirstOccurrence (Object o) | Supprime la première occurrence de l'élément o donné du deque. |
| removeLast | E removeLast () | Récupère et supprime le dernier élément du deque. |
| removeLastOccurrence | booléen removeLastOccurrence (Object o) | Supprime la dernière occurrence d'un élément o donné du deque. |
| Taille | taille int () | Renvoie la taille ou le nombre d'éléments dans le deque. |
Et implémentation en Java
Implémentons maintenant un programme Java pour illustrer certaines des principales méthodes de deque évoquées ci-dessus.
Dans ce programme, nous utilisons un type String deque, puis ajoutons des éléments à ce deque en utilisant diverses méthodes comme add, addFirst, addLast, push, offer, offerFirst, etc. Ensuite, nous affichons le deque. Ensuite, nous définissons les itérateurs standard et inversés pour le deque et traversons le deque pour imprimer les éléments.
Nous utilisons également les autres méthodes telles que contains, pop, push, peek, poll, remove, etc.
import java.util.*; public class Main { public static void main(String() args) { //Declare Deque object Deque deque = new LinkedList(); // add elements to the queue using various methods deque.add('One'); //add () deque.addFirst('Two'); //addFirst () deque.addLast('Three'); //addLast () deque.push('Four'); //push () deque.offer('Five'); //offer () deque.offerFirst('Six'); //offerFirst () deque.offerLast('Seven'); //offerLast () System.out.println('Initial Deque:'); System.out.print(deque + ' '); // Iterate using standard iterator System.out.println('
Deque contents using Standard Iterator:'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Iterate using Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Deque contents using Reverse Iterator:'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek () method System.out.println('
Deque Peek:' + deque.peek()); System.out.println('
Deque,After peek:' + deque); // Pop () method System.out.println('
Deque Pop:' + deque.pop()); System.out.println('
Deque,After pop:' + deque); // contains () method System.out.println('
Deque Contains Three: ' + deque.contains('Three')); deque.removeFirst(); //removeFirst () deque.removeLast(); //removeLast () System.out.println('
Deque, after removing ' + 'first and last elements: ' + deque); } }Production:
Questions fréquemment posées
Q # 1) Deque est-il compatible avec les threads Java?
Répondre: ArrayDeque n'est pas thread-safe. Mais l'interface BlockingDeque dans la classe java.util.concurrent représente le deque. Ce deque est thread-safe.
Q # 2) Pourquoi Deque est-il plus rapide que stack?
Répondre: L'interface ArrayDeque qui implémente l'interface deque est efficace en mémoire car elle n'a pas besoin de garder une trace des nœuds précédents ou suivants. En outre, il s'agit d'une implémentation redimensionnable. Ainsi deque est plus rapide que la pile.
Q # 3) Deque est-il une pile?
Répondre: Un deque est une file d'attente à deux extrémités. Il permet le comportement LIFO et peut donc être implémenté comme une pile bien que ce ne soit pas une pile.
Q # 4) Où Deque est-il utilisé?
Répondre: Un deque est principalement utilisé pour implémenter des fonctionnalités telles que l'annulation et l'historique.
Q # 5) Est-ce que Deque est circulaire?
Répondre: Oui, Deque est circulaire.
Conclusion
Ceci complète notre tutoriel sur l'interface Deque en Java. L'interface deque est implémentée par une structure de données deque qui est une collection qui peut insérer et supprimer des éléments des deux extrémités.
Les deux classes, à savoir ArrayDeque et LinkedList, implémentent l'interface deque. Nous pouvons utiliser ces classes pour implémenter la fonctionnalité de l'interface deque.
=> Visitez ici pour la série exclusive de didacticiels de formation Java.
lecture recommandée
- File d'attente à double extrémité (Deque) en C ++ avec des exemples
- Java Queue - Méthodes de file d'attente, implémentation de file d'attente avec des exemples
- Tutoriel Java Priority Queue - Implémentation et exemples
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- Structure de données de file d'attente en C ++ avec illustration
- Structure de données de file d'attente circulaire C ++: implémentation et applications
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
- File d'attente prioritaire dans STL