Structures de données

2 ) Les files

Une file est une structure de données qui permet d'accéder aux données en suivant la règle : première donnée ajoutée, première donnée sortie ; on peut imaginer une file de gens à l'entrée d'une attraction, la personne située en tête de file sera la première à en sortir :
On parle de structure ou de file FIFO (queue en anglais). FIFO est l'abbréviation de First In First Out (première donnée entrée , première donnée sortie).

Ci dessous des liens vers des vidéos permettant d'asseoir les connaissances :

* D'abord une autre présentation python des Piles et Files
* Comprendre la structure de données de la file FIFO

Voici les opérations que l'on peut réaliser sur une file :

• on peut créer une file vide                                                                ( creer_file_vide() retourne un objet de type file)
• on peut savoir si une file est vide                                                      (file_vide(F) retourne un booléen)
• on peut enfiler un nouvel élément sur la file (push)                            (enfiler (F,e)insère un élément en queue de la file)
• on peut récupérer l'élément au tête de la file tout en le supprimant.
  on dit que l'on défile (pop)                                                               (défiler (F)retourne l'élément qui est en tête de la file et l'enlève de la file)
• on peut accéder à l'élément situé en tête de la file sans le supprimer de la file (front)                (tete (F)renvoie l'élémént de tete)
• on peut connaitre le nombre d'éléments présents dans la file (size)                                          (taille(F)renvoie le nombre d'éléménts de la file)
• on peut savoir si une file est pleine                                                   (file_pleine(F) retourne un booléen)

Exemples :

Voici une série d'instructions (les instructions ci-dessous s'enchaînent):

• F=creer_file_vide() => on a créé une file vide
• file_vide(F) => renvoie vrai
• enfiler (F,23) => La file F contient maintenant l'élément 23
• file_vide(F) => renvoie faux
• enfiler (F,12) => La pile F contient maintenant les éléments 23 et 12
• N = défiler (F) => la variable N vaut 23, la file contient l'élément 12 ; 23 disparait de la file
• enfiler (F,15) => La file F contient maintenant les éléments 12 et 15
• enfiler (F,7) => La file F contient maintenant les éléments 12,15 et 7
• enfiler (F,9) => La file F contient maintenant les éléments 12,15,7 et 9
• file_vide(F) => renvoie faux
• N = défiler (F) => la variable N vaut 12, la file contient les éléments 15,7 et 9 ; 12 disparait de la file

Exercice 1

Soit une file F composée des éléments suivants : 12, 10, 8, 7, 13 et 25 (la tête de la file est 12); Pour chaque exemple ci-dessous on repart de la file d'origine :

• que renvoie pop(F) ? que contient la file F après ce pop ? quelle est la tête de la file ?
• donner la composition de la file après push(F,33) ?
• que renvoie front(F) ?
• si on applique pop(f) 3 fois de suite, que renvoie file_vide(F) ?
• Après avoir appliqué pop(F) une fois, que renvoie size(F) ?

remarque : Pour creer une file de n valeurs, on peut se servir d'un tableau F[0...(n+3)] qui pourra donc contenir (n+4) valeurs.

• La première case du tableau [indice 0] contient l'indice de la tête de la file
• La deuxième case du tableau [indice 1] contient l'indice de la queue de la file, c'est à dire la prochaine case disponible pour la queue
• La troisième case du tableau [indice 2] contient le nombre d'éléments présents dans la file
• Les cases suivantes du tableau [indice 3 à n+3] contiennent les autres éléments de la file ou elles sont vides

En python

Si (size == 0) la file est vide et si (size == n) la file est pleine.
Pour implémenter une FILE en python, on peut utiliser un code comme celui-ci :

Exercice 2