Structures de données linéaires

Rédigez l'interface (le contrat) d'une pile d'entiers : pour chaque opération, donnez sa signature, son effet et, le cas échéant, sa précondition. N'écrivez aucun code de représentation interne.

1. 01creer_pile()

   Signature : creer_pile() → Pile. Effet : renvoie une nouvelle pile vide. Précondition : aucune.

2. 02est_vide(p)

   Signature : est_vide(p) → bool. Effet : renvoie True si la pile p ne contient aucun élément, False sinon. Précondition : aucune.

3. 03empiler(p, x)

   Signature : empiler(p, x) → None. Effet : ajoute x au sommet de p ; après l'appel, sommet(p) vaut x. Précondition : aucune.

4. 04depiler(p)

   Signature : depiler(p) → élément. Effet : retire et renvoie l'élément situé au sommet de p. Précondition : p ne doit pas être vide (sinon l'opération est indéfinie).

5. 05sommet(p)

   Signature : sommet(p) → élément. Effet : renvoie l'élément au sommet SANS le retirer. Précondition : p ne doit pas être vide.

Résultat : L'interface décrit entièrement le comportement attendu de la pile (le contrat) sans rien dire de sa représentation : on peut maintenant l'implémenter de plusieurs façons.

On modélise une liste chaînée par une classe Maillon (attributs valeur et suivant). Écrivez la fonction inserer_en_tete(tete, x) qui insère x au début et renvoie la nouvelle tête, et justifiez son coût.

1. 01Représentation

   Un maillon a deux champs : valeur (l'entier stocké) et suivant (le maillon d'après, ou None). La liste est désignée par son premier maillon, la tête.

2. 02Créer le nouveau maillon

   On crée m = Maillon(x). On veut que m précède l'ancienne tête : on règle donc m.suivant sur l'ancienne tête.

3. 03Renvoyer la nouvelle tête

   Le nouveau premier maillon est m : on le renvoie. Aucun autre maillon n'a été déplacé ni modifié.

4. 04Coût

   On a effectué un nombre constant d'opérations (création d'un maillon + une affectation), indépendant de la longueur de la liste.

Résultat : inserer_en_tete s'écrit en trois lignes (m = Maillon(x) ; m.suivant = tete ; return m) et s'exécute en temps constant O(1), là où l'insertion en tête d'un tableau dynamique serait en O(n).

On part d'une structure vide et on exécute la suite d'opérations : ajouter 3, ajouter 7, ajouter 8, puis retirer, retirer. Donnez la valeur renvoyée par chaque retrait et l'état final (a) si la structure est une pile, (b) si c'est une file.

1. 01Pile — empilements

   On empile 3, 7, 8 dans cet ordre. De bas en haut, la pile contient [3, 7, 8] ; le sommet est 8.

2. 02Pile — dépilements

   Le premier depiler() retire le sommet 8 et le renvoie. Le second retire le nouveau sommet 7 et le renvoie (LIFO). Il reste [3].

3. 03File — enfilements

   On enfile 3, 7, 8 ; de la tête vers la queue : [3, 7, 8]. La tête est 3.

4. 04File — défilements

   Le premier defiler() retire la tête 3 et le renvoie. Le second retire la nouvelle tête 7 et le renvoie (FIFO). Il reste [8].

Résultat : Pile : les retraits renvoient 8 puis 7, état final [3]. File : les retraits renvoient 3 puis 7, état final [8]. Même suite d'entrées, ordres de sortie opposés : c'est toute la différence LIFO / FIFO.

À l'aide d'une pile, écrivez l'algorithme bien_parenthesee(ch) qui renvoie True si la chaîne ch, composée des symboles ( ) [ ], est correctement parenthésée (chaque fermante correspond à la dernière ouvrante non encore fermée). Déroulez-le sur « ([]) » puis sur « ([)] ».

1. 01Principe

   On parcourt ch de gauche à droite. À chaque ouvrante ( ou [, on l'empile. À chaque fermante, on dépile : la pile doit être non vide et son sommet doit être l'ouvrante correspondante, sinon la chaîne est mal parenthésée.

2. 02Test final

   Après lecture complète, la chaîne est bien parenthésée si et seulement si la pile est vide (toutes les ouvrantes ont été refermées).

3. 03Dérouler « ([]) »

   ( → empile ( ; [ → empile [ ; ] → sommet [ correspond, on dépile ; ) → sommet ( correspond, on dépile. Pile vide à la fin → True.

4. 04Dérouler « ([)] »

   ( → empile ( ; [ → empile [ ; ) → sommet est [ mais on attend [ ↔ ], incompatibilité → False (les paires se croisent).

Résultat : L'algorithme renvoie True pour « ([]) » (pile vide à la fin) et False pour « ([)] » (sommet incompatible à la fermeture). La discipline LIFO de la pile capture exactement l'imbrication correcte des parenthèses.

Écrivez compter_lettres(mot) qui renvoie un dictionnaire {lettre : nombre d'occurrences}, et déroulez-le sur « banane ».

1. 01Initialiser

   On part d'un dictionnaire vide d = {}. Il associera chaque lettre rencontrée à son compteur.

2. 02Parcourir le mot

   Pour chaque lettre du mot : si la lettre est déjà une clé de d (lettre in d), on incrémente d[lettre] ; sinon on crée le couple d[lettre] = 1. Le test in s'appuie sur le hachage, en O(1) moyen.

3. 03Dérouler « banane »

   b → {b:1} ; a → {b:1, a:1} ; n → {b:1, a:1, n:1} ; a → a déjà présent, {b:1, a:2, n:1} ; n → {b:1, a:2, n:2} ; e → {b:1, a:2, n:2, e:1}.

4. 04Coût

   Chaque lettre déclenche un test d'appartenance et une mise à jour en O(1) moyen ; pour un mot de longueur n, le total est O(n).

Résultat : compter_lettres('banane') renvoie {'b': 1, 'a': 2, 'n': 2, 'e': 1}. Le dictionnaire permet un comptage direct par clé, là où une liste de couples imposerait une recherche séquentielle à chaque lettre.

Un logiciel gère les travaux envoyés à une imprimante : ils doivent être imprimés dans l'ordre d'arrivée, et l'on veut pouvoir retrouver instantanément le propriétaire d'un travail à partir de son identifiant. Choisissez les structures adaptées et justifiez par le coût des opérations.

1. 01Identifier les opérations

   Besoin 1 : traiter les travaux dans l'ordre d'arrivée (on ajoute à la fin, on retire au début). Besoin 2 : retrouver un propriétaire à partir d'un identifiant (accès par clé, répété).

2. 02Besoin 1 → file (FIFO)

   L'ordre d'arrivée doit être respecté : c'est exactement la discipline FIFO d'une file. Enfiler en queue et défiler en tête (avec collections.deque) coûtent O(1).

3. 03Besoin 2 → dictionnaire

   On veut un accès direct par identifiant : un dictionnaire identifiant → propriétaire donne cet accès en O(1) en moyenne. Une liste de couples imposerait une recherche séquentielle en O(n) à chaque requête.

4. 04Conclusion chiffrée

   Pour q requêtes sur n travaux, la liste de couples coûte O(q·n) tandis que le dictionnaire coûte O(q) en moyenne : le gain est décisif quand n grandit.

Résultat : On choisit une file (FIFO) pour l'ordre d'impression — enfiler/défiler en O(1) — et un dictionnaire identifiant → propriétaire pour l'accès par clé en O(1) moyen, là où une liste de couples donnerait O(n) par requête. Le choix est justifié par le coût des opérations dominantes.