Structures de données

1 ) Les piles

Une pile est une structure de données qui permet d'accéder en premier à la dernière donnée ajoutée ; on peut imaginer une pile de dossiers ou une pile d'assiettes, l'objet situé au sommet de la pile sera le premier à être sorti :
On parle de structure ou de pile LIFO (stack en anglais). LIFO est l'abbréviation de Last In First Out (dernière donnée entrée , première donnée sortie).

Ci dessous des liens vers des vidéos permettant d'asseoir les connaissances :

* D'abord une présentation générale des Piles et Files
* Comprendre la structure de données de la pile LIFO

Voici les opérations que l'on peut réaliser sur une pile :

• on peut créer une pile vide                                                      ( creer_pile_vide() retourne un objet de type pile)
• on peut savoir si une pile est vide                                            (pile_vide(P) retourne un booléen)
• on peut empiler un nouvel élément sur la pile (push)                 (empiler (P,e)insère un élément au sommet de la pile)
• on peut récupérer l'élément au sommet de la pile tout en le supprimant.
  on dit que l'on dépile (pop)                                                      (dépiler (P)retourne l'élément qui est au sommet de la pile et l'enlève de la pile)
• on peut accéder à l'élément situé au sommet de la pile sans le supprimer de la pile (top)        (sommet (P)renvoie l'élémént du dessus)
• on peut connaitre le nombre d'éléments présents dans la pile (size)                                      (taille(P)renvoie le nombre d'éléménts de la pile)
• on peut savoir si une pile est pleine                                         (pile_pleine(P) retourne un booléen)

Exemples :

Voici une série d'instructions (les instructions ci-dessous s'enchaînent):

• P=creer_pile_vide() => on a créé une pile vide
• pile_vide(P) => renvoie vrai
• empiler (P,3) => La pile P contient maintenant l'élément 3
• pile_vide(P) => renvoie faux
• empiler (P,2) => La pile P contient maintenant les éléments 2 et 3
• N = dépiler (P) => la variable N vaut 2, la pile contient l'élément 3 ; 2 disparait de la pile
• empiler (P,5) => La pile P contient maintenant les éléments 5 et 3
• empiler (P,7) => La pile P contient maintenant les éléments 7,5 et 3
• empiler (P,9) => La pile P contient maintenant les éléments 9,7,5 et 3
• pile_vide(P) => renvoie faux

Exercice 1

Soit une pile P composée des éléments suivants : 12, 10, 8, 7, 13 et 25 (le sommet de la pile est 25) Pour chaque exemple ci-dessous on repart de la pile d'origine :

• que renvoie pop(P) ? que contient la pile P après ce pop ? quel est le sommet de la pile ?
• donner la composition de la pile après push(P,63) ?
• que renvoie top(P) ?
• si on applique pop(P) 6 fois de suite, que renvoie pile_vide(P) ?
• Après avoir appliqué pop(P) une fois, que renvoie size(P) ?

En python

Si (P[0]== 1), la pile est vide et on augmente P[0] d'une unité à chaque fois qu'on insère un élément, la première case permet de connaitre le nombre d'éléments présents dans la pile
Si (P[0]== n+1), la pile est pleine et on diminue P[0] d'une unité à chaque fois qu'on enlève un élément .
Pour implémenter une PILE en python, on peut utiliser un code comme celui-ci :

Exercice 2