Structures de données en Java - Pile et file d'attente

Bonjour! Aujourd'hui, nous allons parler de choses aussi importantes pour tout programmeur que les structures de données . Wikipédia dit : La structure de données ( eng. data structure ) est une unité logicielle qui vous permet de stocker et de traiter un grand nombre de données du même type et/ou logiquement liées en informatique. La définition est un peu confuse, mais son essence est claire. Une structure de données est une sorte de stockage dans lequel nous stockons des données pour une utilisation ultérieure. Il existe une grande variété de structures de données en programmation. Très souvent, lors de la résolution d'un problème spécifique, le plus important est de choisir la structure de données la plus adaptée à cet effet. Et vous en connaissez déjà beaucoup ! Par exemple, avec des tableaux . Et aussi avec Map(qui est généralement traduit par « dictionnaire », « carte » ou « tableau associatif »). Il est très important de comprendre : les structures de données ne sont liées à aucun langage spécifique . Ce sont simplement des « plans » abstraits selon lesquels chaque langage de programmation crée ses propres classes - implémentations de cette structure. Par exemple, l'une des structures de données les plus connues est la liste chaînée . Vous pouvez aller sur Wikipédia, découvrir comment cela fonctionne, quels sont ses avantages et ses inconvénients. Sa définition vous est peut-être familière :) « Une liste chaînée est une structure de données dynamique de base en informatique, composée de nœuds dont chacun contient à la fois les données elles-mêmes et un ou deux liens (« liens ») vers le suivant et/ou liste de nœuds précédente » Alors c'est le nôtre LinkedList! Exactement, c'est comme ça :) La structure des données de la liste chaînée est implémentée en langage Java dans la classe LinkedList. Mais d'autres langages implémentent également des listes chaînées ! En Python, il s'appelle «llist », en Scala, il s'appelle de la même manière qu'en Java - «LinkedList ». Une liste chaînée est l’une des structures de données communes de base, vous pouvez donc trouver son implémentation dans n’importe quel langage de programmation moderne. Même chose avec un tableau associatif. Voici sa définition tirée de Wikipédia : Un tableau associatif est un type de données abstrait (une interface vers un magasin de données) qui permet de stocker des paires de la forme « (clé, valeur) » et prend en charge les opérations d'ajout de paire, ainsi que la recherche. et supprimer une paire par clé. Cela ne vous rappelle rien ? :) Justement, pour nous Javanistes, un tableau associatif est une interfaceMap. Mais cette structure de données est également implémentée dans d'autres langages ! Par exemple, les programmeurs C# le connaissent sous le nom de « Dictionnaire ». Et dans le langage Ruby, il est implémenté dans une classe appelée « Hash ». En général, vous comprenez à peu près ce que cela signifie : une structure de données est une chose commune à toute programmation, qui est implémentée différemment dans chaque langage spécifique. Aujourd'hui, nous allons étudier deux de ces structures et voir comment elles sont implémentées en Java : la pile et la file d'attente.

Pile en Java

Une pile est une structure de données connue. C'est très simple et pas mal d'objets de notre vie quotidienne sont « implémentés » sous forme de pile. Imaginez une situation simple : vous vivez dans un hôtel et dans la journée vous recevez des lettres commerciales. Comme vous n'étiez pas dans la chambre à ce moment-là, l'employé de l'hôtel a simplement déposé les lettres entrantes sur votre table. Il posa d’abord la première lettre sur la table. Puis le deuxième est arrivé et il l’a mis par-dessus le premier. Il plaça la troisième lettre arrivée au-dessus de la deuxième, et la quatrième au-dessus de la troisième. Maintenant, répondez à une question simple : quelle lettre lisez-vous en premier lorsque vous arrivez dans votre chambre et voyez une pile sur la table ? C'est vrai, vous lirez la lettre du haut. C’est-à-dire celui qui est arrivé en dernier dans le temps . C'est exactement ainsi que fonctionne une pile. Ce principe de fonctionnement est appelé LIFO – « last in - first out » (« dernier entré, premier sorti »). A quoi peut servir une pile ? Par exemple, vous créez une sorte de jeu de cartes en Java. Un jeu de cartes repose sur la table. Les cartes jouées sont défaussées. Vous pouvez implémenter à la fois le deck et la défausse en utilisant deux piles. Les joueurs piochent les cartes du haut du paquet – le même principe que pour les lettres. Lorsque les joueurs défaussent des cartes, de nouvelles cartes sont placées sur les anciennes. Voici à quoi ressemblerait la première version de notre jeu, implémentée à l'aide d'une pile :

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Comme nous l'avons dit plus tôt, nous avons deux piles : le paquet et la défausse. La structure de données de la pile est implémentée en Java dans le java.util.Stack. Dans notre jeu de cartes, il existe 3 méthodes qui décrivent les actions des joueurs :

• prendre une carte du jeu (méthode getCardFromDeck());
• défausser la carte (méthode discard());
• regardez la carte du haut (méthode lookTopCard()). Disons qu'il s'agira de la mécanique bonus « Intelligence », qui permettra au joueur de savoir quelle carte entrera en jeu ensuite.

A l'intérieur de nos méthodes, les méthodes de classe sont appeléesStack :

• push()— ajoute un élément en haut de la pile. Lorsque nous défaussons une carte, elle vient au-dessus des cartes précédemment défaussées ;
• pop()- supprime l'élément supérieur de la pile et le renvoie. Cette méthode est idéale pour mettre en œuvre la mécanique « le joueur pioche une carte ».
• peek()- renvoie l'élément supérieur de la pile, mais ne le supprime pas de la pile

Voyons comment notre jeu fonctionnera :

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Nous avons donc ajouté cinq cartes à notre deck. Le premier joueur en a pris 3. Quelles cartes a-t-il obtenu ? Sortie de la console :

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Faites attention à l'ordre dans lequel les cartes ont été sorties sur la console. La carte « Edwin Van Cleiff » était la dernière à arriver dans le jeu (la cinquième consécutive), et c'était la carte que le joueur prenait en premier. "Michhlaus" était l'avant-dernier sur le jeu, et son joueur l'a pris en deuxième position. "Sylvanas" a frappé le jeu en troisième position depuis la fin et est allé au troisième joueur. Ensuite, le joueur défausse ses cartes. Il laisse d'abord tomber Edwin, puis Millhouse, puis Sylvanas. Après quoi nous sortons une à une vers la console les cartes qui sont dans notre défausse : Sortie vers la console :

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

Et encore une fois, nous voyons comment fonctionne la pile ! La défausse dans notre jeu est aussi une pile (tout comme le deck). "Edwin Van Clyffe" fut le premier à être abandonné. Le deuxième à être abandonné était "Millhouse Manastorm" - et se trouvait sur Edwin dans la défausse. Ensuite, Sylvanas a été défaussée - et cette carte se trouvait au-dessus de Millhouse. Comme vous pouvez le constater, le fonctionnement de la pile n’a rien de compliqué. Cependant, il est nécessaire de connaître cette structure de données - elle est souvent posée lors des entretiens et des structures de données plus complexes sont souvent construites sur cette base.

File d'attente

Une file d'attente (ou, en anglais, « Queue ») est une autre structure de données courante. Tout comme une pile, il est implémenté dans de nombreux langages de programmation, dont Java. Quelle est la différence entre une file d’attente et une pile ? Sa file d'attente n'est pas basée sur LIFO, mais sur un autre principe - FIFO (« premier entré - premier sorti », « premier entré - premier sorti ») . C'est facile à comprendre, en prenant comme exemple... ou du moins une vraie file d'attente ordinaire de la vraie vie ! Par exemple, une file d'attente au magasin. S'il y a cinq personnes en file d'attente, la première personne en file entrera dans le magasin . Si une personne supplémentaire (en plus des cinq en file d'attente) veut acheter quelque chose et fait la queue, alors elle entre dans le magasin en dernier , c'est-à-dire en sixième. Lorsque vous travaillez avec une file d'attente, de nouveaux éléments sont ajoutés à la fin, et si vous souhaitez obtenir un élément, il sera repris depuis le début. C'est le principe de base de son fonctionnement, qu'il faut retenir.Le principe de la file d'attente est très simple à comprendre intuitivement, puisqu'on le rencontre souvent dans la vraie vie. Il convient de noter séparément qu'en Java, une file d'attente n'est pas représentée par une classe, mais par une interface - Queue. Mais en même temps, une file d’attente en Java est une interface qui a de nombreuses implémentations. Si l'on regarde la documentation Oracle, nous verrons que 4 interfaces différentes et une liste de classes extrêmement impressionnante sont héritées de la file d'attente :

All Known Subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All Known Implementing Classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Quelle grande liste ! Mais, bien sûr, vous n'avez pas besoin de mémoriser toutes ces classes et interfaces maintenant - votre tête pourrait exploser :) Nous n'examinerons que quelques-uns des points les plus importants et les plus intéressants. Tout d'abord, prêtons attention à l'une des quatre « sous-interfaces » de la file d'attente - Deque. Qu'a-t-il de si spécial ? Deque- C'est une file d'attente à double sens. Il étend les fonctionnalités d'une file d'attente normale en vous permettant d'ajouter des éléments aux deux extrémités (le début et la fin de la file d'attente) et de prendre des éléments des deux extrémités de la file d'attente. Le deque est largement utilisé dans le développement. Faites attention à la liste des classes de file d'attente que nous avons fournie ci-dessus. La liste est assez longue, mais y a-t-il quelque chose qui nous soit familier ?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, alors notre vieil ami est là LinkedList! Autrement dit, il implémente l'interface Queue? Mais comment peut-il faire la queue ? Après tout LinkedList, c'est une liste connectée ! C'est vrai, mais cela ne l'empêche pas d'être une file d'attente :) Voici une liste de toutes les interfaces qu'il implémente :

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Comme vous pouvez le voir, LinkedListil implémente une interface Deque- une file d'attente bidirectionnelle. Pourquoi est-ce nécessaire ? Grâce à cela, nous pouvons obtenir des éléments du début et de la fin LinkedList. Et aussi - ajoutez des éléments au début et à la fin. Voici les méthodes héritées LinkedListde l'interface Deque:

• peekFirst()— renvoie (mais ne supprime pas de la file d'attente) le premier élément.
• peekLast()— renvoie (mais ne supprime pas de la file d'attente) le dernier élément.
• pollFirst()- renvoie le premier élément de la file d'attente et le supprime.
• pollLast()- renvoie le dernier élément de la file d'attente et le supprime.
• addFirst()— ajoute un nouvel élément au début de la file d'attente.
• addLast()— ajoute un élément à la fin de la file d'attente.

Comme vous pouvez le voir, LinkedListil implémente pleinement la fonctionnalité d'une file d'attente bidirectionnelle ! Et si une telle fonctionnalité est nécessaire dans le programme, vous saurez qu'elle peut être utilisée :) Et notre conférence d'aujourd'hui touche à sa fin. Enfin, je vais vous donner quelques liens pour des lectures plus approfondies. Tout d'abord, faites attention à l'article dédié à PriorityQueue - « file d'attente prioritaire ». C'est l'une des implémentations les plus intéressantes et utiles de Queue. Par exemple, s’il y a 50 personnes qui font la queue dans votre magasin, et que 7 d’entre elles sont des clients VIP, PriorityQueuecela vous permettra de les servir en premier ! Une chose très utile, n’est-ce pas ? :) Deuxièmement, il ne serait pas superflu de mentionner encore une fois le livre de Robert Laforet « Structures de données et algorithmes en Java » . En lisant le livre, vous apprendrez non seulement de nombreuses structures de données (y compris la pile et la file d'attente), mais vous en implémenterez également beaucoup vous-même ! Par exemple, imaginez si Java n'avait pas de classe Stack. Que feriez-vous si vous aviez besoin d’une telle structure de données pour votre programme ? Bien sûr, je devrais l'écrire moi-même. En lisant le livre de Laforet, c'est souvent ce que vous ferez. Grâce à cela, votre compréhension des structures de données sera beaucoup plus large qu'en étudiant simplement la théorie :) Nous en avons fini avec la théorie pour aujourd'hui, mais la théorie sans la pratique n'est rien ! Les problèmes ne se résoudront pas d’eux-mêmes, il est donc temps de les résoudre ! :)