Aller au contenu principal

File

Historique​

La théorie des files d'attente devint un domaine de recherches en 1917, issue de la gestion des réseaux téléphoniques de Copenhague par l’ingénieur danois Erlang.

En informatique, les files étaient initialement employées pour gérer l'accès à des ressources partagées. Elles servent maintenant principalement comme tampons lorsque des données ou des opérations ne peuvent pas être traitées immédiatement.

Description​

La file (queue) est régulièrement utilisée pour temporiser :

  • Type : F.I.F.O. (First-In, First-Out)
  • Accès : Devant (front) et Derrière (back)
  • Fonctionnalités : Enfiler (push) et Défiler (pop)

Implémentations​

Statique​

L'implémentation statique permet d'utiliser une file dont la capacité est fixe en mémoire centrale.

Enfiler​

Empiler

Défiler​

Dépiler

Dynamique​

L'implémentation dynamique permet d'utiliser une file dont la capacité est dynamique en mémoire centrale :

File

Circulaire​

Il est possible d'éviter un pointeur avec une implémentation circulaire :

File circulaire

Le noeud à la droite du dernier noeud est toujours le premier noeud.

Double​

Une double-file (deque) permet d'enfiler et de défiler au devant et au derrière.