File (structure de données)

---

Structure de donnée « file »

---

Un file est une structure de données concrète, associé au type abstrait « PEPS ».

SD concrète

• nom
  • file
• nom anglais
  • queue
• type
  • séquentielle

---

Structure de données concrète.

Informations supplémentaires
Utilisée en ordonnancement, mémoire tampon ("buffer" en anglais)

Définition

Une file est basée sur la structure de données abstraite « PEPS » (Premier Entré, Premier Sorti), une structure séquentielle permettant de contenir des objets, pouvant être enfilée (ajout d'objet) et défilée (retrait d'objet).

Comme son nom l'indique, elle fonctionne comme une file d'attente : le premier objet entré est le premier objet sorti, et ainsi de suite.

Implémentation

Voici un tutoriel expliquant comment implémenter un file en Scratch.

Implémentation naïve

L'implémentation suivante est rudimentaire et adaptée aux usages simples de la structure de données concrète.

définir file.vider
mettre [file v] à [nil]
supprimer tous les éléments de la liste [file v]

définir file.enfiler (valeur)
mettre [file v] à [nil]
ajouter (valeur) à [file v]::list

définir file.regarder
mettre [file v] à (élément [1] de [file v])

définir file.défiler
mettre [file v] à (élément [1] de [file v])
supprimer l'élément [1] de [file v]

définir file.est vide ?
mettre [file v] à <(longueur de [file v]) = [0]>

Complexité

On note n la longueur de la file. Voici la complexité des primitives attendues :

• Complexité (enfiler) :

  O(1)

  .
• Complexité (défiler) :

  O(n)

  .

Autres implémentations

Implémentation cyclique

Une méthode d'implémentation des files plus performante est la méthode cyclique.

 Info :

Comme entendu par le terme cyclique, cette méthode consiste à utiliser un tableau de taille fixe pré-construit et de l'utiliser de manière circulaire.

Le seul défaut de cette méthode est que la taille maximale de la file est limitée.

Implémentation

définir file.créer (capacité)
mettre [file v] à [nil]
mettre [file.marque v] à [0]
mettre [file.taille v] à [0]
supprimer tous les éléments de la liste [file v]
répéter (capacité) fois
    ajouter [nil] à [file v]::list
fin

définir file.enfiler (valeur)
mettre [file v] à [nil]
si < (file.taille) < (longueur de [file v]) > alors
mettre [file v] à [0]
remplacer l'élément ([1] + (((file.marque) + (file.taille)) modulo (longueur de [file v]))) de la liste [file v] par (valeur)
ajouter [1] à [file.taille v]
fin

définir file.défiler
mettre [file v] à [nil]
si <(file.taille) > [0]> alors
mettre [file v] à (élément ([1] + (file.marque)) de [file v])
mettre [file.marque v] à (((file.marque) + [1]) modulo (longueur de [file v]))
fin

définir file.est vide ?
mettre [file v] à <(file.taille) = [0]>

 Idée :

Il est possible d'implémenter deux primitives supplémentaires non détaillées par le type abstrait :

définir file.élément (i)
mettre [file v] à [nil]
si <non <(i) > (file.taille)>> alors
mettre [file v] à (élément ((i) + (((file.marque) + (file.taille)) modulo (longueur de [file v]))) de [file v])
fin

définir file.est pleine ?
mettre [file v] à <(file.taille) = (longueur de [file v])>

Complexité

Toutes les primitives sont en

O(1)

. Le constructeur (créer) a pour complexité

O(capacité)

.

Voir aussi

• File sur Wikipédia ;
• type abstrait PEPS sur Wikipédia ;
• Structure de données et type abstrait ;
• Langage Scratch
• Tutoriels