Structures de données : pile et file d'attente

Salut! Aujourd'hui, nous allons parler de quelque chose de très important pour tout programmeur : les structures de données. Wikipedia dit : « Une structure de données est un format d'organisation, de gestion et de stockage de données qui permet un accès et une modification efficaces. Plus précisément, une structure de données est un ensemble de valeurs de données, les relations entre elles et les fonctions ou opérations qui peuvent être appliquée aux données." La définition est un peu confuse, mais l'essentiel est clair. Une structure de données est une sorte de référentiel où nous stockons des données pour une utilisation future. En programmation, il existe une grande variété de structures de données. Lors de la résolution de problèmes spécifiques, le plus important est très souvent de choisir la structure de données la plus adaptée au problème. Et vous en connaissez déjà beaucoup ! Par exemple, vous connaissez les tableaux. Et vous connaissez aussiMap(cette structure de données peut également être appelée "dictionnaire" ou "tableau associatif"). Il est très important de comprendre que les structures de données ne sont liées à aucun langage particulier. Ce sont simplement des "plans" abstraits que chaque langage de programmation utilise pour créer ses propres classes ou implémentations d'une structure particulière. Par exemple, l'une des structures de données les plus connues est une liste chaînée. Vous pouvez aller sur Wikipédia et lire comment cela fonctionne et quels sont ses avantages et ses inconvénients. Peut-être que sa définition vous semblera familière :) "Une liste chaînée est une collection linéaire d'éléments de données, dont l'ordre n'est pas donné par leur emplacement physique en mémoire. Au lieu de cela, chaque élément pointe vers le suivant." Cela décrit notre bien-aimé LinkedList, n'est-ce pas ? Oui, et c'est exactement ce que c'est :) En Java, la structure de données "liste chaînée" est implémentée par la LinkedListclasse. Mais d'autres langages implémentent également des listes chaînées ! En Python, cette structure de données s'appelle " llist". Dans Scala, il s'appelle " LinkedList", tout comme en Java. Une liste liée est l'une des structures de données communes de base, vous constaterez donc qu'elle est implémentée dans n'importe quel langage de programmation moderne. Il en va de même pour les tableaux associatifs. Voici la définition de Wikipedia : "Un tableau associatif, une carte, une table de symboles ou un dictionnaire est un type de données abstrait composé d'une collection de paires (clé, valeur), de sorte que chaque clé possible apparaisse au plus une fois dans la collection." Cela ne vous rappelle rien ? :) Ouais. Pour nous développeurs Java, un tableau associatif est leMapinterface. 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 en Ruby, il est implémenté dans une classe appelée "Hash". Eh bien, vous avez compris : les structures de données sont des concepts universels en programmation, et chaque langage de programmation les implémente à sa manière. Aujourd'hui, nous allons étudier deux de ces structures - la pile et la file d'attente - et voir comment elles sont implémentées en Java.

Piles en Java

Une pile est une structure de données bien connue. C'est très simple. De nombreux éléments de notre vie quotidienne sont "implémentés" comme une pile. Imaginez cette situation simple : vous séjournez dans un hôtel et, au cours de la journée, vous recevez des lettres commerciales. Vous n'étiez pas dans votre chambre à ce moment-là, alors l'employé de l'hôtel a simplement placé les lettres entrantes sur votre bureau. D'abord, il posa la première lettre sur le bureau. Puis une seconde lettre arriva, et il la posa sur la première. Il a mis la troisième lettre au-dessus de la seconde et la quatrième au-dessus de la troisième. Et maintenant, répondez à une question simple : quelle lettre lirez-vous en premier lorsque vous reviendrez dans votre chambre et que vous verrez la pile sur la table ? À droite, vous lirez le plus hautlettre. C'est-à-dire celui qui est arrivé le plus récemment . C'est exactement comment fonctionne une pile. Ce principe est appelé "dernier entré, premier sorti" (LIFO) . A quoi servent les stacks ? Eh bien, supposons que vous créez une sorte de jeu de cartes en Java. Un jeu de cartes est posé sur la table. Les cartes jouées sont défaussées. Vous pouvez utiliser deux piles pour implémenter à la fois la pioche et la pile de défausse. Les joueurs prennent leurs cartes du haut du paquet, en suivant le même principe que pour vos lettres commerciales. Lorsque les joueurs placent des cartes dans la pile de défausse, les cartes nouvellement défaussées sont placées au-dessus des anciennes. Voici notre première tentative de jeu, implémentée sur la base d'un stack :

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 {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

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

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

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Comme nous l'avons dit plus tôt, nous avons deux piles : une pioche et une pile de défausse. En Java, la structure de données de la pile est implémentée dans la java.util.Stackclasse. Notre jeu de cartes a 3 méthodes qui décrivent les actions des joueurs :

• prendre une carte du jeu ( getCardFromDeck()méthode)
• défausser une carte ( discard()méthode)
• regardez la carte du haut ( lookAtTopCard()méthode). Disons qu'il s'agit d'un bonus "Intelligence" qui permet au joueur de savoir quelle carte viendra ensuite dans le jeu.

Dans nos méthodes, nous appelons les méthodes suivantes de la classe Stack :

• push()— ajoute un élément au sommet de la pile. Lorsque nous envoyons une carte à la pile de défausse, elle va en haut de la pile
• pop()— supprime l'élément supérieur de la pile et le renvoie. Cette méthode est parfaite pour mettre en œuvre des actions dans lesquelles 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) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

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

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Faites attention à l'ordre dans lequel les cartes sont affichées sur la console. La carte "Edwin VanCleef" est entrée dans le jeu en dernier (c'était la cinquième carte), et c'est la carte que le joueur a piochée en premier. "Millhouse" était l'avant-dernier dans le jeu et le joueur l'a pioché en deuxième. "Sylvanas" est entré dans le jeu en troisième à partir du haut, et c'est la troisième carte que le joueur a piochée. Ensuite, le joueur se défausse des cartes. D'abord, elle se débarrasse d'Edwin, puis de Millhouse, puis de Sylvanas. Ensuite, nous affichons les cartes de notre pile de défausse une par une : Sortie console :

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Encore une fois, nous voyons comment fonctionne une pile ! Dans notre jeu, la pile de défausse est aussi une pile (tout comme la pioche). "Edwin VanCleef" a été écarté en premier. La deuxième carte défaussée était Millhouse Manastorm, et elle a été placée au-dessus d'Edwin dans la pile de défausse. Ensuite, Sylvanas a été défaussé et cette carte a été placée au-dessus de Millhouse. Comme vous pouvez le voir, il n'y a rien de compliqué dans une pile. Pourtant, vous devez connaître cette structure de données - elle est souvent posée lors des entretiens d'embauche, et c'est souvent la base pour construire des structures de données plus complexes.

File d'attente en Java

Une file d'attente est une autre structure de données courante. En plus des piles, de nombreux langages de programmation, dont Java, implémentent également la structure de données de file d'attente. Quelle est la différence entre une file d'attente et une pile ? Une file d'attente n'est pas basée sur le principe LIFO, mais plutôt sur le principe FIFO ("premier entré, premier sorti"). Ce principe est facile à comprendre en considérant, par exemple, une ligne ordinaire, ou file d'attente, dans la vraie vie ! Par exemple, une ligne à l'épicerie. S'il y a cinq personnes dans la file, la première à être servie sera celle qui est entrée la première dans la file . Si une autre personne (en plus des cinq déjà en ligne) veut acheter quelque chose et fait la queue, elle est servie en dernier, c'est-à-dire sixième. Lorsque vous travaillez avec une file d'attente, de nouveaux éléments sont ajoutés à la queue (arrière) et si vous souhaitez obtenir un élément, il sera extrait de la tête (avant). C'est le principe de base dont vous devez vous souvenir concernant le fonctionnement d'une file d'attente. Le fonctionnement d'une file d'attente est très intuitif, car on retrouve souvent des files d'attente 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. De plus, il existe de nombreuses implémentations de cette interface de file d'attente en Java. Si nous regardons la documentation d'Oracle, nous verrons que 4 interfaces différentes, ainsi qu'une liste de classes extrêmement impressionnante, héritent de l'interface Queue :

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 pour le moment — 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 Queue : Deque . Qu'est-ce qui le rend si spécial? A Dequeest une file d'attente à double extrémité. Il étend la fonctionnalité d'une file d'attente régulière, vous permettant d'ajouter des éléments aux deux extrémités (en tête et en queue) et de prendre des éléments des deux extrémités de la file d'attente. Les files d'attente doubles sont largement utilisées dans le développement de logiciels. Faites attention à la liste des classes de file d'attente que nous avons fournie ci-dessus. La liste est assez longue, mais contient-elle quelque chose de familier ?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Voici notre vieil ami LinkedList! Donc, il implémente l'interface Queue ? Mais comment peut-il être une file d'attente? Après tout, a LinkedListest une liste chaîné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, LinkedListimplémente l' Dequeinterface (encore une fois, cela signifie une file d'attente à double extrémité). Pourquoi est-ce nécessaire ? Cela nous permet d'obtenir des éléments du début et de la fin d'un fichier LinkedList. Cela nous permet également d'ajouter des éléments au début et à la fin. Voici les méthodes qui LinkedListproviennent de l' Dequeinterface :

• peekFirst()— renvoie le premier élément (mais ne le supprime pas de la file d'attente).
• peekLast()— renvoie le dernier élément (mais ne le supprime pas de la file d'attente).
• 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, LinkedListimplémente pleinement la fonctionnalité d'une file d'attente à double extrémité ! Et vous avez besoin d'une telle fonctionnalité dans votre programme, vous saurez où la trouver :) La leçon d'aujourd'hui touche à sa fin. En conclusion, je vais vous donner quelques liens pour une lecture supplémentaire. Tout d'abord, faites attention à cet article sur PriorityQueue . C'est l'une des Queueimplémentations les plus intéressantes et les plus utiles. Par exemple, supposons qu'il y ait 50 personnes faisant la queue dans votre magasin, dont 7 sont des clients VIP. Une file d'attente prioritaire vous permettra de les servir en premier ! Des trucs très utiles, non? :) Deuxièmement, cela ne ferait pas de mal de mentionner à nouveau le livre de Robert Lafore "Data Structures and Algorithms in Java". En lisant ce 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, que se passerait-il 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 ? Vous auriez à l'écrire vous-même, bien sûr. En lisant le livre de Lafore , vous ferez souvent exactement cela. En conséquence, votre compréhension des structures de données sera beaucoup plus profonde que ce que vous obtiendriez d'une simple étude de la théorie :) Nous terminons la théorie pour aujourd'hui, mais la théorie sans pratique n'est rien ! Les tâches ne se résolvent pas d'elles-mêmes, il est donc temps de s'y attaquer ! :)