Avec ces méthodes importantes expliquées, jetons un coup d’œil à l’implémentation finale de notre classe de pile:
Les méthodes push et pop apparaissent exactement comme prévu (lignes13-32). Nous pouvons utiliser notre méthode push pour créer un initialiseur personnalisé avec des valeurs variadiques (lignes 7 à 11). De plus, nous pouvons vérifier une pile vide en vérifiant si notre rootNode a une valeur (lignes 34-36) et dispose d’une méthode d’impression de base qui parcourt notre liste tant qu’il est capable d’accéder aux nœuds via la propriété suivante (lignes 38-44).
Un test de base de notre fonctionnalité de pile ressemble à ceci:
Savoir comment implémenter une pile est une chose, mais encore plus important est de reconnaître les situations pour lesquelles une pile est bien adaptée. Dans cette section suivante, nous examinerons trois cas de ce type.
Cas d’utilisation 1: Inverser l’ordre
Comme l’ordre d’une pile est fixe, l’ordre inverse peut être obtenu très facilement en détachant des éléments d’une pile et immédiatement sur une autre. Pas de déconner avec l’échange d’index!
Cas d’utilisation 2: Tester la symétrie
Un autre bon cas d’utilisation pour les piles est de tester la symétrie. Dans l’exemple ci-dessous, nous testons une chaîne de supports pour nous assurer que chaque support de fermeture est la contrepartie correcte d’un support d’ouverture antérieur.
Nous commençons par vérifier que le nombre de caractères est divisible par deux comme un nombre impair de caractères le serait immédiatement par asymétrique (ligne 6). Ensuite, nous vérifions que nous avons une entrée valide en définissant un jeu de caractères de caractères illégaux, puis en vérifiant que notre chaîne d’entrée a une plage de caractères illégaux nulle (lignes 7 à 8). Pour vérifier que nos crochets de fermeture et d’ouverture correspondent, nous les mettons dans un dictionnaire sous forme de paires clé-valeur (ligne 10). Dans d’autres situations, vous pouvez calculer la valeur inverse sans avoir à stocker des paires dans un dictionnaire. Ensuite, nous avons notre pile (ligne 11). Le but de notre pile dans ce cas est de stocker les supports d’ouverture. Au fur et à mesure que nous parcourons notre chaîne, nous pouvons vérifier si notre caractère est un crochet d’ouverture en testant s’il s’agit d’une clé dans notre dictionnaire. Si c’est le cas, nous le poussons sur notre pile. Une fois que nous avons trouvé notre première parenthèse fermée, nous savons que nous travaillons à travers la seconde moitié de notre modèle, nous mettons donc notre première demi-booléenne sur false (ligne 12). Si nous trouvons d’autres crochets d’ouverture après ce point, nous pouvons vérifier le booléen et indiquer un test échoué. Pour chaque support de fermeture, nous sautons le dernier support d’ouverture et vérifions s’il s’agit d’une paire clé-valeur correcte. Encore une fois, nous n’avons besoin de parcourir la chaîne qu’une seule fois, nous obtenons donc beaucoup de valeur d’un algorithme linéaire.
Cas d’utilisation 3 : Annuler les commandes
Enfin, nous utiliserons une pile en conjonction avec le modèle de commande, pour créer un historique d’annulation. Pour commencer, jetons un coup d’œil à un simple objet de compte bancaire. Il a un solde et une limite de découvert et quelques méthodes simples pour déposer et retirer des fonds:
Au lieu d’appeler directement les méthodes de dépôt et de retrait, nous pouvons stocker les informations pertinentes dans une commande. Dans l’extrait ci-dessous, nous spécifions le type d’action que nous voulons effectuer avec une propriété enum (dépôt ou retrait) et un montant. Nous stockons également un booléen pour indiquer si la commande a pu être exécutée (lignes 4 à 11). Notez que si la demande de retrait dépasse la limite de découvert, rien ne se passera sur le compte bancaire et le booléen réussi restera faux, sinon il deviendra vrai une fois la commande terminée (lignes 18 à 26). Nous avons deux méthodes pour appeler ou annuler la commande, chacune prenant un compte bancaire comme argument (lignes 18 & 28). Ces méthodes prennent le compte bancaire et appellent ses méthodes d’instance que nous avons vues dans l’extrait précédent.
En revenant au compte bancaire, nous pouvons maintenant introduire notre propriété commandStack, qui a été initialisée avec notre BankAccountType (ligne 47). Nous marquons nos méthodes de dépôt et de retrait comme fileprivate afin qu’elles ne soient accessibles que par notre commande de compte bancaire (lignes 62 & 66). Nous avons maintenant deux méthodes exposées : process(command:) et undoLastCommand(). Le premier accepte une commande en entrée, l’exécute avec le compte bancaire en entrée, puis pousse la commande sur la pile. Pendant ce temps, la méthode undoLastCommand supprime la dernière commande de la pile et effectue une annulation (lignes 51 à 60).
C’est un modèle très simple et très puissant. Les applications possibles sont infinies et offrent une expérience utilisateur satisfaisante.
Et maintenant, voyons le modèle en action:
Résumé
Dans cet article, nous avons exploré le concept de pile et de comportement LIFO. Nous avons implémenté notre propre pile à l’aide d’une liste doublement chaînée et démontré comment elle alloue et désalloue la mémoire à mesure que la taille de la pile change. Nous avons également examiné trois cas d’utilisation courants pour les piles: inverser, tester la symétrie et annuler. Chacune de ces trois situations se présente un nombre incalculable de fois dans des projets du monde réel. J’espère que vous penserez à une pile comme une structure appropriée pour gérer ces besoins. Comme toujours, merci d’avoir lu!