%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Piles et Files/Piles et Files|Accueil · Piles et Files]]
>
> | [[Code et Développement/Programmation/Piles et Files/01_Les piles\|← Les piles]] | |
> |:---|---:|
%% nav-fin %%
# Les files
Une file (en anglais *queue*) est une structure de données où l'on ajoute les éléments à une extrémité et où on les retire à l'autre.
On ajoute en **queue** de file. On retire en **tête** de file.
Le premier élément ajouté est le premier retiré. Ce principe s'appelle **FIFO**, pour *First In, First Out*.
Une file offre quatre opérations :
- **enfiler** : ajouter un élément en queue ;
- **défiler** : retirer l'élément de tête et le renvoyer ;
- **tête** : lire l'élément de tête sans le retirer ;
- **taille** : compter les éléments.
Les files servent par exemple à gérer une file d'impression, à traiter des requêtes dans leur ordre d'arrivée ou à parcourir un graphe en largeur.
---
## Implémenter une file en Python
La classe `File` stocke ses éléments dans une liste Python. La tête est le début de la liste, la queue est la fin.
```python
class File:
def __init__(self):
self.elements = []
def enfile(self, element):
self.elements.append(element)
def defile(self):
if self.elements:
return self.elements.pop(0)
def taille(self):
return len(self.elements)
def tete(self):
if len(self.elements) == 0:
raise Exception("La file est vide")
return self.elements[0]
def __str__(self):
if not self.elements:
return "File vide"
return "File : " + " <- ".join(str(x) for x in self.elements)
```
Chaque méthode correspond à une opération de liste :
| Méthode | Opération de liste | Effet |
|---|---|---|
| `enfile(x)` | `append(x)` | ajoute `x` à la fin de la liste, donc en queue |
| `defile()` | `pop(0)` | retire et renvoie le premier élément |
| `tete()` | `elements[0]` | lit le premier élément |
| `taille()` | `len(elements)` | compte les éléments |
Sur une file vide, `defile()` ne retire rien et renvoie `None`. `tete()` lève une exception.
La méthode `__str__` affiche la tête en premier. Elle traite le cas de la file vide.
> [!note] Coût de `pop(0)`
> `pop(0)` retire le premier élément d'une liste. Python décale alors tous les autres éléments d'une case. Le coût grandit avec la taille de la file.
>
> Le module `collections` fournit `deque`, conçue pour les files. `append` ajoute en queue et `popleft` retire en tête, en temps constant.
>
> ```python
> from collections import deque
> f = deque([4, 9, 1])
> f.append(3) # enfiler
> f.popleft() # défiler, renvoie 4
> ```
**À manipuler :** créez la file du programme suivant, puis appelez ses méthodes. Chaque bouton affiche l'appel Python équivalent.
```python
queue = File()
queue.enfile(4)
queue.enfile(9)
queue.enfile(1)
print(queue) # File : 4 <- 9 <- 1
queue.defile()
print("Tête", queue.tete()) # Tête 9
print("Taille", queue.taille()) # Taille 2
queue.enfile(3)
print(queue) # File : 9 <- 1 <- 3
```
```sq-file
initial: 4, 9, 1
nom: queue
```
---
## Application : le jeu de Josèphe
Des personnes sont disposées en cercle. On compte de 3 en 3 à partir de la première personne. La troisième personne comptée est éliminée. On recommence à compter à partir de la personne suivante, jusqu'à ce qu'il ne reste personne.
On cherche la dernière personne éliminée.
Une file représente le cercle :
1. on enfile les personnes dans l'ordre du cercle ;
2. on défile deux personnes et on les renfile aussitôt : elles passent de la tête à la queue ;
3. on défile la troisième sans la renfiler : elle est éliminée ;
4. on recommence tant que la file n'est pas vide.
```python
cercle = ["A", "B", "C", "D", "E", "F", "G"]
def dernier_elimine(c):
f = File()
for personne in c:
f.enfile(personne)
sortie = None
while f.taille() != 0:
f.enfile(f.defile())
f.enfile(f.defile())
sortie = f.defile()
return sortie
print(dernier_elimine(cercle)) # D
```
Quand il reste une ou deux personnes, une même personne peut être défilée puis renfilée plusieurs fois avant son élimination.
**À manipuler :** suivez la file à chaque étape. Le cercle montre les personnes éliminées.
```sq-josephe
cercle: A, B, C, D, E, F, G
pas: 3
```
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Piles et Files/Piles et Files|Accueil · Piles et Files]]
>
> | [[Code et Développement/Programmation/Piles et Files/01_Les piles\|← Les piles]] | |
> |:---|---:|
%% nav-fin %%