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 accessible par ses deux extrémités, la tête et la queue. Les quatre opérations sont : tester si la file est vide, enfiler, c'est-à-dire entrer dans la file (<< à la queue >>), défiler, c'est-à-dire sortir de la file en tête, et enfin prendre la valeur de tête. Voici leur interface en Java :

interface File {
  boolean estVide();
  void enfiler(Object o);
  Object tête();
  Object défiler();
}

 

Il existe plusieurs implémentations des files : par un tableau dont l'index est géré de façon circulaire, par une liste doublement chaînée, l'entrée se faisant à l'une des extrémités de la liste et la sortie à l'autre extrémité. C'est le choix retenu dans l'implémentation suivante, les opérations étant déléguées à une liste doublement chaînée de type java.util.LinkedList.

import java.util.LinkedList;

public class FileParListe implements File {
  private LinkedList contenu;

  FileParListe() {
    contenu = new LinkedList();
  }

  public boolean estVide() {
    return contenu.isEmpty();
  }
  
  public void enfiler(Object o) {
    contenu.addFirst(o);
  }

  public Object tête() {
    return contenu.getLast();
  }
  
  public Object défiler() {
    return contenu.removeLast();
  }
}