Aller au contenu
Algorithmique avancée et structures de données · L2

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

Pose ta question à Karamö