Exercices TD Piles et files
Télécharger PDFIntroduction et objectifs
Dans ce TD consacré principalement aux piles (stacks) et, dans une moindre mesure, aux files (queues), on s’entraîne fondamentalement à manipuler des listes en tenant compte des contraintes imposées par les structures des piles et des files. En particulier, dans les exercices ci-dessous, on utilisera exclusivement les fonctions de création et manipulation de piles et de files vues en cours et présentes dans le fichier StackQueue_lib.py.
Piles
Remarque : les fonctions des exercices 1 à 4, ainsi que d’autres de votre propre cru, pourront bien sûr être ajoutées au fichier StackQueue_lib.py.
Exercice N°1 – Copie d’une pile
Écrire une fonction stack_copy recevant une pile s comme argument et renvoyant une copie s2 de s. Attention, la pile s doit (bien sûr) être conservée ! Évaluer le coût en mémoire et le nombre d’opérations de la fonction.
Exercice N°2 – Inversion d’une pile
Écrire une fonction stack_reverse recevant une pile (s) comme argument et renvoyant une copie inversée rs de s. Attention, la pile s doit être conservée ! Évaluer le coût en mémoire et le nombre d’opérations de la fonction.
Exercice N°3 – Permutations circulaires (acte 1)
Écrire une fonction stack_circperm qui reçoit en argument une pile s et un entier n et effectue sur la pile n permutations circulaires successives. Dans cet exercice, c’est la pile s elle-même qui sera modifiée. Évaluer le coût en mémoire et le nombre d’opérations de la fonction.
Exercice N°4 – Permutations circulaires (acte 2)
Écrire une fonction stack_circperm2 qui reçoit en argument une pile s et un entier k et effectue une permutation circulaire sur les k premiers éléments de la pile. Dans cet exercice, c’est la pile s elle-même qui sera modifiée. Évaluer le coût en mémoire et le nombre d’opérations de la fonction.
Exercice N°5 – Expression correctement parenthésée
Écrire une fonction qui reçoit comme argument une chaîne de caractères, en analyse la correction du parenthésage et renvoie à l’utilisateur un message adapté. L’analyse de la chaîne de caractères se fera caractère après caractère. On gèrera une pile contenant les parenthèses ouvrantes et on comparera chaque parenthèse fermante au sommet (éventuel) de la pile.
Files
Exercice N°5 – Permutations circulaires
Reprendre les exercices 1 et 3 de la partie « Piles » mais en traitant cette fois le cas d’une file.
Suggestions de compléments
1. Les fonctions stack_circperm et stack_circperm2 peuvent être réunies en une seule. La nouvelle fonction recevra trois arguments : le nom de la pile, le nombre d’éléments sur lesquels on appliquera des permutations circulaires et, enfin, le nombre de permutations circulaires à appliquer à ces éléments.
2. En Python, les concepts de pile et de file sont généralisés via les objets deque (double ended queue) du module collections. Ce sont en quelque sorte des files modifiables à gauche et à droite. Les méthodes utilisables et de nombreux exemples se trouvent au paragraphe 8.3.2 de la documentation Python (versions 2.x) et 8.3.3 de la documentation Python (versions 3.x).
FAQ
Qu'est-ce qu'une pile en informatique ?
Une pile est une structure de données qui suit le principe LIFO (Last In, First Out), où le dernier élément ajouté est le premier à être retiré.
Qu'est-ce qu'une file en informatique ?
Une file est une structure de données qui suit le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré.
Comment évaluer le coût en mémoire et le nombre d’opérations d’une fonction ?
Pour évaluer le coût en mémoire, il faut compter le nombre d'éléments supplémentaires utilisés par la fonction. Pour le nombre d’opérations, il faut compter le nombre de fois que la fonction effectue des opérations de base comme des additions, des comparaisons, etc.