Interface Java Deque

Java Deque est une structure de données qui combine une file d'attente et une pile ordinaires. Vous pouvez ajouter et supprimer des éléments à la fois à la tête et à la queue du Deque. Dans la file d'attente "traditionnelle", vous ajoutez des éléments à la fin de la ligne (après le dernier élément) et supprimez des éléments de la tête de la file d'attente. Ce principe s'appelle First In First Out (FIFO) et fonctionne comme n'importe quelle ligne habituelle de clients dans la vraie vie. Dans Java Queue est une interface, une partie du cadre des collections. Il existe également une structure de données importante appelée Stack, une liste qui fonctionne avec des éléments selon un principe totalement inverse, LIFO - dernier entré, premier sorti. Il est similaire à une pile d'assiettes, l'ajout ou le retrait n'est possible qu'en haut.

File d'attente contre Deque

Deque est un type de file d'attente un peu étrange : vous pouvez ajouter de nouveaux éléments à la fois à la queue et à la tête de la ligne. Même histoire avec la suppression : vous pouvez supprimer le dernier ou le premier élément de cette structure. Par conséquent, cela semble être un mélange de pile et de file d'attente. Le nom "Deque" signifie "file d'attente à double extrémité". "Deque" se prononce comme un "jeu" de cartes et vous savez quoi ? Cela ressemble un peu à un vrai jeu de cartes : vous pouvez prendre une carte du bas ou du haut d'un tel jeu de cartes. Vous souhaitez ajouter ou supprimer des éléments des deux côtés d'une structure linéaire ? Utilisez Deque. Java 8 ou presque toute autre version le prend en charge. Imaginez une brique lego typique et des "tours" à une colonne faites de briques. Vous pouvez ajouter une nouvelle brique au sommet de la tour ou au bas. Vous pouvez également retirer une brique des deux côtés. Ici, nous avons un exemple : nous ajoutons toutes les briques jaunes en haut et toutes les briques rouges en bas. Nous allons bientôt démontrer cet exemple avec du code Java. Ainsi, vous pouvez mettre en file d'attente et retirer la file d'attente des deux extrémités d'un Deque Java, ce qui signifie que vous pouvez utiliser un Deque à la fois comme file d'attente et comme pile. En savoir plus sur Stack en Java : Java Stack 101 : plonger dans la classe Stack En savoir plus sur Queue en Java : Java Queue Interface et ses implémentations

Les fonctionnalités de Deque

• Deque en Java est une interface, dont les implémentations fournissent le support d'un tableau redimensionnable. Vous disposez ainsi d'un éventail de capacités sans restriction et vous pouvez ajouter de nouveaux éléments en fonction de vos besoins.
• L'accès simultané par plusieurs threads n'est pas pris en charge par Deque
• Deque n'est pas thread-safe en cas d'absence de synchronisation externe.
• Aucun élément Null autorisé dans le tableau deque.

Déclaration de l'interface Java Deque

public interface Deque<E> extends Queue<E>

Méthodes Java Deque

java.util.Deque est une interface qui étend l'interface de file d'attente Java et représente une file d'attente à double extrémité. Ainsi, vous pouvez utiliser toutes les méthodes Java Queue tout en travaillant avec un Deque. Bien que Deque n'étende pas l'interface Stack, l'interface Deque définit des méthodes qui vous permettent d'effectuer des opérations de pile typiques telles que push , peek et pop .

• boolean add(element) ajoute un élément à la queue du Deque. Renvoie true en cas de succès, lève une IllegalStateException si aucun espace n'est actuellement disponible.
• addFirst(element) ajoute un élément à la tête du Deque.
• addLast(element) ajoute un élément à la queue du Deque.
• offre (élément) ajoute un élément à la queue et renvoie un booléen pour expliquer si l'insertion a réussi.
• offerFirst(element) ajoute un élément à la tête et renvoie un booléen pour expliquer si l'insertion a réussi.
• offerLast(element) ajoute un élément à la queue et renvoie un booléen pour expliquer si l'insertion a réussi.
• iterator() renvoie un itérateur pour le deque.
• descendantIterator() renvoie un itérateur qui a l'ordre inverse pour cette deque.
• push(element) ajoute un élément à la tête.
• pop(element) supprime un élément de la tête et le renvoie.
• removeFirst() supprime l'élément en tête.
• removeLast() supprime l'élément à la fin.
• poll() récupère et supprime la tête de la file d'attente représentée par ce deque (autrement dit, le premier élément de ce deque), ou renvoie null si ce deque est vide.
• pollFirst() récupère et supprime le premier élément de ce deque, ou renvoie null si ce deque est vide.
• pollLast() récupère et supprime le dernier élément de ce deque, ou retourne null si ce deque est vide.
• peek() récupère, mais ne supprime pas, la tête de file représentée par ce deque (autrement dit, le premier élément de ce deque), ou renvoie null si ce deque est vide.
• peekFirst() récupère, mais ne supprime pas, le premier élément de ce deque, ou renvoie null si ce deque est vide.
• peekLast() récupère, mais ne supprime pas, le dernier élément de ce deque, ou renvoie null si ce deque est vide.

Ici, dans le tableau ci-dessous, toutes les méthodes sont divisées par groupes. Comme vous pouvez le voir, il existe de nombreuses méthodes différentes pour ajouter et supprimer un élément. Par exemple, removeFirst() et pop() suppriment le premier élément de deque. Le second "est venu" de la pile. Cela signifie que si vous utilisez votre ArrayDeque uniquement en tant que pile, utilisez pop() pour supprimer, push() pour ajouter et peek() pour examiner. Cela rend votre code plus sensible pour les autres développeurs.

Implémentations Deque

Java Deque est une interface et a des implémentations dans l'API Java Collections :

• java.util.LinkedList // Implémentation de la liste et de Deque
• java.util.ArrayDeque // Implémentation de Deque, bibliothèque Java

La classe LinkedList utilise une liste à double liaison en interne pour modéliser une file d'attente ou une deque. La classe ArrayDeque stocke les éléments en interne dans un tableau. Si le nombre d'éléments dépasse le volume du tableau, un nouveau tableau est alloué et tous les éléments sont déplacés. Cela signifie qu'ArrayDeque grandit en fonction des besoins.

Classe ArrayDeque

La classe ArrayDeque <E> est une file d'attente générale bidirectionnelle, héritant des fonctionnalités de la classe AbstractCollection et utilisant l'interface Deque. ArrayDeque fournit la possibilité d'utiliser deque et resizable-array. Initialement, le tableau est initialisé avec la taille 16. Il est implémenté comme une file d'attente bidirectionnelle, où il prend en charge deux pointeurs, à savoir la tête et la queue. Il hérite de la classe AbstractCollection et implémente l' interface Deque . Les points importants concernant la classe ArrayDeque sont :

• Vous pouvez ajouter ou supprimer des éléments de la queue et de la tête du ArrayDeque
• Les éléments nuls ne sont pas autorisés
• ArrayDeque n'est pas thread-safe, en l'absence de synchronisation externe.
• ArrayDeque n'a aucune restriction de capacité.

Constructeurs de classe ArrayDeque

• ArrayDeque() crée une file d'attente vide.
• ArrayDeque (Collection <? Extends E> collection) crée une file d'attente remplie d'éléments de la collection Collection.
• ArrayDeque (capacité int) crée une file d'attente avec une capacité de capacité initiale . Si vous ne spécifiez pas la capacité initiale, la capacité par défaut est 16.

Exemple Java Deque — ArrayDeque

Vous souvenez-vous de l'exemple de la tour Lego du début de l'article ? Créons une classe pour construire des tours à une colonne en briques Lego. Les briques peuvent être rouges, jaunes ou bleues. Notre règle de construction de tour : nous mettons les briques rouges en bas et les briques jaunes en haut. Exemple Big Java Deque

//enum with colors
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Voici notre classe Tour. Nous initions une tour. La tour initiée dépend de la quantité de rouges et de jaunes. Nous pouvons ajouter de la brique à la tour ou l'enlever. Nous ajoutons de la brique en haut si elle est jaune et en bas si elle est rouge.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

Le résultat de l'exécution de ce programme :

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements:
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

Attends quoi?? Pourquoi les rouges sont-ils en haut ? Non, ils ne le font pas. Ils viennent d'être imprimés sur la console en commençant par le premier (en bas) jusqu'au dernier (en haut). Donc, si vous voulez voir quelque chose comme dans l'image avec les briques ci-dessus, vous pouvez modifier la méthode drawTower de la classe LegoTower. C'est une tâche très facile !

Liste liée

L'interface List conserve la séquence d'ajout d'éléments et permet l'accès à l'élément par index. Deque est une file d'attente bidirectionnelle et prend en charge l'ajout et la suppression d'éléments des deux côtés. LinkedList est principalement connue comme une implémentation de List, mais cette classe implémente également Deque, et elle nous permet de créer une file d'attente bidirectionnelle composée de tous les objets, y compris null. LinkedList est une collection d'éléments. On peut le voir dans le code source de la classe, cette fois attention aux champs : Ici on rajoute un exemple, mais si vous voulez en savoir plus sur LinkedList, bienvenue dans cet article CodeGym .

Implémentation de listes chaînées en Java, ajout et suppression d'éléments. Exemple

Essayons ces opérations dans la pratique. Tout d'abord, l'implémentation de Java LinkedList : créer une LinkedList de chaînes, en y ajoutant 3 éléments. Retirez-en ensuite un, puis ajoutez-en un au milieu.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Le résultat de l'exécution de ce programme :

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]