La structure de données de la pile

Bienvenue dans un autre tutoriel sur les structures de données. Dans ce 4ème épisode de la série, nous allons jeter un œil à notre première structure de données complexe - la pile. Ne vous inquiétez pas! Ce n'est pas vraiment compliqué. Il s'appuie simplement sur notre connaissance des listes chaînées. Donc, si vous n'êtes pas familier avec les listes liées, c'est probablement le bon moment pour les revoir.

Qu'est-ce qu'une pile ?

Si nous repensons à notre leçon sur les méthodes, nous nous souviendrons que Java stocke les appels de méthode sur la pile. Mais qu'est-ce qu'une pile exactement ? Comme son nom l'indique, une pile est une structure de données qui ressemble à une pile d'éléments. Nous pouvons y penser comme une pile de papiers ou une pile de crêpes. En effet, une pile nous permet uniquement d'ajouter ou de supprimer des éléments du haut. Par conséquent, les piles ne prennent en charge que deux opérations :pop et push.

Comme nous pouvons probablement l'imaginer, l'opération de poussée consiste à placer un nouvel élément au sommet de la pile. Pendant ce temps, l'opération pop effectue le contraire. Ces deux fonctionnalités suffisent à elles seules pour créer une pile. Cependant, certaines piles ont des fonctionnalités supplémentaires telles que Peek, qui nous permettent de vérifier le nœud supérieur sans avoir à le retirer du haut.

Propriétés des piles

Les piles sont essentiellement des listes liées à des cas particuliers (bien qu'elles puissent être implémentées à l'aide de tableaux). En d'autres termes, nous gardons la même structure d'une liste chaînée, mais nous n'exposons que pop et push. En conséquence, nous ne pouvons pas traverser une pile. Au lieu de cela, nous interagissons avec la structure de données exclusivement via l'élément supérieur.

Restreindre une liste liée nous donne de nouvelles propriétés assez intéressantes. D'une part, une pile est une structure de données dernier entré, premier sorti (LIFO). Cette structure nous permet de garder une trace de l'état d'un système de manière récursive. Par exemple, Java utilise des accolades pour définir des blocs de code. Cependant, nous imbriquons parfois plusieurs niveaux avant de fermer un bloc. Si nous voulons suivre ces accolades, nous pourrions intuitivement penser que nous pouvons simplement compter le nombre d'accolades ouvertes et fermées. Si les chiffres correspondent, nous sommes bons. Malheureusement, ce genre de méthode échouerait. Après tout, démarrer un programme avec une accolade fermante est une erreur de compilation.

Au lieu de cela, nous pouvons suivre les accolades à l'aide d'une pile. Chaque fois que nous rencontrons une accolade ouverte, nous la posons sur le dessus. Si nous rencontrons une accolade fermée, nous jetons un coup d'œil en haut pour toutes les accolades ouvertes. S'il en existe un, nous le retirons et continuons. Sinon, nous savons que nous avons une erreur de compilation ! 🙂

Applications des piles

En raison de la nature récursive de la pile, nous avons quelques applications amusantes pour eux. L'exemple classique est l'inversion d'une chaîne. Nous poussions simplement chaque lettre sur le coin, puis nous les ressortions. Ce comportement d'inversion est en fait utile si nous voulons inverser l'état d'un système. Pensez à annuler . En fait, la commande d'annulation universelle (ctrl + z) est probablement implémentée à l'aide d'une pile.

Nous pouvons également utiliser une pile pour implémenter le retour en arrière. Pensez à la traversée du labyrinthe. Dans un labyrinthe, nous commençons par stocker chaque mouvement sur une pile. Finalement, nous allons manquer de mouvements. Si le labyrinthe n'est pas résolu à ce stade, nous revenons en arrière jusqu'à ce que nous atteignions un endroit où nous avons des mouvements inutilisés. Ce processus continuerait jusqu'à ce que nous ayons résolu le labyrinthe.

Bien sûr, les compilateurs font un usage intensif des piles pour faire correspondre les accolades. Cela s'applique particulièrement aux langages comme Java et C/C++ qui utilisent des accolades pour signifier les blocs de code.

Syntaxe de la pile Java

Comme les listes chaînées, Java prend également en charge la structure de données Stack. Les piles se présentent sous deux formes principales :statique et dynamique. Nous pouvons vraiment considérer ces deux implémentations comme des tableaux ou des listes chaînées. Pour les besoins de ce didacticiel, notre pile sera implémentée sous la forme d'une liste chaînée (alias dynamique). Pour plus d'informations sur les piles statiques, n'hésitez pas à consulter cette implémentation d'un ArrayStack en Java.

Définition de classe

Parce qu'une pile est vraiment une liste chaînée déguisée, la définition de la classe va sembler assez similaire.

public class Stack {
  private Node top;
}

Et c'est à peu près tout. Notez que nous masquons en fait le nœud supérieur. Nous souhaitons uniquement exposer push et pop dans le but d'encapsuler la structure sous-jacente de la liste chaînée.

La classe Node que nous utilisons est le même nœud de la dernière leçon. Cela ne fonctionnera qu'avec des entiers car les types génériques sont encore un peu hors de portée. Cependant, nous y reviendrons bien assez tôt !

Insertion

Comme indiqué précédemment, il n'y a vraiment qu'une seule façon d'effectuer une insertion sur une pile. Cela s'appelle une poussée. Une poussée est clairement une opération à temps constant. Nous insérons simplement un nœud au début de la liste et réinitialisons la tête.

public void push(int value) {
  this.top = new Node(value, this.top);
}

Avec cette méthode, nous pouvons pousser les valeurs au sommet de la pile pour toujours. Lorsque nous voulons commencer à le nettoyer, nous aurons besoin d'une implémentation de pop.

Suppression

Étant donné que les piles sont si simples, il est logique de montrer au moins un autre élément de syntaxe :la suppression. Comme l'insertion, la suppression est une opération à coût fixe que nous appelons pop.

public int pop() {
  if (this.top != null) {
    Node toRemove = this.top;
    this.top = this.top.getNext();
    return toRemove.getPayload();
  } else {
    throw new NoSuchElementException();
  }
}

Dans le cas où la pile est vide, nous levons une exception. Sinon, nous supprimons le nœud et renvoyons l'élément à l'utilisateur.

Résumé

C'est à peu près tout ce que nous avons pour les piles. Comme toujours, voici la répartition des opérations de structure de données typiques et leurs estimations Big O. Comme les listes liées, les piles fonctionnent très bien avec l'insertion et la suppression. Cependant, ils ne prennent pas vraiment en charge l'accès et la recherche. Il est possible d'implémenter ces deux fonctionnalités, mais nous aurions alors essentiellement une liste liée.

Algorithme	Durée d'exécution
Accès	O(N)
Insérer	O(1)
Supprimer	O(1)
Rechercher	O(N)

Merci d'être resté pour un autre tutoriel sur les structures de données. Ensuite, nous couvrirons la file d'attente !