Dans cette partie nous allons analyser une nouvelle structure de données : les piles.
Les piles sont extrèmement utiles en informatique et vous les utilisez quotidiennement, parfois même sans vous en rendre compte :
les serveurs d'impression, qui traitent ainsi les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (dite aussi queue ou spool) ;
les serveurs web traitent aussi les requêtes dans l'ordre dans lequel elles arrivent;
Certains ordonnanceurs dans un système d'exploitation, qui doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune ;
Une file est une liste particulière ou l'on accède uniquement à l'élément le plus ancien (qui a été placé en premier).
Représentation
On représente en général cette structure sous forme horizontal.
On peut prendre pour file d'attente au guichet, le premier arrivée sera le premier servi (First In First Out : premier entré, premier sorti).
L'interface
Comme pour les piles, les primitives des files se trouvent en nombre réduit.
Les primitives
Les opérations permises sur les files sont équivalentes à celle des listes :
creer : créer une file vide
enfiler un nouvel élément (ajouter un élément au sommet de la pile)
défiler le premier élément saisi
de consulter le premier élément de la file sans le défiler
de tester si la file est vide
de connaître le nombre d'éléments dans la file.
Exercice
On contruite une pile avec les instructions suivantes :
créer une file vide nommée p
enfiler "A" dans p
enfiler "B" dans p
enfiler "C" dans p
enfiler "D" dans p
enfiler "E" dans p
enfiler "F" dans p
enfiler "G" dans p
enfiler "H" dans p
enfiler "I" dans p
défiler p
défiler p
défiler p
défiler p
enfiler "S" dans p
défiler p
défiler p
enfiler "N" dans p
défiler p
défiler p
Représenter la file obtenue :
Les valeurs de la liste seront séparées par un tiret (-) sans espace entre.
L'implémentation
Pour l'implémentation en python c'est dans le TD que ça se passe :
