Page MenuHomePhabricator
Contents

La gestions des files d'attentes
Updated 189 Days AgoPublic

En informatique, une file d'attente est un ensemble d'éléments qui sont maintenues dans une séquence et peuvent être modifiées par l'ajout ou la suppression d'éléments à l'une extrémité de son conteneur (le tableau). Il existe deux familles d'algorithme selon ce que l'on souhaite faire.

  • Une pile est une structure de données fondée sur le principe « dernier arrivé, premier sorti » (LIFO). On peut facilement se représenter l'idée en imaginant une pile d'assiettes que l'on empile les unes sur les autres.
  • Une file est une structure de données fondée sur le principe « premier arrivé, premier sorti » (FIFO). Les files sont similaires à l'idée que les gens font la queue à la caisse d'un magasin.
Une pileUne file
ezgif.com-gif-maker_7.gif (460×480 px, 584 KB)
ezgif.com-gif-maker_5.gif (460×480 px, 652 KB)

La gestion des files d'attente sont organisées à l'aide de primitive homologue. On utilisera par contre le vocabulaire le plus approprié selon le type choisi pour éviter une ambiguïté. Par exemple, pour ajouter un élément on dira "empiler" ou "enfiler". Il est également intéressant de savoir si le nombre d'éléments dans la structure. En effet, cela permet de savoir si la file est vide ou pleine.

La pile

Une pile peut être est gérée d'une façon similaire à la méthode que nous avons vue pour les ensembles. Nous pouvons utiliser la variable compteur comme étant l'endroit où nous allons insérer l'élément suivant.

STRUCTURE PILE:
   VARIABLE top: ENTIER
   VARIABLE N: ENTIER
   VARIABLE conteneur: TABLEAU DE N ENTIER
FIN STRUCTURE
empiler
FONCTION PUSH(p: PILE, v: ENTIER)
    P.conteneur[ P.top ] <- v
    P.top <- P.top + 1
FIN FONCTION
dépiler
FONCTION POP(p: PILE)
    VARIABLE v: ENTIER

    v <- P.conteneur[ P.top-1 ]
    P.top <- P.top - 1

    RETOURNER v
FIN FONCTION
est vide
FONCTION IS_EMPTY(p: PILE)
    RETOURNER P.top == 0
FIN FONCTION
est pleine
FONCTION IS_FULL(p: PILE)
    RETOURNER P.top == P.N
FIN FONCTION

La file

Une file est un peu plus complexe que l'autre méthode. En réalité, nous aurons besoins ici de deux variables pour savoir quelle est la case du début et quelle case est la fin de la file.

Untitled (2).png (473×512 px, 53 KB)

Cette structure peut être placée dans ce qu'on appelle un buffer circulaire. Ce dernier est en réalité un tableau où nous utilisons l'opération modulo. En effet, lorsqu'on prend la dernière case du tableau +1 %N, nous retournons en réalité au début de ce dernier. Comme s'il s'agissait d'un tableau circulaire.

buffer_anim.gif (282×400 px, 54 KB)

STRUCTURE FILE:
   VARIABLE head, tail: ENTIER
   VARIABLE N: ENTIER
   VARIABLE tableau: TABLEAU DE N ENTIER
FIN STRUCTURE
enfiler
FONCTION PUSH(p: FILE, v: ENTIER)
    P.conteneur[ P.head ] <- v
    P.head <- (P.head + 1) % P.max
FIN FONCTION
défiler
FONCTION POP(p: FILE)
    VARIABLE v: ENTIER

    v <- P.conteneur[ P.tail ]
    P.tail <- (P.tail + 1) % P.max

    RETOURNER v
FIN FONCTION
est vide
FONCTION IS_EMPTY(p: FILE)
    RETOURNER p.head== p.tail
FIN FONCTION
est pleine
FONCTION IS_FULL(p: FILE)
    RETOURNER (p.head+1) % p.N == p.tail
FIN FONCTION
Last Author
Steve
Last Edited
Jan 18 2021, 1:47 PM

Event Timeline

Steve created this object.
Steve changed the title from Queue to La gestions des files d'attentes.Jan 14 2021, 2:16 PM
Steve edited the content of this document. (Show Details)