19 - Implémenter une File

⏪

⏬

⏩

1 - File tableau

2 - File Chainée

3 - File de 2 Piles

4 - Autres

Nous allons voir quelques implémentations possibles du type File.

Prerequis : l'activité sur les Piles, sur les Files, ainsi qu'au moins l'une des activités d'implémentation.

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

1 - MAUVAISE Implémentation de la File sous forme d'un tableau dynamique

⇩ ⇧ ⤊

Note préliminaire importante

La File présentée dans cette partie va être facile à réaliser mais aura des performances assez faibles : le but est de vous montrer qu'il faut souvent mieux réfléchir AVANT de passer à une réalisation pratique.

(Rappel) 1.1 Primitives d'une File

Voir

A (RAPPEL) Fonctions d'interface

Fonctions d'interface d'un module : en informatique, les fonctions d'interface caractérisent les fonctions qui sont utilisables par l'utilisateur d'un module.

B (RAPPEL) Primitives

Trois idées caractérisent ces fonctions particulières :

Les opérations primitives font partie des fonctions d'interface disponibles pour ce type abstrait de données.
Les opérations primitives sont les briques d'actions fondamentales permettant d'agir sur ce type de données.
Les futures implémentations des primitives devront avoir le coût le plus faible possible (se rapprochant d'un coût constant si possible).

C - Les primitives d'une File

nouvelleFile() -> File VIDE : on crée une nouvelle file vide.
En anglais, cela pourrait donner newQueue().
estFileVide(f:File) -> bool : prédicat qui renvoie True si la File p transmise est une File vide.
En anglais, cela pourrait donner isEmpty().
enfiler(f:File, elt:Element) -> File NON VIDE : on renvoie une file en rajoutant l'élément elt à l'ARRIERE dans f.
En anglais, ça se nomme enqueue().
defiler(f:File NON VIDE) -> File : on supprime l'élément à l'AVANT et renvoie la nouvelle File f.
En anglais, ça se nomme dequeue(). La fonction n'est pas définie si la file est vide.
lireAvant(f:File NON VIDE) -> Element : on renvoie l'élément en sortie(sans le supprimer ici). La fonction n'est définie que si la file n'est pas vide.
En anglais, ça se nomme front().

Contrairement à la Liste, il n'y a pas de primitives liées au type intermédiaire Place : pas de fonctions acces(), successeur() ou contenu() nécessaires puisque l'utilisateur n'a le droit que d'accéder au sommet. On lui simplifie le travail en ne lui fournissant que les outils nécessaires à la gestion de ce type de structure.

01° Quel est le coût espéré des primitives enfiler(), defiler() et lire_avant() ?

Correction ?

...CORRECTION...

On voudrait qu'elles soient à coût CONSTANT si possible.

02° On se propose d'utiliser directement le type list de Python pour tenter de faire notre File. Quel est le coût des méthodes suivantes sur un tableau t ?

t.append(elt)
t.pop()
t.pop(0)
t.insert(0, elt)

Correction ?

...CORRECTION...

Nous avons vu que :

t.append(elt) est à coût amorti CONSTANT
t.pop() est à coût CONSTANT
t.pop(0) est à coût LINEAIRE car il faut déplacer tous les éléments d'une case vers la gauche.
t.insert(0, elt) est à coût LINEAIRE car il faut déplacer tous les éléments d'une case vers la droite. Si le tableau dynamique a déjà atteint sa taille maximum, il faudra même recréer un tableau plus grand.

03° Expliquons maintenant pourquoi on ne peut pas obtenir une bonne implémentation de File en utilisant directement le type list de Python :

Possibilité 1 :

l'Arrière est positionné sur l'indice 0 du tableau dynamique et
l'Avant est positionné sur le dernier indice du tableau dynamique.

En image, cela donne ceci :

graph LR I(("+"))-. enfilement .-> D("Arrière [0]") --> C["[1]"] --> B["[2]"] --> A("Avant [3]") -. défilement .-> S(("-")) style A fill:#f55,stroke:#333,stroke-width:2px style D fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px

Questions : avec ce choix d'implémentation

Que veut dire insérer à l'arrière ? Quel est le coût de cette action ?
Que veut dire supprimer à l'avant ? Quel est le coût de cette action ?
Pourquoi ne peut-on pas choisir ceci pour obtenir une bonne implémentation de File ?

Correction ?

...CORRECTION...

Choix 1 : l'arrière est l'indice 0 et l'avant le dernier indice du tableau dynamique.

Insérer à l'arrière veut donc signifier insérer sur l'indice 0.

C'est donc à coût LINEAIRE puisqu'on va devoir utiliser t.insert(0, elt) qui est à coût LINEAIRE.

Supprimer l'avant veut donc signifier supprimer la dernière case du tableau.

C'est donc à coût CONSTANT puisqu'on va devoir utiliser t.pop() qui est à coût CONSTANT.

On voit donc que cela ne fonctionne pas car les deux opérations ne sont pas à coût CONSTANT.

04° Passons à l'autre possibilité.

Possibilité 2 :

l'Avant est positionné sur l'indice 0 du tableau dynamique et
l'Arrière est positionné sur le dernier indice du tableau dynamique.

graph RL I(("+"))-. enfilement .-> D("Arrière [3]") --> C["[2]"] --> B["[1]"] --> A("Avant [0]") -. défilement .-> S(("-")) style A fill:#f55,stroke:#333,stroke-width:2px style D fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px

Questions : avec ce choix d'implémentation

Que veut dire insérer à l'arrière ? Quel est le coût de cette action ?
Que veut dire supprimer à l'avant ? Quel est le coût de cette action ?
Pourquoi ne peut-on pas choisir ceci pour obtenir une bonne implémentation de File ?

Correction ?

...CORRECTION...

Choix 2 : l'arrière est l'indice final et l'avant l'indice 0 du tableau.

Insérer à l'arrière va donc signifier l'insertion en fin de tableau dynamique.

C'est donc à coût CONSTANT puisqu'on va devoir utiliser t.append(elt) qui est à coût CONSTANT.

Supprimer à l'avant va donc signifier de supprimer le contenu de la case d'indice 0.

Cela va se faire à coût LINEAIRE puisqu'on va devoir utiliser t.pop(0) qui est à coût LINEAIRE (on va décaler le contenu des cases une à une).

On voit donc que cela ne fonctionne pas car les deux opérations ne sont pas à coût CONSTANT.

Voyons maintenant deux autres implémentations de meilleur qualité car elles réagissent à coût constant pour enfiler() et defiler() .

2 - Implémentation d'une File avec une liste chaînée

⇩ ⇧ ⤊

05° On se propose d'implémenter notre File en utilisant le principe d'une liste chaînée basée sur des tuples.

Une liste chaînée vide est composée du tuple vide ()
Une liste chaînée non vide pointe vers un tuple (valeur, successeur)

Quels étaient les coûts des fonctions suivantes en utilisant la structure tuples-cellules proposée ci-dessus ?

inserer_tete()
supprimer_tete()
inserer_fin()
supprimer_fin()

Correction ?

...CORRECTION...

Nous avons vu que :

inserer_tete() est à coût CONSTANT.
supprimer_tete() est à coût constant
inserer_fin() est à coût LINEAIRE car il faut supprimer et stocker les têtes pour atteindre la fin et ensuite les remettre en place.
supprimer_fin() est à coût LINEAIRE car il faut supprimer et stocker les têtes pour atteindre la fin et ensuite les remettre en place.

06° Pourquoi n'est-il pas utile de continuer sur cette voie d'implémentation ?

Correction ?

...CORRECTION...

Nous avons besoin de savoir insérer à coût CONSTANT d'un côté et de supprimer à coût CONSTANT de l'autre.

Puisqu'on agit toujours à coût LINEAIRE sur la Fin, on ne parviendra pas à agir de façon constante sur ce côté.

07° On se propose d'implémenter notre File en utilisant le principe d'une liste chaînée basée sur des objets Cellule.

Une liste chaînée vide est composé un objet dont l'attribut tete contient None.
Une liste chaînée non vide est un objet dont l'attribut tete pointe vers une Cellule qui est la cellule de tête.

Quels étaient les coûts des fonctions suivantes en utilisant la structure proposée ci-dessus (sur laquelle on ne connaît que la référence de la Tête) ?

inserer_tete()
supprimer_tete()
inserer_fin()
supprimer_fin()

Correction ?

...CORRECTION...

Nous avons vu que :

insererTete() est à coût CONSTANT puisqu'on sait localiser facilement la tête.
supprimerTete() est à coût CONSTANT puisqu'on sait localiser facilement la tête
insererFin() est à coût LINEAIRE car on d'abord localiser la cellule de Fin en partant de la la cellule de Tête.
supprimerFin() est à coût LINEAIRE car on doit d'abord localiser le prédécesseur de la cellule de Fin en partant de la Tête.

08° Pourquoi n'est-il pas utile de continuer sur cette voie d'implémentation ?

Correction ?

...CORRECTION...

Nous avons besoin de savoir insérer à coût CONSTANT d'un côté et de supprimer à coût CONSTANT de l'autre.

Puisqu'on agit toujours à coût LINEAIRE sur la Fin, on ne parviendra pas à agir de façon constante sur ce côté.

09° Comment améliorer notre liste chaînée pour parvenir à nous permettre d'implémenter correctement une File ?

Correction ?

...CORRECTION...

Il faudrait parvenir à insérer à coût CONSTANT en Fin de liste.

Nous avions vu dans l'activité Implémentation de Liste 3 que c'était possible si on stockait la référence de la Cellule de Fin dans la liste, en plus de la Cellule de Tête.

Voici donc ce que vous allez faire dans cette partie : réaliser une File à partir d'une Liste pointant sa Tête et sa Fin déjà implémentée (dans l'activité Implémenter une Liste 3).

10° Voici un extrait de la documentation de ce module : on y détaille notamment les coûts des différentes fonctions d'insertion et de suppression.

Question : Où placer l'Avant pour obtenir une suppression à coût CONSTANT ? où placer l'Arrière pour insérer à coût CONSTANT ?

Primitives d'interface cachant l'aspect objet
---------------------------------------------
+ CST : nouvelle_liste() -> Liste
+ CST : est_liste_vide(lst:'Liste') -> bool
 
+ CST : inserer_tete(lst:'Liste', elt:'Element') -> None
+ CST : inserer_fin(lst:'Liste', elt:'Element') -> None
+ LIN : inserer(lst:'Liste', elt:'Element', i:'int VALIDE') -> None
 
+ CST : supprimer_tete(lst:'Liste NON VIDE') -> 'Element'
+ LIN : supprimer_fin(lst:'Liste NON VIDE') -> 'Element'
+ LIN : supprimer(lst:'Liste', i:'int VALIDE') -> 'Element'
 
+ LIN : longueur(lst:'Liste') -> int
 
+ CST : premier(lst:'Liste NON VIDE') -> 'Element'
+ CST : dernier(lst:'Liste NON VIDE') -> 'Element'
+ LIN : ieme(lst:'Liste NON VIDE', i:'int VALIDE') -> 'Element'

Correction ?

...CORRECTION...

Un seul choix possible pour la suppression à coût constant : on ne sait que supprimer la Tête. Cela veut donc dire qu'il faudra placer l'AVANT au niveau de la TETE.

On placera donc l'ARRIERE au niveau de la FIN et ça tombe bien : on sait insérer à coût constant au niveau de la FIN.

11° Téléchargez le module, et enregistrez le dans un répertoire implementation_file de votre espace de travail. Il faudra impérativement enregistrer le module sous le nom liste_chainee_objet_tete_fin.py.

MODULE Liste Tete et Fin MUABLE

12° Créer dans le même répertoire un programme file_basee_liste_tete_fin.py dont voici le contenu :

"""Module proposant une implémentation d'une File MUABLE
   en utilisant une liste chaînée tete-fin sous forme objet
 
Sur notre exemple :
* L'AVANT de la File est la TETE de la liste chaînée (pour la suppression à coût CST)
* L'ARRIERE de la File est la FIN de la liste chaînée (pour l'insertion à coût CST)
 
Fonctions primitives
--------------------
CST : nouvelle_file() -> 'File'
CST : est_file_vide(f:'File') -> bool
CST : enfiler(f:'File', elt:'Element') -> None
CST : defiler(f:'File NON VIDE') -> 'Element'
CST : lire_avant(f:'File NON VIDE') -> 'Element'
 
"""
 
# Importation
 
from liste_chainee_objet_tete_fin import nouvelle_liste
from liste_chainee_objet_tete_fin import est_liste_vide
from liste_chainee_objet_tete_fin import inserer_fin
from liste_chainee_objet_tete_fin import supprimer_tete
from liste_chainee_objet_tete_fin import premier
 
 
# Fonctions primitives de la File
 
def nouvelle_file() -> 'File':
    """Renvoie une nouvelle File vide"""
    pass
 
def est_file_vide(f:'File') -> bool:
    """Prédicat qui renvoie True si la File est vide"""
    pass
 
def enfiler(f:'File', elt:'Element') -> None:
    """Enfile elt dans la File"""
    pass
 
def defiler(f:'File NON VIDE') -> 'Element':
    """Défile la file f"""
    pass
 
def lire_avant(f:'File') -> 'Element':
    pass
 
# Programme de test
 
if __name__ == '__main__':
    a = nouvelle_file()
    enfiler(a, 0)
    enfiler(a, 5)
    enfiler(a, 10)
    enfiler(a, 15)
 
    s = lire_avant(a)
    assert s == 0
 
    defiler(a)
    s = lire_avant(a)
    assert s == 5

Utiliser une Liste Tete Fin pour implémenter une File

Puisque la suppression est à coût CONSTANT uniquement sur la Tête de la Liste, il faut placer l'Avant de la File de ce côté.

On place donc l'Arrière du côté de la Fin. Attention, pour obtenir une insertion en Fin à coût CONSTANT, il faut connaître la référence de cette Fin !

Les données du point de vue de la File

graph RL I(("+"))-. enfilement .-> D("ARRIERE en FIN de Liste]") --> C["..."] --> B["..."] --> A("AVANT en TETE de Liste") -. défilement .-> S(("-")) style A fill:#f55,stroke:#333,stroke-width:2px style D fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px

Attention, sur cette représentation de la File, on ne représente pas la possibilité de trouver le successeur mais le sens de déplacement des données qui se dirigent inexorablement vers la Tête au fur et à mesure qu'on défile la File. C'est trompeur.

Les données du point de vue de la Liste implémentant les données

graph LR A("AVANT en TETE de Liste") -- succ --> C["..."] -- succ --> B["..."] --succ --> D("ARRIERE en Fin de Liste]") style A fill:#f55,stroke:#333,stroke-width:2px style D fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px

13° Finaliser le module File en réalisant les 5 primitives de la File en utilisant en interne le module Liste qui utilise lui-même en interne une implémentation objet.

graph TB A("file_basee_liste_tete_fin.py") -- importe --> C["liste_chainee_objet_tete_fin"] -- qui utilise en interne l'idée d' --> B["une liste chaînée avec des objets Cellule"]

Il faudra bien entendu comprendre comment utiliser les fonctions importées sur les lignes 20 à 24 depuis le module liste_chainee_objet_tete_fin.

La fonction native help() est votre amie !


>>> help(inserer_fin)
  Help on function inserer_fin in module liste_chainee_objet_tete_fin:
 
  inserer_fin(lst: 'Liste', elt: 'Element') -> None
      Rajoute elt en Fin de liste
 
>>> help(...)

Module File dont l'implémentation est basée sur une liste chaînée construite à partir de cellules objets

"""Module proposant une implémentation d'une File MUABLE
   en utilisant une liste chaînée tete-fin sous forme objet
 
Sur notre exemple :
* L'AVANT de la File est la Tete de la liste chaînée (pour la suppression à coût CST)
* L'ARRIERE de la File est la Fin de la liste chaînée (pour l'insertion à coût CST)
 
Fonctions primitives
--------------------
CST : nouvelle_file() -> 'File'
CST : est_file_vide(f:'File') -> bool
CST : enfiler(f:'File', elt:'Element') -> None
CST : defiler(f:'File NON VIDE') -> 'Element'
CST : lire_avant(f:'File NON VIDE') -> 'Element'
 
"""
 
# Importation
 
from liste_chainee_objet_tete_fin import nouvelle_liste
from liste_chainee_objet_tete_fin import est_liste_vide
from liste_chainee_objet_tete_fin import inserer_fin
from liste_chainee_objet_tete_fin import supprimer_tete
from liste_chainee_objet_tete_fin import premier
 
 
# Fonctions primitives de la File
 
def nouvelle_file() -> 'File':
    """Renvoie une nouvelle File vide"""
    return nouvelle_liste()
     
def est_file_vide(f:'File') -> bool:
    """Prédicat qui renvoie True si la File est vide"""
    return est_liste_vide(f)
     
def enfiler(f:'File', elt:'Element') -> None:
    """Enfile elt dans la File"""
    inserer_fin(f, elt)  # L'insertion en fin de liste est à coût constant
     
def defiler(f:'File NON VIDE') -> 'Element':
    """Défile la file f"""
    return supprimer_tete(f)
     
def lire_avant(f:'File') -> 'Element':
    return premier(f)
 
 
# Programme de test
     
if __name__ == '__main__':
    a = nouvelle_file()
    enfiler(a, 0)
    enfiler(a, 5)
    enfiler(a, 10)
    enfiler(a, 15)
     
    s = lire_avant(a)
    assert s == 0
     
    defiler(a)
    s = lire_avant(a)
    assert s == 5

3 - Implémentation d'une File avec deux Piles

⇩ ⇧ ⤊

Le principe est simple :

Lorsqu'on veut enfiler un élément, on le dépose en réalité dans une Pile d'entrée qu'on nommera pileEntree.
Lorsqu'on veut defiler, on va chercher en réalité le sommet d'une Pile de sortie qu'on nommera pileSortie.

Sur l'image ci-dessous, on a inséré les horaires d'arrivée des clients dans un magasin. Le premier est arrivé à 13h, le suivant à 13h20... Lorsqu'on enfile les heures d'arrivée, on voit bien que la dernière heure est au Sommet de pileEntree.

Le problème vient du fait que lorsqu'on va vouloir défiler ces données, on veut récupérer d'abord le 13h !

Comment faire ?

14° Réflechir à ce problème. Auriez-vous une solution ?

Comme souvent, une fois la solution trouvée cela paraît évident.

Le tout est de trouver l'idée...

Comment alors ?

L'idée est d'inverser les éléments de la Pile d'entrée en les déversant dans la Pile de sortie.

L'ancien Sommet de l'entrée (en rose ici) va bien se retrouver tout en bas de la pile de sortie. Et l'élément qui va se retrouver au Sommet de la pile de Sortie est bien le plus ancien élément de la pile d'Entrée.

Par contre, la subtilité est qu'il ne faire le déversement que la pile de sortie est vide et qu'on veut défiler.

Lorsqu'on veut défiler les données de la File, deux cas se présentent :

SI pileSortie est vide

On déverse d'abord pileEntree dans pileSortie en dépilant les éléments un par un dans l'autre pile : cela va permettre d'inverser les positions respectives du premier arrivé et du dernier arrivé.

Après cette opération, pileEntree est vide.

Ensuite, il suffit de dépiler une fois pileSortie pour obtenir l'élément reçu le plus ancien !

SINON, c'est que pileSortie n'est pas vide.

Pour défiler, il suffit de continuer à dépiler pileSortie.

Il ne faut surtout pas déverser car l'élément le plus ancien non traité est bien le sommet de pileSortie. Si on rajoute les éléments de la pile d'entrée, on va mettre des éléments plus récents au dessus du plus ancien

Les étapes de l'inversion en images :

pileEntree a déjà reçu ceci :

On veut défiler mais pileSortie est vide. Il faut donc déverser pileEntree dans pileSortie. Comment ? Tant que pileEntree n'est pas vide, on la dépile en mémorisant l'ancien sommet qu'on empile dans pileSortie.

Etape 1 : On dépile pileEntree en mémorisant l'ancien sommet (14h30) et on l'empile dans pileSortie

On continue. On dépile pileEntree en mémorisant l'ancien sommet (14h20) et on l'empile dans pileSortie

On continue. On dépile pileEntree en mémorisant l'ancien sommet (14h00) et on l'empile dans pileSortie

Au final, à la fin du déversement, pileEntree sera vide et pileSortie aura de nouveaux éléments et son sommet sera bien le plus ancien élément reçu par la File !

Déversement de la pile d'entrée dans la pile de sortie

Maintenant que pileSortie n'est pas vide, on peut la défiler et obtenir l'élément "13h".
Et on peut continuer à enfiler de nouveaux éléments : ils iront dans pileEntree. D'ailleurs, tant que pileSortie n'est pas vide, ces éléments resteront stocker dans pileEntree.

Nous allons maintenant réaliser cette implémentation de File MUABLE basée sur deux Piles IMMUABLES par exemple.

L'utilisateur écrira donc des instructions de ce type pour manipuler sa File MUABLE :

enfiler(file, 5) pour enfiler 5 dans sa File.

Par contre, comme nos Piles sont immuables, on écrira des choses comme ceci à l'intérieur des fonctions primitives puisqu'on manipulera des Piles IMMUABLES pour implémenter les données de notre Pile MUABLE :

Pour enfiler : pileEntree = empiler(pileEntree, 5).

Pour défiler : pileSortie = defiler(pileSortie).

graph LR I(("+"))-. enfilement .-> D("Pile d'entrée") -- "déversement si sortie vide" --> A("Pile de sortie") -. défilement .-> S(("-")) style A fill:#f55,stroke:#333,stroke-width:2px style D fill:#ff9,stroke:#333,stroke-width:2px

15-A° ENFILEMENT : nous allons stocker les références de nos deux piles dans un tableau que nous nommerons f puisque cette variable permettra de gérer la file.

f = [pileEntree, pileSortie].

Pour accéder à la pileEntree, il suffit donc d'accéder à f[0].
Pour accéder à la pileSortie, il suffit donc d'accéder à f[1].

Voici donc un exemple d'utilisation de la file : on y enfile des éléments qui viennent s'empiler dans la pile d'entrée.


>>> f = nouvelleFile()
>>> f
[(), ()]
 
>>> enfiler(f, 5)
>>> f
[(5, ()), ()]
 
>>> enfiler(f, 10)
>>> enfiler(f, 20)
>>> f
[(20, (10, (5, ()))), ()]

Question : quelle instruction doit-on trouver dans la fonction enfiler() pour parvenir à rajouter un nouvel élément dans la pileEntree IMMUABLE ? A ou B ?

f[0] = empiler(f[0], 5)
empiler(f[0], 5)

Correction ?

...CORRECTION...

Pour obtenir la référence de pileEntree, il faut utiliser effectivement f[0] puisque la pile d'entrée est stockée dans l'indice 0 du tableau f.

Les piles sont IMMUABLES dans cette implémentation : les fonctions "modifiant" les piles renvoient donc une "copie modifiée" de la pile fournie en entrée.

La réponse est donc A :

f[0] = empiler(f[0], 5)

De façon abstraite, cela revient à demander ceci :

pileEntree = empiler(pileEntree, 5)

15-B° LECTURE DE L'AVANT : on désire maintenant lire l'Avant de notre File (le 5 puisque c'est le premier élément qu'on avait inséré), il faudra d'abord regarder si la pile de sortie f[1] est vide, ou pas.

Comme c'est le cas ici, il faudra déverser la pile d'entrée f[0] dans la pile de sortie f[1].


>>> f
[(20, (10, (5, ()))), ()]
 
>>> lire_avant(f)
5
 
>>> f
[(), (5, (10, (20, ())))]
 
>>> enfiler(f, 50)
>>> f
[(50, ()), (5, (10, (20, ())))]
 
>>> lire_avant(f)
5
 
>>> f
[(50, ()), (5, (10, (20, ())))]

Deux question :

sur l'exemple ci-dessus, que voyez-vous de notable sur la position du plus ancien élément (5) stockée avant et après la premier lecture ?
pourquoi le 5 est-il toujours au sommet de la pile de sortie même après avoir enfiler un 50 et demander une deuxième lecture de l'Avant ?

Correction ?

...CORRECTION...

On remarque que le contenu de la pile est inversée. Le 5 est maintenant au sommet de la pile de sortie. Or, ce 5 était le premier arrivé lors du remplissage de la pile d'entrée.

15-C° DEFILEMENT : on veut maintenant défiler notre file, implémentée avec deux piles. Pour cela, il suffit de dépiler la pile de sortie.

f = [pileEntree, pileSortie].


>>> f
[(), (5, (10, (20, ())))]
 
>>> defiler(f)
5
 
>>> f
[(), (10, (20, ()))]

Question quelle instruction doit-on trouver dans la fonction defiler() pour parvenir à supprimer le sommet de la pile de sortie IMMUABLE stockée à l'intérieur de la variable f ?

f[1] = depiler(f[1])
depiler(f[1])

Correction ?

...CORRECTION...

Pour atteindre la pile de sortie, il faut utiliser f[1] puisque la pile de sortie est stockée dans l'indice 1 du tableau f.

L'énoncé dit que nos piles sont IMMUABLES. Si on veut modifier notre liste, il faut donc remplacer par affectation l'ancien contenu par le nouveau.

La réponse est donc A : f[1] = depiler(f[1])

Passons à l'écriture de l'implémentation File avec deux Piles.

Vous disposez plus bas d'un module incorporant une implémentation d'une Pile IMMUABLE (déjà réalisée) et l'ébauche de l'implémentation d'une File MUABLE basée sur l'utilisation de deux Piles.

Vous trouverez plus bas la correction du module complet en cas de problèmes lors de la réalisation du module.

16° Deux questions.

Regarder l'implémentation ci-dessous. Comment se nomment les fonctions permettant de vérifier si une pile ou une file est vide ?
Regarder la fonction nouvelle_file(). Quelle est la structure qui stocke les données de la file ? Que contient cette structure ?

"""Module implémentant un File MUABLE
   en utilisant un tableau de deux Piles
 
Les Piles sont implémentées sous forme de tuples (sommet, reste de la pile)
Les Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]
 
Fonctions primitives de la File
--------------------------------
... : nouvelle_file() -> 'File'
... : est_file_vide(f:'File') -> bool
... : enfiler(f:'File', elt:'Element') -> None
... : defiler(f:'File NON VIDE') -> 'Element'
... : lire_avant(f:'File NON VIDE') -> 'Element'
 
"""
 
# Fonctions primitives des PILES
 
def nouvelle_pile() -> 'Pile':
    """Renvoie une liste vide"""
    return ()
 
def est_pile_vide(p:'Pile') -> bool:
    """Prédicat qui renvoie True si la pile est vide"""
    return p == ()
 
def empiler(p:'Pile', elt:'Element') -> 'Pile':
    """Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile."""
    return (elt, p)
 
def depiler(p:'Pile NON VIDE') -> 'Pile':
    """Renvoie une nouvelle pile où on a supprimé l'ancien sommet d'une pile NON VIDE"""
    return p[1]
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    """Renvoie la valeur stockée au sommet d'une pile NON VIDE"""
    return p[0]
 
# Fonctions d'interface de la FILE
 
def nouvelle_file() -> 'File':
    """Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]"""
    pile_entree = nouvelle_pile() # inputStack en anglais
    pile_sortie = nouvelle_pile() # outputStack en anglais
    return [pile_entree, pile_sortie]
 
def est_file_vide(f:'File') -> bool:
    """Prédicat qui renvoie True si la File est entièrement vide, False sinon"""
    return est_pile_vide(f[0]) and est_pile_vide(f[1])
 
def enfiler(f:'File', elt:'Element') -> None:
    """Enfile l'élement elt dans la file f"""
    pass
 
def defiler(f:'File NON VIDE') -> 'Element':
    """Défile le sommet de la file NON VIDE f et le renvoie"""
    pass
 
def lire_avant(f:'File NON VIDE') -> 'Element':
    """Renvoie le sommet de la file NON VIDE f sans la modifier"""
    pass
 
# Fonctions hors interface
 
def deverser_entree_vers_sortie(f:'File') -> None:
    """Déverse entièrement la pile d'entrée dans la pile de sortie"""
    while not est_pile_vide(f[0]):
        elt = lire_sommet(f[0])
        f[0] = depiler(f[0])
        f[1] = empiler(f[1], elt)
 
 
# Programme de test
     
if __name__ == '__main__':
    a = nouvelle_file()
    enfiler(a, 0)
    enfiler(a, 5)
    enfiler(a, 10)
    enfiler(a, 15)
     
    s = lire_avant(a)
    assert s == 0
     
    defiler(a)
    s = lire_avant(a)
    assert s == 5

Correction ?

...CORRECTION...

On constate que les fonctions se nomment est_pile_vide() et est_file_vide().

La FILE est implémentée sous la forme d'un tableau de deux éléments : l'indice 0 correspond à la pile d'entrée et l'indice 1 correspond à la pile de sortie.

f = [pileEntree, pileSortie].

17-A° Créer la fonction enfiler() après avoir étudié le prototype pour savoir ce qu'elle doit recevoir et renvoyer. Pensez à aller revoir les QCM précédents si vous n'arrivez pas à trouver ce qu'il faut y faire.

Prototype

enfiler(f:'File', elt:'Element' ) -> None

17-B° Expliquer comment la fonction deverser_entree_vers_sortie() réalise le déversement de la pile d'entrée vers la pile de sortie.

def deverser_entree_vers_sortie(f:'File') -> None:
    """Déverse entièrement la pile d'entrée dans la pile de sortie"""
    while not est_pile_vide(f[0]):
        elt = lire_sommet(f[0])
        f[0] = depiler(f[0])
        f[1] = empiler(f[1], elt)

Notez bien que cette fonction ne fait pas partie de l'interface : l'utilisateur n'est pas censé faire cela lui-même : ce sont les fonctions d'interface defiler() et lire_avant() qui en font l'appel au besoin. L'utilisateur n'est pas autorisé à l'utiliser puisqu'elle ne figure pas dans la liste des fonctions d'interface utilisables.

17-C° Créer la fonction lire_avant(). Attention, pensez à vérifiez d'abord si la pile de sortie est vide. Dans ce cas, il faudra utiliser la fonction deverser_entree_vers_sortie() pour remplir la file de sortie.

On pourra ensuite lire le sommet de la pile de sortie.

Prototype

lire_avant(f:'File NON VIDE') -> 'Element'

17-D° Créer la fonction defiler() qui devra également d'abord utiliser deverser_entree_vers_sortie() si la pile de sortie est vide. Attention, notez bien que cette fonction travaille sur une File MUABLE et qu'on en profite pour renvoyer l'élément qu'on vient de supprimer.

Prototype

defiler(f:'File NON VIDE') -> 'Element'

Le code final corrigé est en fin de section.

18° Utiliser des instructions dans la console pour enfiler 5, 10, 20. Défiler (vous devriez obtenir 5). Enfiler ensuite un 40. Défiler jusqu'à bout. Vous devriez obtenir le 10, le 20 puis le 40.

Correction ?

...CORRECTION...


>>> f = nouvelle_file()
>>> enfiler(f, 5)
>>> f
[(5, ()), ()]
 
>>> enfiler(f, 10)
>>> f
[(10, (5, ())), ()]
 
>>> enfiler(f, 20)
>>> file
[(20, (10, (5, ()))), ()]
 
>>> defiler(f)
5
 
>>> f
[(), (10, (20, ()))]
 
>>> enfiler(f, 40)
>>> f
[(40, ()), (10, (20, ()))]
 
>>> defiler(f)
10
 
>>> f
[(40, ()), (20, ())]
 
>>> defiler(f)
20
 
>>> f
[(40, ()), ()]
 
>>> defiler(f)
40
 
>>> f
[(), ()]

19° Quel est le coût de la fonction enfiler() ?

Constant 𝞗(1)
Linéaire en 𝞗(n)
Linéaire en 𝞞(n)
Quadratique en 𝞗(n²)

Correction ?

...CORRECTION...

La fonction enfiler() consiste à :

Accéder à une case d'un tableau statique dont on connait l'indice : coût constant
Utiliser la fonction d'interface des piles empiler() : coût constant avec l'implémentation (sommet, reste de la pile)

La fonction enfiler() est donc à coût constant.

20° Quel est le coût de la fonction lire_avant() dans le meilleur des cas ? dans le pire des cas ?

Constant 𝞗(1) dans le meilleur des cas et dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞗(n) dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞞(n) dans le pire des cas.
Linéaire en 𝞗(n) dans le meilleur des cas et dans le pire des cas.
Linéaire en 𝞞(n) dans le meilleur des cas et dans le pire des cas.

Correction ?

...CORRECTION...

Dans le meilleur des cas, la fonction lire_avant() consiste à :

Accéder à une case d'un tableau statique dont on connait l'indice : coût constant
Utiliser la fonction d'interface des piles lire_sommet() : coût constant avec l'implémentation (sommet, reste de la pile)

La fonction lire_avant() est donc à coût constant dans le meilleur des cas.

Dans le pire des cas, il va falloir déverser les données (intégralement stockées dans la pile d'entrée) dans la pile de sortie avant toute lecture. Comme on doit déplacer les données une par une de la pile d'entrée vers la pile de sortie, on retrouve un coût linéaire. Et comme on doit vraiment gérer toute les données, la complexité est bien en 𝞗(n).

Il s'agit donc de la réponse B.

23° Quel est le coût de la fonction defiler() dans le meilleur des cas ? dans le pire des cas ?

Constant 𝞗(1) dans le meilleur des cas et dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞗(n) dans le pire des cas.
Constant 𝞗(1) dans le meilleur des cas et linéaire en 𝞞(n) dans le pire des cas.
Linéaire en 𝞗(n) dans le meilleur des cas et dans le pire des cas.
Linéaire en 𝞞(n) dans le meilleur des cas et dans le pire des cas.

Correction ?

...CORRECTION...

C'est exactement comme la lecture de l'avant. La réponse est donc la réponse B.

Implémentation n° 1 d'une File MUABLE basée à l'interne sur l'utilisation de deux Piles IMMUABLES

Principe général

On enfile en empilant les donénes dans une pile d'entrée.

On déverse la pile d'entrée vers la pile de sortie lorsqu'on veut utiliser la pile de sortie mais que celle-ci est vide.

On défile en dépilant la pile de sortie.

Coût du défilement

On notera que le coût du défilement dépend de la pile de sortie.

Si elle contient encore des données, le coût est constant.

Si elle est vide, il faut d'abord déverser une fois à coût linéaire les données situées dans la pile d'entrée.

Comme avec le tableau dynamique, on retrouve alors la notion de coût amorti : on peut considérer que le coût est globalement constant puisqu'on va réaliser ce déversement assez peu souvent. Sans faire de théorie, on voit que le coût va être souvent constant et uniquement parfois linéaire. C'est pour cela qu'on considère que le coût amorti est constant.

Module 1

AVANTAGE : le module est indépendant de tout autre module.

DESAVANTAGE : on a dû créer un type Pile local pour créer notre File, alors qu'on a déjà créer un Pile plusieurs fois auparavant...

"""Module implémentant un File MUABLE
   en utilisant un tableau de deux Piles
 
Les Piles sont implémentées sous forme de tuples (sommet, reste de la pile)
Les Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]
 
Fonctions primitives de la File
--------------------------------
CST : nouvelle_file() -> 'File'
CST : est_file_vide(f:'File') -> bool
CST : enfiler(f:'File', elt:'Element') -> None
CST* : defiler(f:'File NON VIDE') -> 'Element'
CST : lire_avant(f:'File NON VIDE') -> 'Element'
 
"""
 
# Fonctions primitives des PILES
 
def nouvelle_pile() -> 'Pile':
    """Renvoie une liste vide"""
    return ()
 
def est_pile_vide(p:'Pile') -> bool:
    """Prédicat qui renvoie True si la pile est vide"""
    return p == ()
 
def empiler(p:'Pile', elt:'Element') -> 'Pile':
    """Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile."""
    return (elt, p)
 
def depiler(p:'Pile NON VIDE') -> 'Pile':
    """Renvoie une nouvelle pile où on a supprimé l'ancien sommet d'une pile NON VIDE"""
    return p[1]
 
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
    """Renvoie la valeur stockée au sommet d'une pile NON VIDE"""
    return p[0]
 
# Fonctions primitives et d'interface de la File
 
def nouvelle_file() -> 'File':
    """Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]"""
    pile_entree = nouvelle_pile() # inputStack en anglais
    pile_sortie = nouvelle_pile() # outputStack en anglais
    return [pile_entree, pile_sortie]
 
def est_file_vide(f:'File') -> bool:
    """Prédicat qui renvoie True si la File est entièrement vide, False sinon"""
    return est_pile_vide(f[0]) and est_pile_vide(f[1])
 
def enfiler(f:'File', elt:'Element') -> None:
    """Enfile l'élement elt dans la file f"""
    f[0] = empiler(f[0], elt)
 
def defiler(f:'File NON VIDE') -> 'Element':
    """Défile le sommet de la file NON VIDE f et le renvoie"""
    if est_pile_vide(f[1]):
        deverser_entree_vers_sortie(f)
    valeur = lire_sommet(f[1])
    f[1] = depiler(f[1])
    return valeur
 
def lire_avant(f:'File NON VIDE') -> 'Element':
    """Renvoie le sommet de la file NON VIDE f sans la modifier"""
    if est_pile_vide(f[1]):
        deverser_entree_vers_sortie(f)
    return lire_sommet(f[1])
 
# Fonctions hors interface
 
def deverser_entree_vers_sortie(f:'File') -> None:
    """Déverse entièrement la pile d'entrée dans la pile de sortie"""
    while not est_pile_vide(f[0]):
        elt = lire_sommet(f[0])
        f[0] = depiler(f[0])
        f[1] = empiler(f[1], elt)
 
 
# Programme de test
     
if __name__ == '__main__':
    a = nouvelle_file()
    enfiler(a, 0)
    enfiler(a, 5)
    enfiler(a, 10)
    enfiler(a, 15)
     
    s = lire_avant(a)
    assert s == 0
     
    defiler(a)
    s = lire_avant(a)
    assert s == 5

Implémentation n° 2 d'une File MUABLE basée à l'interne sur l'utilisation de deux Piles IMMUABLES

Le problème de l'implémentation précédente ?

On utilise le type Pile mais on crée intégralement le type dans le module plutôt que d'utiliser une Pile IMMUABLE déjà implémentée ailleurs.

Module 2 dépendant du module pile_immuable

Avantage : le module File lui-même est plus court et on peut changer facilement de support pour gérer les Piles.

Désavantage : le module File possède une dépendance par rapport au module Pile.

"""Module implémentant un File MUABLE
   en utilisant un tableau de deux Piles
Les Files sont implémentées sous forme de tableaux [pileEntree, pileSortie]
 
Fonctions primitives de la File
--------------------------------
CST : nouvelle_file() -> 'File'
CST : est_file_vide(f:'File') -> bool
CST : enfiler(f:'File', elt:'Element') -> None
CST* : defiler(f:'File NON VIDE') -> 'Element'
CST : lire_avant(f:'File NON VIDE') -> 'Element'
 
"""
 
# Importation
 
from pile_immuable import nouvelle_pile
from pile_immuable import est_pile_vide
from pile_immuable import empiler
from pile_immuable import depiler
from pile_immuable import lire_sommet
 
# Fonctions primitives et d'interface de la File
 
def nouvelle_file() -> 'File':
    """Renvoie la référence d'une File sous forme d'un tableau [pileEntree, pileSortie]"""
    pile_entree = nouvelle_pile() # inputStack en anglais
    pile_sortie = nouvelle_pile() # outputStack en anglais
    return [pile_entree, pile_sortie]
 
def est_file_vide(f:'File') -> bool:
    """Prédicat qui renvoie True si la File est entièrement vide, False sinon"""
    return est_pile_vide(f[0]) and est_pile_vide(f[1])
 
def enfiler(f:'File', elt:'Element') -> None:
    """Enfile l'élement elt dans la file f"""
    f[0] = empiler(f[0], elt)
 
def defiler(f:'File NON VIDE') -> 'Element':
    """Défile le sommet de la file NON VIDE f et le renvoie"""
    if est_pile_vide(f[1]):
        deverser_entree_vers_sortie(f)
    valeur = lire_sommet(f[1])
    f[1] = depiler(f[1])
    return valeur
 
def lire_avant(f:'File NON VIDE') -> 'Element':
    """Renvoie le sommet de la file NON VIDE f sans la modifier"""
    if est_pile_vide(f[1]):
        deverser_entree_vers_sortie(f)
    return lire_sommet(f[1])
 
# Fonctions hors interface
 
def deverser_entree_vers_sortie(f:'File') -> None:
    """Déverse entièrement la pile d'entrée dans la pile de sortie"""
    while not est_pile_vide(f[0]):
        elt = lire_sommet(f[0])
        f[0] = depiler(f[0])
        f[1] = empiler(f[1], elt)
 
 
# Programme de test
     
if __name__ == '__main__':
    a = nouvelle_file()
    enfiler(a, 0)
    enfiler(a, 5)
    enfiler(a, 10)
    enfiler(a, 15)
     
    s = lire_avant(a)
    assert s == 0
     
    defiler(a)
    s = lire_avant(a)
    assert s == 5

4 - Autres implémentations

⇩ ⇧ ⤊

Il existe bien d'autres implémentations. Celles que nous avons vu permettent de réaliser des Files sans limite de taille.

En utilisant un dictionnaire et un tableau statique, on peut par contre réaliser assez facilement une File possédant une taille limite.

Comment ?

La File est un dictionnaire possèdant les clés suivantes :

{'avant': None, 'arriere': None, 'taille': 0, 'max': 5, 'data': [None, None, None, None, None]}

'avant' : la valeur associée à cette clé est l'indice de la case du tableau contenant l'Avant (la case à lire ou défiler)
'arrière' : la valeur associée à cette clé est l'indice de la case du tableau contenant l'Arrière
'taille' : le nombre de cases du tableau réellement utilisées
'max' : le nombre de cases du tableau
'data' : la référence du tableau statique qui va contenir les données

Exemple concret d'utilisation et d'évolution des contenus


>>> file = nouvelleFile()
>>> file
{'avant': None, 'arriere': None, 'taille': 0, 'max': 5, 'data': [None, None, None, None, None]}
 
>>> enfiler(10, file)
>>> file
{'avant': 0, 'arriere': 0, 'taille': 1, 'max': 5, 'data': [10, None, None, None, None]}
 
>>> enfiler(20, file)
>>> file
{'avant': 0, 'arriere': 1, 'taille': 2, 'max': 5, 'data': [10, 20, None, None, None]}
 
>>> enfiler(30, file)
>>> file
{'avant': 0, 'arriere': 2, 'taille': 3, 'max': 5, 'data': [10, 20, 30, None, None]}
 
>>> enfiler(100, file)
>>> file
{'avant': 0, 'arriere': 3, 'taille': 4, 'max': 5, 'data': [10, 20, 30, 100, None]}
 
>>> defiler(file)
10
 
>>> file
{'avant': 1, 'arriere': 3, 'taille': 3, 'max': 5, 'data': [10, 20, 30, 100, None]}
 
>>> defiler(file)
20
 
>>> file
{'avant': 2, 'arriere': 3, 'taille': 2, 'max': 5, 'data': [10, 20, 30, 100, None]}
 
 
>>> enfiler(6, file)
>>> file
{'avant': 2, 'arriere': 4, 'taille': 3, 'max': 5, 'data': [10, 20, 30, 100, 6]}
 
 
>>> enfiler(15, file)
>>> file
{'avant': 0, 'arriere': 0, 'taille': 4, 'max': 5, 'data': [15, 20, 30, 100, 6]}

Un beau sujet d'épreuve ou de DS non ?

Activité publiée le 14 10 2020
Dernière modification : 27 11 2022
Auteur : ows. h.

⏪

⏫

⏩