Skip to content

File bornée

Énoncé

On va implanter le type abstrait file qui fonctionne selon la politique du « premier entré, premier sorti » : on retire les éléments dans le même ordre que celui dans lequel ils ont été insérés.

Pour cette implantation, on va utiliser un tableau statique pour stocker les valeurs. Ce tableau sera géré selon le modèle du « tableau circulaire ». Cela signifie que si on arrive au bout du tableau mais qu'il y a des cases libres au début (car on a retiré des valeurs anciennes), alors on utilisera les cases du début lorsqu'on aura besoin d'insérer de nouvelles valeurs. Le dessin ci-dessous illustre ce principe de tableau circulaire :

fifo

Comme on utilisera un tableau statique pour stocker les valeurs de la file, on définira une constante CAPACITE = 5 en haut du programme indiquant la taille fixe du tableau statique.

Pour rappel, voici le lien vers le document résumant les notions de type abstrait et de structure de données.

On pourra tester les fonctions qu'on va écrire avec le programme principal ci-dessous. On donne aussi deux fonctions de base pour comprendre comment implanter la file : afficher et creer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#!/usr/bin/env python3
"""
Implantation d'une file bornée en utilisant un tableau statique
"""

CAPACITE = 5

# TODO implantez les fonctions :
#  - inserer
#  - retirer

def creer():
    """
    Crée une file de capacité donnée, sous la forme d'un tuple de trois éléments :
    - l'indice de l'élément le plus ancien de la file ;
    - le nombre d'éléments dans la file ;
    - le tableau contenant les valeurs, initialisé avec une valeur non-significative.
    """
    return (0, 0, ['@' for _ in range(CAPACITE)])

def afficher(tab, ix_ancien, nbr_elem):
    """
    Affiche le contenu de la file
    """
    print(f"(indice du plus ancien = {ix_ancien}, nombre d'éléments = {nbr_elem}, tableau = {tab})")


def test_inserer(tab, ix_ancien, nbr_elem, vals):
    """
    Test d'insertions
    """
    print("\nJe vais faire des insertions...")
    for val in vals:
        print("Valeur à insérer :", val)
        try:
            nbr_elem = inserer(tab, ix_ancien, nbr_elem, val)
        except AssertionError as exc:
            print(exc)
            print("=> file non modifiée")
        else:
            print("=> ", end="")
            afficher(tab, ix_ancien, nbr_elem)
    return ix_ancien, nbr_elem

def test_retirer(tab, ix_ancien, nbr_elem, nbr):
    """
    Test de suppressions
    """
    print("\nJe vais faire des extractions...")
    for _ in range(nbr):
        try:
            ix_ancien, nbr_elem, val = retirer(tab, ix_ancien, nbr_elem)
        except AssertionError as exc:
            print(exc)
            print("=> file non modifiée")
        else:
            print(f"Valeur retirée = {val}")
            print("=> ", end="")
            afficher(tab, ix_ancien, nbr_elem)
    return ix_ancien, nbr_elem

def main():
    """
    Programme principal
    """
    print("Creation d'une file vide...")
    ix_ancien, nbr_elem, tab = creer()
    print("=> ", end="")
    afficher(tab, ix_ancien, nbr_elem)
    ix_ancien, nbr_elem = test_retirer(tab, ix_ancien, nbr_elem, 1)
    ix_ancien, nbr_elem = test_inserer(tab, ix_ancien, nbr_elem, (1, 2, 3))
    ix_ancien, nbr_elem = test_retirer(tab, ix_ancien, nbr_elem, 2)
    ix_ancien, nbr_elem = test_inserer(tab, ix_ancien, nbr_elem, (4, 5, 6, 7, 8))
    ix_ancien, nbr_elem = test_retirer(tab, ix_ancien, nbr_elem, 1)
    ix_ancien, nbr_elem = test_inserer(tab, ix_ancien, nbr_elem, (8, 9))

main()

Création de la file

La fonction creer qui renvoie une nouvelle file vous est donnée. On a choisi de représenter la file sous la forme de 3 éléments :

  1. un entier qui représente l'indice de l'élément le plus ancien de la file, c'est à dire celui qui a été inséré avant tous les autres encore présents dans la file ;
  2. un autre entier qui contient le nombre d'éléments dans la file (à ne pas confondre avec la taille du tableau représentée par la constante CAPACITE ci-dessus) ;
  3. un tableau qui contient tout simplement les valeurs stockées dans la file, dans les indices [0 .. CAPACITE-1].

Affichage de la file

On donne aussi la fonction d'affichage de la file qui va utiliser les variables définies ci-dessus.

Insertion d'un élément dans la file

Implantez la fonction inserer(tab, idx_ancien, nbr_elem, val) qui va insérer la valeur val dans la file. Cette fonction renvoie le nouveau nombre d'éléments de la file après l'insertion. Attention à bien réfléchir à ce qui doit se passer si on essaie d'insérer une valeur dans une file déjà pleine en regardant la fonction test_inserer fournie.

Suppression d'un élément dans la file

On va ensuite implanter la fonction retirer(tab, ix_ancien, nbr_elem) qui doit retirer la valeur la plus ancienne présente dans la file. Cette fonction renvoie l'indice du nouvel éléments le plus ancien, le nouveau nombre d'éléments ainsi bien sûr que la valeur extraite. Là encore, il faut faire attention au cas particulier de la file vide en regardant la fonction test_retirer fournie.

Correction

Cliquez ici pour révéler la correction.

fifo.py :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#!/usr/bin/env python3
"""
Implantation d'une file bornée en utilisant un tableau statique
"""

CAPACITE = 5

# TODO implantez les fonctions :
#  - inserer
#  - retirer

def creer():
    """
    Crée une file de capacité donnée, sous la forme d'un tuple de trois éléments :
    - l'indice de l'élément le plus ancien de la file ;
    - le nombre d'éléments dans la file ;
    - le tableau contenant les valeurs, initialisé avec une valeur non-significative.
    """
    return (0, 0, ['@' for _ in range(CAPACITE)])

def afficher(tab, ix_ancien, nbr_elem):
    """
    Affiche le contenu de la file
    """
    print(f"(indice du plus ancien = {ix_ancien}, nombre d'éléments = {nbr_elem}, tableau = {tab})")

def inserer(tab, ix_ancien, nbr_elem, val):
    """
    Insère une valeur dans la file
    Renvoie le nouveau nombre d'éléments de la file
    Lance une exception si la file est pleine
    """
    assert nbr_elem < CAPACITE, "La file est pleine !"
    tab[(ix_ancien + nbr_elem) % CAPACITE] = val
    return nbr_elem + 1

def retirer(tab, ix_ancien, nbr_elem):
    """
    Retire une valeur de la file et la renvoie
    Renvoie :
    - le nouvel indice de l'élément le plus ancien
    - la nouveau nombre d'éléments de la file
    - la valeur extraite, ou None en cas d'erreur
    Lance une exception si la file est vide
    """
    assert nbr_elem > 0, "La file est vide !"
    val = tab[ix_ancien]
    ix_ancien = (ix_ancien + 1) % CAPACITE
    nbr_elem -= 1
    return ix_ancien, nbr_elem, val

def test_inserer(tab, ix_ancien, nbr_elem, vals):
    """
    Test d'insertions
    """
    print("\nJe vais faire des insertions...")
    for val in vals:
        print("Valeur à insérer :", val)
        try:
            nbr_elem = inserer(tab, ix_ancien, nbr_elem, val)
        except AssertionError as exc:
            print(exc)
            print("=> file non modifiée")
        else:
            print("=> ", end="")
            afficher(tab, ix_ancien, nbr_elem)
    return ix_ancien, nbr_elem

def test_retirer(tab, ix_ancien, nbr_elem, nbr):
    """
    Test de suppressions
    """
    print("\nJe vais faire des extractions...")
    for _ in range(nbr):
        try:
            ix_ancien, nbr_elem, val = retirer(tab, ix_ancien, nbr_elem)
        except AssertionError as exc:
            print(exc)
            print("=> file non modifiée")
        else:
            print(f"Valeur retirée = {val}")
            print("=> ", end="")
            afficher(tab, ix_ancien, nbr_elem)
    return ix_ancien, nbr_elem

def main():
    """
    Programme principal
    """
    print("Creation d'une file vide...")
    ix_ancien, nbr_elem, tab = creer()
    print("=> ", end="")
    afficher(tab, ix_ancien, nbr_elem)
    ix_ancien, nbr_elem = test_retirer(tab, ix_ancien, nbr_elem, 1)
    ix_ancien, nbr_elem = test_inserer(tab, ix_ancien, nbr_elem, (1, 2, 3))
    ix_ancien, nbr_elem = test_retirer(tab, ix_ancien, nbr_elem, 2)
    ix_ancien, nbr_elem = test_inserer(tab, ix_ancien, nbr_elem, (4, 5, 6, 7, 8))
    ix_ancien, nbr_elem = test_retirer(tab, ix_ancien, nbr_elem, 1)
    ix_ancien, nbr_elem = test_inserer(tab, ix_ancien, nbr_elem, (8, 9))

main()