Informatique · Terminale · 2 min de lecture
Séparer l’interface d’une pile de son implémentation
Spécifier une structure de données par son interface (les opérations disponibles et leur effet) ; distinguer l'interface de l'implémentation (la façon de programmer ces opérations) ; écrire plusieurs implémentations d'une même structure, par exemple une file avec un tableau ou avec deux piles ; modularité et utilisation de bibliothèques.
Chapitre du programme : Numérique et sciences informatiques (spécialité)
Bloc 1 sur 7 · Comprendre
Comprendre
Une interface décrit les opérations offertes par une structure et leurs effets observables. Une implémentation précise comment ces opérations sont réalisées en mémoire. Pour une pile, empiler ajoute au sommet et dépiler retire le dernier élément empilé encore présent : c'est le principe dernier entré, premier sorti.
Bloc 2 sur 7 · Approfondir
Approfondir
Plusieurs représentations peuvent respecter la même interface : tableau redimensionnable, liste chaînée ou autre structure adaptée. Le résultat logique des opérations doit rester conforme au contrat, même si leur coût et leur organisation interne diffèrent. Le comportement sur pile vide doit aussi être spécifié.
Bloc 3 sur 7 · Exemple
Exemple travaillé
Partez d'une pile vide. Empiler4 puis7 donne [4,7], avec le sommet à droite. Dépiler renvoie7 et laisse [4]. Empiler2 donne [4,2]. Le dépilement suivant renvoie2 et laisse [4]. Les valeurs retirées dépendent de l'ordre des opérations, pas de la manière de ranger physiquement les éléments.
Bloc 4 sur 7 · Visualiser
Visualiser le raisonnement
Dessinez une colonne dont le haut est le sommet ou une liste dont le sommet est explicitement à droite. Après chaque opération, mettez à jour le dessin avant de passer à la suivante. Ne changez pas la convention de sommet en cours de trace.
Continuez sur votre lancée
Vous avez découvert l’essentiel et un exemple. Retrouvez la suite du cours et les points à retenir, puis passez à l’entraînement guidé dans votre compte.
- Les formules et les repères à retenir
- Les erreurs fréquentes expliquées
- Un exercice avec des aides et sa correction
L’accès gratuit comprend les cours et exercices de votre niveau choisi.
Sources
- https://docs.python.org/3/tutorial/datastructures.html
- Python Software Foundation, listes utilisées comme piles : https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks
- Princeton, stacks and queues : https://algs4.cs.princeton.edu/13stacks/
Vous pensez avoir trouvé une erreur dans cette leçon ? Signalez-la par e-mail.