Files

    Les files (en anglais queue ) sont une autre structure linéaire dont l'usage est typique des << files d'attente >> d'un service (d'un guichet, d'une liste d'attente, etc) : le premier arrivé est le premier servi (en anglais first in, first out ou FIFO ). Contrairement aux piles, une file est accédée par ses deux extrémités, la tête et la queue.

Les opérations sont : entrer dans la file (à la queue, comme tout le monde), sortir de la file (en tête), prendre la valeur de tête, tester si la file est vide.

  

Figure 18: Fonctionnement d'une file

Comme pour les piles, l'implémentation des files utilise un tableau, mais cette fois-ci avec deux indices indiquant la tête (head ) et la queue (tail ). On utilise le tableau de façon circulaire : la file est vide si les valeurs $h$ de head et $t$ de tail sont égales. Les entrées dans la file se font par la droite ; une file f non vide a la forme f.valeur[$h$] (le prochain sorti), ..., f.valeur[$t-1$] (le dernier entré) ; si $t=$MAX, le prochain élément sera entré dans le tableau à l'indice 0 ; un troisième champ, full, est nécessaire pour distinguer une file vide d'une file pleine.

typedef struct {
  int head, tail, full;
  queue_data content[MAX];
} queue;

  

Figure 19: Représentation d'une file : deux configurations possibles

void mk_empty_queue (queue *q) {
  q->head = q->tail = q->full =0;
}
  
int is_empty_queue(queue *q) {
  return (q->head == q->tail) && !q->full;
}

void in(queue_data x, queue *q) {
  if (!q->full) {
    q->content[q->tail] = x;
    q->tail = (q->tail +1) % MAX;
  } else {
    fprintf(stderr, "file pleine\n");
    exit(1);
  }
  if (q->head == q->tail) {
    q->full = 1;
  }
}

queue_data head(queue *q) {
  if (is_empty_queue (q)) {
    fprintf(stderr, "file vide\n");
    exit(1); 
  } else {
    return q->content[q->head];
  }
}

queue_data out(queue *q) {
  if (is_empty_queue(q)) {
    fprintf(stderr, "file vide\n");
    exit(1); 
  } else {
    int h = q->head;
    q->head = (h +1) % MAX;
    if (h == q->tail) {
      q->full = 0;
    }
    return q->content[h];
  }
}