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) dans 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.