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.

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. On utilise les deux types d'exception underflow_error et overflow_error déclarées dans <stdexcept>.

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

#include <stdexcept>

void mk_empty_queue (queue& q) {
  q.head = 0;
  q.tail = 0;
  q.full = 0;
}
  
bool is_empty_queue(const queue& q) {
  return (q.head == q.tail) && !q.full;
}

void in(const queue_data& x, queue& q) {
  if (!q.full) {
    q.content[q.tail] = x;
    q.tail = (q.tail +1) % MAX;
  } else throw overflow_error("pile pleine");
  if (q.head == q.tail) q.full = 1;
}

queue_data head(const queue& q) {
  if (is_empty_queue (q)) 
    throw underflow_error("pile vide");
  else
    return q.content[q.head];
}

queue_data out(queue& q) {
  if (is_empty_queue(q)) 
    throw underflow_error("pile vide");
  else {
    int h = q.head;
    q.head = (h+1) % MAX;
    if (h == q.tail) {
      q.full = 0;
    }
    return q.content[h];
  }
}

Signalons que la bibliothèque standard de C++ contient des types génériques pour les piles, les files et bien d'autres types << conteneurs >> de données.