Première partie
Objectifs d'apprentissage
- Utiliser des files afin de résoudre des problèmes.
- Implémenter une file d'attente à l'aide de tableaux et des éléments chaînés.
Introduction
Il y a plusieurs applications des files dans la vie de tous les jours. Les files d'attente en sont un bon exemple. Afin d'améliorer le service à la clientèle, les gestionnaires cherchent des techniques permettant de réduire le temps moyen d'attente ou la longueur moyenne des files. Pour les compagnies aériennes, on a fait l'introduction de files d'attente séparées pour les voyageurs adhérant à un programme de fidélité (frequent flyers), en plus des files normales. Pour les supermarchés, nous avons fait l'ajout de files express, en plus des files normales. Ce sont là des façons de réduire le temps d'attente.
Cependant, les gestionnaires ont besoin d'outils leur permettant de comparer plusieurs scénarios afin d'améliorer les services à moindres coûts. Ils doivent donc connaître le temps moyen d'attente pour chaque scénario.
Il y a deux grandes approches permettant de déterminer ces statistiques. Une branche des mathématiques (Queueing theory) étudie spécifiquement ces questions. L'approche alternative consiste à développer une simulation informatique de ces systèmes et de mesurer les valeurs de certains paramètres à l'aide de la simulation.
Pour ce laboratoire, nous développons une simulation des files d'attente pour un supermarché ayant des files express ainsi que des files normales. Les files d'attente seront modélisées à l'aide de files (objets réalisant l'interface Queue).
Implémentation d'une file
Avant tout, assurez-vous de bien comprendre l'implémentation d'une file. D'abord, nous verrons comment implémenter une file à l'aide d'un tableau.
Les méthodes
public interface Queue<E> {
public abstract void enqueue( E obj );
public abstract E dequeue();
public abstract boolean isEmpty();
public abstract int size();
}- void enqueue: ajouter un élément à l'arrière de la file
- E dequeue: retire et retourne l'élément au début de la file
- boolean isEmpty: retourne true si la file est vide, false autrement
- int size: retourne le nombre d'éléments dans la file
L'implémentation avec un tableau
Une file doit toujours respecter le principe de first in first out (FIFO) (premier entré premier sorti). Vous remarquerez donc dans l'implémentation de ArrayQueue l'usage de front (devant) qui indique l’index du premier élément de la file (donc le prochain à sortir) ainsi que rear (arrière) indiquant l’index du dernier élément de la file (-1 si la file est vide). La variable size permet de conserver la taille réelle de notre file (n'oubliez pas que elems.length n'équivaut pas à size à moins que la file soit pleine!). Enfin, c'est dans un tableau E elems[] que les éléments de la file seront sauvegardés.
1 public class ArrayQueue<E> implements Queue<E> {
2
3 // Constant
4
5 private static final int MAX_QUEUE_SIZE = 10000;
6
7 // Instance variables
8
9 private E[] elems; // stores the elements of this queue
10 private int front, rear, size;
11
12 @SuppressWarnings( "unchecked" )
13
14 public ArrayQueue() {
15 elems = (E []) new Object[MAX_QUEUE_SIZE];
16 front = 0;
17 rear = -1;
18 size = 0;
19 }
20
21 // Instance methods
22
23 public int size() {
24 return size;
25 }
26
27 public boolean isEmpty() {
28 return size == 0;
29 }
30
31 public boolean isFull() {
32 return size == MAX_QUEUE_SIZE;
33 }
34
35 public void enqueue( E elem ) {
36
37 // pre-condition: ???
38
39 if ( rear == ( MAX_QUEUE_SIZE -1 ) ) {
40
41 int j=0;
42 for ( int i=front; i<=rear; i++ ) {
43 elems[ j++ ] = elems[ i ];
44 }
45
46 front = 0;
47 rear = size - 1;
48
49 }
50
51 elems[ ++rear ] = elem;
52 size++;
53 }
54
55 public E dequeue() {
56
57 // pre-condition: ???
58
59 E saved = elems[ front ];
60 elems[ front ] = null; // scrubbing the memory!
61
62 front++;
63 size--;
64
65 return saved;
66 }
67
68 }Remarque: lorsque nous retirons l'élément à la position front du tableau dans la méthode dequeue, nous assignons en fait la valeur null à cet élément et incrémentons front afin que le prochain élément dans la file devienne le premier. Ceci cause donc un décalage dans le tableau où les premiers éléments sont null jusqu'à la position front. Lorsque le tableau elems[] avec lequel nous implémentons notre file devient plein, il est fort probable qu'en réalité il y ait de l'espace dans les premières positions du tableau qui aurait pu être dequeue. Les lignes 39 à 49 permettent donc de décaler ce tableau vers la gauche dans le cas où la variable rear aurait atteint la taille maximale du tableau!
Prenez le temps de déterminer les pré-conditions de chacune des méthodes.
L'implémentation avec des éléments chaînés
public class LinkedQueue<E> implements Queue<E> {
private static class Elem<T> {
private T value;
private Elem<T> next;
private Elem(T value, Elem<T> next) {
this.value = value;
this.next = next;
}
}
private Elem<E> front;
private Elem<E> rear;
private int size;
public LinkedQueue() {
size = 0;
}
public int size() {
return size;
}
public void enqueue(E value) {
Elem<E> newElem;
newElem = new Elem<E>(value, null );
if (rear == null) {
front = rear = newElem;
} else {
rear.next = newElem;
rear = newElem;
}
size++;
}
public E dequeue() {
E result = front.value;
if (front != null && front.next == null) {
front = rear = null;
} else {
front = front.next;
}
size--;
return result;
}
public boolean isEmpty() {
return front == null;
}
}Cette implémentation diffère de celle vue précédemment. Nous utilisons cette fois 3 variables d'instance, soit Elem front, Elem rear et int size. Qu'est-ce que cet objet de type Elem? Il provient de la classe imbriquée statique privée Elem (private static class) dans laquelle sont sauvegardées la valeur réelle de l'élément de la file (un type T générique!) ainsi qu'une référence au prochain Elem de la file. Ainsi, front est une référence au premier Elem de la file, tandis que rear est le dernier Elem de la file.
Réflexion:
- Dans quel cas est-ce que front == rear?
- La file peut-elle être pleine?
- Sans la variable size, comment pourrions-nous déterminer la taille de notre file?
Figure 1 : Les principales classes de la simulation.