File et pile

Exercices ou programmes  corrigés (avec solution) sur la manipulation des files et des piles  avec le langage de programmation Python. Chaque solution/correction est enrichi par des commentaire explicatif pour rendre la correction plus claire.




Les primitives d'une pile: LIFO

Les primitives d'une piles ou les opérations caractéristiques d’une pile sont :
  • creer_pile( ): qui permet de créer et retourner une pile
  • pilevide( P ) : Retourne True si la pile est vide et False sinon
  • empiler( P , e ) : Ajouter l’élément e au somme de la pile P
  • depiler ( P ) : supprimer l’élément du sommet
  • sommet( P ) : Retourne l’élément du sommet de la pile
  • taille( P ) : Retourne la taille de la pile P
Implémentation des ces primitives seront réalisées en utilisant les listes.

Les primitives d'une file d'attente : FIFO

Les primitives d'une file d'attente (FIFO: First In/First Out, c'est-à-dire «premier arrivé, premier servi») ou les opérations caractéristiques d’une file d'attente sont  :
  • creer_file( ): qui permet de créer et retourner une file
  • filevide( F ) : Retourne True si la file est vide et False sinon
  • enfiler( F , e ) : "appelé aussi Enqueue" permet d'ajouter l’élément e à la fin de la file F
  • defiler ( F ) : "appelé aussi Dequeue" permet de renvoie le premier élément de la file et le retire
  • tete( F ) : Retourne le premier élément de la file F.
  • taille( P ) : Retourne la taille de la file P
Implémentation des ces primitives en langage Python seront réalisées en utilisant les listes.

Copier une file d'attente

Fonction Python copier_file( F ) qui retourne la copie de F en utilisant les primitive d'une file, F est une file passée en paramétré.



Copier une pile

Fonction Python copier_pile( F ) qui retourne la copie de la pile P en utilisant les primitive d'une pile, P est une pile passée en paramétré.


Renverser une file d'attente

Fonction Python renverser( F ) qui retourne la file F renversée ( l’élément de la tête sera situé à la queue et ainsi de suite ) en utilisant seulement une pile P et les primitives des PILE et les primitives des FILE, F est une file d'attente passée en paramètre.

Expression bien parenthésée

Fonction Python parenthesage( expression ) qui retourne True su l'expression est bien parenthésée et False sinon en utilisant des piles, l'expression est sous forme une chaîne de caractère passée en argument est ou non bien parenthésée en utilisant les piles Avec les parenthèses ( et ) une expression est bien parenthésée si :
  • Il ne contient aucune parenthèse ’(’ ou ’)’, ou
  • Il est de la forme ’(mot)’ avec expression est une expression bien parenthésée, ou
  • Il est la concaténation de 2 expressions bien parenthésées.


Permutation circulaire d'une file d'attente

Fonction Python PermutationCirculaireFile ( F , n ) qui utilise les primitives d'une file et qui modifie la file F de telle sorte que l’élément en position i se retrouve en position i +n  (c’est à dire que le premier se retrouve en position n +1, si n est plus petit que la longueur de q, le deuxième en position n +2, ... et le dernier en position n).

Permutation circulaire d'une pile

Fonction Python PermutationCirculairePile ( P , n ) qui utilise les primitives d'une pile et qui modifie la pile P de telle sorte que l’élément en position i se retrouve en position i +n  (c’est à dire que le premier se retrouve en position n +1, si n est plus petit que la longueur de q, le deuxième en position n +2, ... et le dernier en position n).

Notation polonaise inversé ou post-fixée

Fonction Python PolonaiseInverse( expression ) qui permet d'évaluer des expressions écrites en polonaise inversée. La notation polonaise inversée ou post-fixée permet de noter les formules arithmétiques sans utiliser de parenthèses. expression est une chaine de caractère sous forme notation polonaise inversé où les nombres ainsi les opérations sont séparés par des espaces. Exemples:
  • la forme polonaise de m'expression (21 + 13)  * 40 est 21  13  +  40  *
  • la forme polonaise de m'expression 10 + (31   * 4 ) est 10  31  4  +  +
  • la forme polonaise de m'expression  ( 3 + ( 5 * ( 7 + 2 ))) + ( 4 + ( 8 * 9 )) est  3  5  7  2  +  *  +  4  8  9  *  +  +