Structure de file

Un modèle est la célèbre file d'attente à la caisse du supermarché :

I/ Définition

1) FIFO

Une file est une liste ne pouvant être parcourue itérativement, et dont les ajouts et suppressions ne se font pas du même côté. L'acronyme FIFO voulant dire « First In, First Out ».

2) Interface

Une file est donc caractérisée par les méthodes

On rappelle que l'interface des listes possède déjà tout ça (à part la dernière méthode) :

class Liste():
	def __init__(self,L):
		self.contenu = L
	def dernier(self):
		pass
	def empiler(self,elt):
		pass
	def premier(self):
		pass
	def pousser(self,elt):
		pass
	def __iter__(self):
		pass
	def __repr__(self):
		return str(self.contenu)

3) Classe

Alors on en extrait l'interface des files :

class File(Liste):
    def est_vide(self):
        return len(self.contenu)==0
    def dernier(self):
        return self.contenu.pop()
    def pousser(self,elt):
        self.contenu.insert(0,elt)

En machine, une file est typiquement implémentée comme une liste munie de deux pointeurs, l'un sur le début de la liste, l'autre sur la fin :

II/ Autre construction

On peut également construire une file à l'aide de deux piles :

On peut considérer que la première pile représente la première partie de la file (à l'envers), et que la seconde pile représente la seconde partie de la file.

class File():
    def __init__(self):
        self.pile1 = []
        self.pile2 = []
    def __repr__(self):
        return str(list(reversed(self.pile1)))+str(self.pile2)
    def flush(self):
        while len(self.pile1):
            self.pile2.append(self.pile1.pop())
    def dernier(self):
        if len(self.pile2)==0:
            self.flush()
        return self.pile2.pop()
    def pousser(self,elt):
        self.pile1.append(elt)

Par exemple, avec

f = File()
for n in range(5):
    f.pousser(n)
print(f.dernier())
f.pousser(8)
f.pousser(5)
print(f)

L'affichage

0
[5, 8][4, 3, 2, 1]

montre que les piles

%3 0 5 1 8 1->0 2 4 3 3 2->3 4 2 3->4 5 1 4->5

représentent la file

%3 0 5 1 8 0->1 2 4 1->2 3 3 2->3 4 2 3->4 5 1 4->5

III/ Exemples

1) Parcours en largeur

Le parcours d'un graphe en largeur utilise une file.

2) Multitâches

Les processus sont gérés par le système d'exploitation comme une file, pour éviter les trop longs temps d'attente.

Les mémoires de type buffer (« tampons ») aussi.