Leçon 2 sur 5
Piles et files : utilisation et implémentation
Je sais reconnaître un problème de type pile (dernier entré, premier sorti) ou de type file (premier entré, premier sorti), implémenter ces deux structures en Python avec des opérations en O(1) et les utiliser pour résoudre des problèmes classiques.
- 1 h 20
- 5 exercices corrigés
- QCM de 6 questions
À la fin de la leçon, vous saurez :
- Définir les types abstraits pile et file et leurs opérations
- Implémenter une pile avec une liste Python et une file avec deque ou une liste chaînée
- Expliquer pourquoi list.pop(0) est une mauvaise file
- Utiliser une pile pour vérifier un parenthésage et évaluer une expression postfixée
- Simuler une file d'attente
Avant de commencer : Leçon 1 (listes chaînées) ; Programmation 1 (L1, Python).
1Je découvre
Au guichet d'un point de transfert d'argent mobile, à Labé, les clients font la queue : le premier arrivé est le premier servi. Derrière le comptoir, l'agent empile les reçus du jour sur une pointe : le dernier reçu posé est le premier qu'il reprend en main.
Mamadou, toujours en L2 de génie informatique, remarque que deux règles opposées gouvernent ces deux tas. La file d'attente des clients suit la règle « premier arrivé, premier servi ». La pile de reçus suit la règle « dernier posé, premier repris ». Et ces deux règles, il les retrouve partout en informatique : le bouton « Retour » de son navigateur, la touche « Annuler » de son traitement de texte, la file d'impression du cybercafé, les messages WhatsApp qui attendent la connexion.
Quelles sont les deux structures qui obéissent à ces règles, comment les programmer pour qu'elles soient rapides, et à quels problèmes servent-elles ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.
Voir toutes les leçons de Algorithmique avancée et structures de données
Signaler une erreur dans cette leçon
Toutes les leçons de Algorithmique avancée et structures de données