Structures de données — Pile

En programmation, nous devons travailler avec beaucoup, beaucoup de données. Par conséquent, nous devons stocker et organiser les données de manière efficace. C'est à ce moment que les structures de données deviennent utiles. Nous pouvons utiliser des structures de données pour stocker, organiser, traiter et récupérer des données. Les structures de données peuvent être divisées en 2 catégories en fonction de la manière dont les données sont organisées.

Dans cet article, je vais parler de structures linéaires ( Stacks ). Par rapport aux structures non linéaires, les concepts sous-jacents aux structures linéaires sont relativement plus faciles à saisir. Quelques exemples de ces structures linéaires sont Stack, Queues, Deques et Lists. Nous allons parcourir chacune de ces structures de données une par une. Ces structures linéaires peuvent être considérées comme ayant 2 extrémités. (avant et arrière | gauche et droite | haut et bas) Certaines structures linéaires permettent l'insertion ou le retrait d'éléments à une seule extrémité, tandis que certaines structures le permettent à chaque extrémité.

1. Piles

• Donc, fondamentalement, une pile est une collection ordonnée d'éléments où l'insertion et la suppression d'éléments ont lieu à la même extrémité. Cette extrémité est communément appelée « Top ». De plus, l'extrémité opposée au sommet est connue sous le nom de "Bas"
• De plus, les éléments les plus récents se trouvent près du haut, tandis que les plus anciens se trouvent près du bas. Par conséquent, l'ordre de retrait des éléments de la pile sera l'inverse de l'ordre d'insertion des éléments dans la pile.
• Maintenant que nous avons une bonne compréhension du comportement d'une pile, examinons quelques opérations importantes liées à la structure de données de la pile.
• push (element) — La méthode push est utilisée pour insérer un élément en haut de la pile.
• pop () - La méthode pop est utilisée pour supprimer le haut - la plupart des éléments de la pile
• peek () - La méthode Peek est utilisée pour voir l'élément actuel le plus haut de la pile.
• size () — Renvoie le nombre d'éléments présents sur la pile
• is_empty () — Cette méthode est utile pour vérifier si la pile est vide ou non
• Notez qu'ici, la fin de la liste est considérée comme le sommet de la pile. (Complexité temporelle — O(1)) Nous pouvons considérer que le début de la liste est le sommet de la pile, cependant, cela ne serait pas très efficace car la complexité temporelle serait O(n) lorsque nous poussons ou détachons des éléments.
• Quand on considère que la fin de la liste est le haut de la pile


• Maintenant que nous savons comment implémenter une pile, examinons maintenant certains scénarios où l'utilisation de la structure de données de la pile devient vitale.
• Conversions du système de numération
• Tout d'abord, voyons comment convertir un nombre décimal en binaire à l'aide d'une pile.

• Étendons maintenant l'algorithme ci-dessus pour convertir un nombre décimal dans n'importe quel système de nombres compris entre 2 et 16.


Presque tous les langages de programmation utilisent des parenthèses dans leur syntaxe. Par conséquent, si nous n'utilisons pas les parenthèses de manière équilibrée, une erreur de syntaxe pourrait se produire.

• Dans la première étape de ce problème, je ne considérerai qu'un seul type de parenthèses, disons (). Ce que nous devons vérifier, c'est si l'ensemble des parenthèses est équilibré ou non. Si équilibré, nous devrions retourner vrai, sinon faux.
• ( ) — équilibré | ( ( ) ) — équilibré | ( ( ( )( ) ) ) — équilibré
• ( ( ) non équilibré | ( ) ( ) ( — non équilibré | ( ( ( ) ) ( ) — non équilibré

• ( [ ] ) — équilibré | ( ( ) { } ) — équilibré | ( ( [ { } [ ] ] ) ) — équilibré
• ( ( ) non équilibré | ( ) { } ]— non équilibré | ( ( { } [ [ ) — non équilibré


3. Inverser une chaîne à l'aide d'une pile



4. Infixe | Notation postfixe et préfixe

En informatique, nous devons faire face à de nombreuses expressions arithmétiques. Une expression se compose d'opérateurs (+, -, *, / etc) d'opérandes (A, B, c, d, 1, 2,… ) et de symboles tels que des parenthèses.

• Notation infixe — Dans cette notation, l'opérateur est placé entre les opérandes. (<opérande> <opérateur> <opérande>)
• Si l'expression se compose d'un seul opérateur (ex : 2 + 3, 4 * 6) nous pouvons résoudre l'expression tout de suite. Cependant, si l'expression a plus d'un opérateur, nous ne pouvons pas la résoudre directement en raison de l'ambiguïté de l'expression. Considérez cette expression 1 + 4 * 5. Si nous faisons d'abord l'addition, nous obtenons la réponse sous la forme [ ( 1 + 4 ) * 5 ] = 25 et si nous effectuons d'abord la multiplication, nous obtenons la réponse sous la forme [1 + (4 * 5 )] = 21. Comme vous pouvez le voir, il y a une certaine ambiguïté dans cette notation. Par conséquent, pour résoudre ce problème, nous utilisons quelque chose appelé "précédence des opérateurs". Selon la priorité de l'opérateur, la multiplication doit être effectuée avant l'addition. La bonne réponse devrait donc être 21 et non 25.
• Fondamentalement, pour résoudre une expression écrite en notation infixe, nous devons suivre un ensemble de règles, ainsi que nous devons également ajouter des parenthèses. Cette notation pourrait donc prendre plus de mémoire lors de la résolution. Donc, pour surmonter ces défis, les scientifiques ont proposé deux autres notations, préfixe et suffixe.
• En notation préfixée, l'opérateur est placé avant les opérandes, (<opérateur><opérande> <opérande>) alors qu'en notation postfixée l'opérateur est placé après les opérandes. (<opérande> <opérande><opérateur>)
• Par rapport à la notation infixe, les deux autres notations sont assez difficiles à lire et à comprendre pour un humain. Cependant, comme ces deux notations n'ont pas de symboles supplémentaires tels que des crochets et ne contiennent aucune ambiguïté, les expressions écrites dans ces 2 formats peuvent facilement être lues par des ordinateurs.


• Évaluation d'une expression postfixée : Lorsque nous devons évaluer une expression postfixée, nous devons commencer le balayage à partir de la gauche jusqu'à ce que nous trouvions un opérateur. Une fois que nous avons trouvé un opérateur, nous devons effectuer l'opération algébrique appropriée sur les 2 premiers opérandes à gauche de l'opérateur.

• Tout d'abord, nous devons supprimer tous les espaces dans notre entrée. Nous devons donc utiliser la méthode de fractionnement. Ensuite, nous devons balayer notre expression de gauche à droite. Si nous rencontrons un nombre, nous devons le pousser dans la pile. Si nous rencontrons un opérateur, nous devons faire apparaître 2 des éléments les plus élevés de notre pile. Ensuite, nous devons appeler notre fonction d'assistance pour effectuer l'opération arithmétique. Après cela, nous pousserons le résultat dans la pile. Une fois que nous aurons terminé l'analyse, nous renverrons ce qui reste dans notre pile, qui est la réponse pour l'expression postfixée évaluée.


• Voyons maintenant comment convertir une expression au format infixe en suffixe en utilisant Python.