Les files : comprendre le fonctionnement FIFO

Un cap pour ce chapitre

Ce que vous saurez faire

Décrire l’interface FIFO d’une file.
Exécuter une réalisation avec deux piles.
Comprendre pourquoi les transferts n’ont lieu que lorsque la pile de sortie est vide.

Les bases utiles pour commencer

Servir le plus ancien élément présent

Une file possède une entrée pour les ajouts et une sortie pour les retraits. Enfiler ajoute un élément après ceux déjà présents ; défiler renvoie et retire le plus ancien. Cette discipline est appelée FIFO : First In, First Out. Elle représente notamment une attente, une liste de tâches ou la frontière d’un parcours en largeur.

Après l’arrivée de A, B et C, la première sortie est A, puis B. Une file vide doit être traitée conformément au contrat. Consulter sa tête peut être une opération distincte du retrait, de la même façon que consulter le sommet d’une pile ne le dépile pas.

FIFO concerne l’ancienneté parmi les éléments encore présents. Après le retrait de A, B devient le plus ancien même si C est arrivé entre-temps. La file conserve cette relation sans avoir à comparer des dates. Une priorité médicale ou une durée de tâche pourrait imposer une autre structure : utiliser une file simple signifie précisément choisir l’ordre d’arrivée comme règle de service.

Une liste peut représenter une file

Avec une liste Python, on peut ajouter à droite et retirer à gauche. Cette réalisation est simple à lire, mais un retrait au début peut déplacer les éléments restants. Une bibliothèque peut proposer d’autres structures plus adaptées. L’objectif du cours est de comprendre la différence entre l’interface FIFO et ses réalisations.

Une implémentation ne doit pas modifier l’ordre sous prétexte de faciliter un retrait. Employer append puis pop sans argument sur une seule liste réalise une pile, pas une file. Le nom donné à la variable ne suffit donc pas à déterminer son comportement.

Deux piles pour inverser l’ordre

Nous utilisons une pile d’entrée E et une pile de sortie S, sommets à droite. Enfiler consiste à empiler sur E. Pour défiler, si S est vide, on dépile tous les éléments de E vers S. Avec E = [A, B, C], le transfert produit S = [C, B, A], dont le sommet est A : le plus ancien.

On dépile ensuite S. Tant que S contient des éléments, on ne transfère pas les nouvelles arrivées : elles restent dans E. Mélanger ces nouvelles arrivées à S trop tôt pourrait les placer devant des éléments plus anciens.

def enfiler(file, valeur):
    entree, sortie = file
    entree.append(valeur)

def defiler(file):
    entree, sortie = file
    if not sortie:
        while entree:
            sortie.append(entree.pop())
    assert sortie
    return sortie.pop()

Observer le coût sur plusieurs opérations

Un défiler peut être coûteux lorsqu’il déclenche le transfert de nombreux éléments. Mais chaque élément traverse au plus une fois de E vers S avant sa sortie. Sur une suite d’opérations, on ne refait donc pas ce transfert pour tous les éléments à chaque retrait. Cela explique l’intérêt de la méthode sans prétendre que chaque opération isolée a le même coût.

L’ordre logique de sortie est celui de S lue du sommet vers le fond, suivi de E lue du fond vers le sommet. Cette lecture permet de vérifier le contrat à tout instant, y compris lorsque les deux piles sont simultanément non vides.

Pour lire l’ordre logique lorsque les deux piles contiennent des données, commencez par la sortie du sommet vers le fond, puis l’entrée du fond vers le sommet. Si S=[B,A] et E=[C,D], l’ordre de sortie est A,B,C,D. Concaténer directement les deux listes écrites produirait B,A,C,D et confondrait leur représentation avec leur signification.

Exemple suivi : une arrivée pendant les départs

Enfilons A et B : E contient A,B et S est vide. Le premier retrait transfère B puis A vers S, puis dépile A. Il reste S=[B]. Enfilons maintenant C : il va dans E, tandis que B reste dans S. Le prochain retrait doit donc dépiler B sans transférer C. Ensuite seulement, S étant vide, le retrait suivant transfère C puis le renvoie.

La suite des sorties A,B,C respecte l’ancienneté. Le transfert renverse E pour que son élément le plus ancien arrive au sommet de S. Répéter ce transfert lorsque S n’est pas vide placerait des arrivants plus récents devant des personnes déjà en attente. La condition « S vide » n’est donc pas une simple optimisation : elle participe directement à la correction du comportement.

Compter le travail sur une suite complète

On enfile n éléments, puis on les retire tous. Chacun est empilé une fois dans E, dépilé une fois de E lors du transfert, empilé une fois dans S, puis dépilé une fois de S. En comptant ces seules opérations élémentaires, il y en a 4n. Le premier retrait peut déclencher n transferts, mais les suivants ne recommencent pas le travail déjà effectué.

Cette analyse sur la suite explique l’efficacité moyenne des opérations sans affirmer que chaque retrait a un coût constant dans le pire cas. Le nombre d’éléments en attente détermine aussi la mémoire utilisée, répartie entre E et S. Pour diagnostiquer une réalisation, testez un lot d’arrivées, des arrivées entre deux départs et le retrait à vide. Ces scénarios vérifient des branches différentes du même contrat.

À vous de faire varier les choses

Faites circuler les visiteurs entre les piles

Avancez une suite d’arrivées et de départs. Regardez quand le transfert se produit et vérifiez l’ordre des sorties.

Lire le résultat de l’expérience initiale

Ordre restant : B, C

Sommets à droite dans les deux piles. On transfère l’entrée seulement lorsque la sortie est vide.

Opération	Entrée E	Sortie S	Ordre FIFO restant
Arrivée A	A		A
Arrivée B	A, B		A, B
Sortie A, 2 transfert(s)		B	B
Arrivée C	C	B	B, C

Indice 2

L’autorisation du transfert et celle du retrait sont deux tests différents.

Comprendre la correction

La version fautive renvoie C alors qu’A doit sortir. Il faut transférer seulement si S est vide, puis vérifier que S est non vide avant le retrait. Si les deux piles étaient vides, le transfert ne produit aucun élément et le retrait doit être refusé selon le contrat.

Les erreurs qui méritent un détour

Transférer les arrivées alors que la sortie contient encore des éléments.: Les nouveaux éléments risquent de dépasser les anciens. Le test de vacuité de la sortie protège l’ordre FIFO.
Lire les deux listes internes directement de gauche à droite.: La sortie se lit depuis son sommet, puis l’entrée depuis son fond pour obtenir l’ordre logique.

La fiche à garder

L’essentiel à retenir

Une file applique l’ordre FIFO.
Deux piles inversent l’ordre au moment nécessaire.
L’interface ne change pas avec l’organisation interne.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

Le prochain pas

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.