Reprendre la fonction $enfiler()$ de la propriété où elle a été implémentée et y ajouter les erreurs de dépassements d'écritures.

On suppose que la structure de données Pile a été implémentée en Python.
On munit les piles du même jeu d'instructions qu'à l'exercice précédent.

Voici une suite d'instructions :

P1=vide()
P2=vide()
P3=vide()
for i in range(12):
    empiler(i,P1)
for j in range(3):
    empiler(depiler(P1),P2)
    depiler(P1)
    empiler(depiler(P1),P3)
                

Que contiennent les piles P1, P2 et P3 à l'issue de l'exécution de la suite d'instructions précédente ?

On rajoute au jeu d'instructions précédent sur les piles la fonction est_vide qui prend en paramètre une pile et renvoie le booléen True si la pile donnée en argument est vide et False sinon.

1. En utilisant les quatre instructions autorisées sur les piles, proposer une fonction hauteur, qui prend en paramètre une pile et renvoie l'entier naturel correspondant au nombre d'élément de la pile entrée comme argument.
   Attention ! Faire en sorte que le contenu de la pile saisie comme argument ne soit pas modifié à l'issue de l'exécution de la fonction hauteur.

   Code de déblocage de la correction :

2. De même, proposer une fonction renverser qui prend en paramètre une pile et renvoie une pile formée des mêmes éléments que la pile saisie comme argument mais dont l'ordre est inversé.
   Faire aussi en sorte que la pile saisie comme argument ne soit pas modifiée à l'issue de l'exécution de cette fonction renverser.

   Code de déblocage de la correction :

Implémentation d'une file à l'aide de deux piles

Dans cet exercice, on choisit d'implémenter une file file à l'aide de d'un couple (entree,sortie) où entree et sortie sont deux piles.
Ainsi file[0] correspond à entree et file[1] à sortie.

Par exemple la file ci-contre :
peut être implémentée par les deux piles suivantes :
tout comme par les deux piles suivantes :

Voici le fonctionnement de cette file :

1. la pile entree contient les éléments que l'on insère dans la file tandis que la pile sortie contient les éléments que l'on retire de la file.

2. la file est vide lorsque les deux piles entree et sortie sont vides.

3. enfiler un nouvel élément elt dans la file revient à empiler cet élément dans la pile entree.

   Voici une illustration de enfiler(elt,file) :

4. defiler un élément de la file, il faut que celle-ci ne soit pas vide. Alors, deux cas se présentent :

   1. la pile sortie n'est pas vide : on dépile cette pile sortie,

      Voici une illustration de defiler(file) dans ce cas :

   2. la pile sortie est vide : on dépile alors les éléments de la pile entree un à un en les empilant dans la pile sortie jusqu'à ce que entree soit vide ; ensuite, on dépile un élément de la pile sortie.

      Voici une illustration de defiler(file) dasn ce cas :

1. On suppose que la file file est dans l'état correspondant à la figure suivante :

   On exécute la séquence d'instructions suivantes :

   enfiler(1,file)
   defiler(file)
   defiler(file)
   enfiler(2,file)
   defiler(file)

   Représenter le contenu final des deux piles représentant la file file à la suite de ces instructions.

2. A la suite des instructions déjà effectuées précédemment, on exécute la séquence d'instructions suivantes :

   defiler(file)
   enfiler(3,file)
   enfiler(defiler(file),file)

   Représenter le contenu final des deux piles représentant la file file à la suite de ces instructions.

3. On suppose disposer des fonctions suivantes écrite en langage Python :

   • empiler(elt,pile) qui empile l'élément elt sur la pile pile,

   • depiler(pile) qui dépile le sommet de la pile pile, si elle n'est pas vide, et renvoie ce sommet,

   • pile_vide(pile) qui renvoie le booléen True si la pile pile est vide et False sinon.

   1. Écrire en langage Python une fonction est_vide(file) qui prend en argument une file file constituée d'un couple de piles et qui renvoie True si la file file est vide et False sinon.

   2. Écrire en langage Python une fonction enfiler(elt,file) qui prend en argument un entier elt et une file file constituée d'un couple de piles et qui ajoute elt en queue de la file file.

   3. Écrire en langage Python une fonction defiler(file) qui prend en argument une file file, supposée non vide, constituée d'un couple de piles et qui renvoie l'élément en tête de la file file en en le retirant.

Il est possible d'implémenter une pile sous forme d'une liste Python en utilisant la méthode append() pour empiler et celle pop() pour dépiler le sommet.

Programmer les trois fonctions empiler(elt,pile), depiler(pile) et pile_vide(pile) de l'exercice précédent en implémentant une pile comme une liste Python.