Correction : Files

ImplémentationS d'une file

Version tableau de taille fixe : file linéaire

Principe

C'est à peine plus délicat à gérer qu'une pile :

• on utilise deux "pointeurs", tete et queue, dont la valeur sera l'indice de l'élément du tableau correspondant respectivement à la tête et à la queue de la file.
• ces deux pointeurs seront tous les deux initialisés de façon à correspondre soit au début du tableau, soit à sa fin. Par exemple, pour la version "début", on les initialisera à -1 ( pour la version "fin", à N = nombre d'éléments du tableau )
• pour enfiler un élément : on incrémente le pointeur queue ( on le décrémenterait dans la version "fin de tableau" ), et on stocke alors l'élément à enfiler dans le tableau à l'indice queue; bien entendu, cela n'est possible que si queue n'a pas atteint l'indice du dernier élément du tableau ( N - 1 ) ! ( indice 0 pour la version "fin" )
• pour défiler un élément : on renvoie l’élément du tableau à l'indice tete, et on incrémente également le pointeur tete
  Bien entendu, cela n'est possible que si la file n'est pas vide. Il y a deux situations pour lesquelles cela se produit :
  1. quand il n'y a encore aucun élément dans la file; à ce moment : tete == -1
  2. quand on a défilé toute la file; à ce moment : tete > queue.

Le gros inconvénient de cette implémentation, est qu'à chaque fois que l'on défile un élément, on perd aussi une capacité de une place dans la file ! Une fois que la file a été remplie, il n'est alors plus possible d'y rajouter de nouveaux éléments, même si on en défile ! Le seul moyen est alors de complètement réinitialiser la file.

Vous verrez en exercice une version optimisée qui n'a pas ces défauts, la file circulaire.

Code

class FileStat:

    def __init__(self, n):
        """ Instancie une file vide de n élements ( initialisés à None ) """
        self.file = [None for i in range(n)]
        self.tete = self.queue = -1

    def enfiler(self, element):
        """ Enfile ( si la file n'est pas pleine ! ) un élément en queue de file """
        assert not self.est_pleine(), "File pleine !"

        if self.tete == -1: # gestion de l'enfilage du premier élément
            self.tete = 0   # on place la tête au début du tableau
        self.queue += 1
        self.file[self.queue] = element

    def defiler(self):
        """ Défile ( si la file n'est pas vide ! ) un élément en tête de file, et le renvoie """
        assert not self.est_vide(), "File vide !"
        
        elt =  self.file[self.tete] # on récupère l'élément en tête de file
        self.tete += 1              # on incrémente le pointeur de tête
        return elt                  # on renvoie l'élément en tête

    def est_vide(self):
        """ Renvoie True si la file est vide, False sinon """
        return self.tete == -1 or self.tete > self.queue # conditions vérifiées quand la file est vide

    def est_pleine(self):
        return self.queue == len(self.file)-1 # n-1 = indice du dernier élément d'un tableau de n éléments
			

On remarque ( lignes 13 et 14 ) qu'il faut prendre la précaution, au moment de l'enfilage du premier élément, de bien positionner le pointeur tete sur l'indice de ce premier élément ( 0 ); au cas où on tentait de défiler ce premier élément, on accéderait sinon à l'élément d'indice -1, qui correspond en Python au dernier élément du tableau !

Complexité des opérations

Défiler et enfiler un élément revient dans tout les cas à adresser un élément d'un tableau, en modifiant la valeur des "pointeurs" utilisés pour cet adressage, toutes opérations en O(1).

Dans tous les cas, ces opérations se font donc en temps constant.

Version tableau dynamique ( type list Python )

Avec tête en fin de tableau / queue en début de tableau → ⓺⓹⓸⓷⓶⓵ →

class FileDyna:

    def __init__(self):
        self.file = []

    def est_vide(self):             # pas de méthode est_pleine, la file ne peut jamais l'être !
        return len(self.file) == 0  # ou self.file == []

    def enfiler(self, elt):
        self.file.insert(0, elt) 	# insertion au début du tableau = queue de la file

    def defiler(self):
        assert not self.est_vide(), "File vide !"

        return self.file.pop() 	   # dernier élément du tableau = tête de la file
			

Avec tête en début de tableau / queue en fin de tableau ← ⓵⓶⓷⓸⓹⓺ ←

class FileDyna:

    def __init__(self):
        self.file = []

    def est_vide(self):
        return len(self.file) == 0

    def enfiler(self, elt):
        self.file.append(elt) 		# insertion en fin de tableau = queue de la file

    def defiler(self):
        assert not self.est_vide(), "File vide !"
        
        return self.file.pop(0)     # premier élément du tableau = tête de la file
        
			

La méthode pop(i) permet de retirer et de renvoyer l'élément d'indice i dans un tableau, pas uniquement le dernier.

Complexité

Il faut savoir que, contrairement à l'ajout ou au retrait d'un élément en fin de tableau, les opérations d'insertion ou de suppression en début d'un tableau entraînent toujours la nécessité de redimensionner, et donc de réécrire le tableau ailleurs en mémoire : ces opérations sont donc en O(n).

Aucune des deux versions n'est donc plus efficace que l'autre :

• avec la première version, les opérations en tête sont peu coûteuses en temps ( pop() en O(1) ), les opérations en queue sont plus coûteuses (insert(0) en O(n) ).
• avec la deuxième version, c'est l'inverse ( pop(0) en O(n), append() en O(1) )

Conclusion : l'implémentation d'une file avec une list Python n'est donc pas la meilleure !...

Implémentation avec liste chaînée à double pointeur

class Maillon:
    def __init__(self, valeur = None, suivant = None):
        self.valeur = valeur
        self.suivant = suivant
        
class FileOptim:
    def __init__(self):
        self.tete = None
        self.queue = None
        
    def __str__(self):
        res = "<- "
        m = self.tete
        while m is not None:
            res += str(m.valeur) + " "
            m = m.suivant
        return res + "<-" 
        
    def est_vide(self):
        return self.tete is None 	# si la file n'a pas de tête, elle n'a pas de queue non plus !!...
        
    def enfiler(self, element):
        nv_maillon = Maillon(element)           # dans tous les cas, il faut créer un nouveau maillon...
        if self.est_vide():						# Si la file est vide,
            self.tete = self.queue = nv_maillon # la tête et la queue de la file correspondent au même nouveau maillon.
        else:									# Sinon,
            self.queue.suivant = nv_maillon		# on fait pointer la queue vers le nouveau maillon,
            self.queue = self.queue.suivant		# et la queue devient le nouveau maillon.
        
    def defiler(self):
        assert not self.est_vide(), "File vide !"
        v = self.tete.valeur				# dans tous les cas, il faut commencer par sauvegarder la valeur de l'élément en tête...
        if self.tete == self.queue:         # Si la tête et la queue sont le même maillon, la file ne contient qu'un seul élément;
            self.tete = self.queue = None   # dans ce cas, on réinitialise la file vide,
            return v                        # et on renvoie l'élément (anciennement) en tête.
        self.tete = self.tete.suivant       # Sinon, on fait juste pointer la tête vers son maillon suivant.
        return v		
			
			

Applications

Version 2 piles

Vérification sur un exemple

Implémentation

			
from pile import *

class File2Piles:

    def __init__(self):
        self.pile_queue = Pile()
        self.pile_tete = Pile()

    def est_vide(self):
        return self.pile_queue.est_vide() and self.pile_tete.est_vide() # la file est vide si les DEUX piles sont toutes les deux vides.

    def enfiler(self, elt):              # on suppose qu'on utilise des piles sans limitation de taille....
        self.pile_queue.empiler(elt) 

    def defiler(self):
        assert not self.est_vide(), "File vide !"
        
        if self.pile_tete.est_vide():                             # si il n'y a pas d'élément dans le pile de tête,  
            while not self.pile_queue.est_vide():                 # il y en a forcément dans la pile de queue ( la file n'est pas vide ! );
                self.pile_tete.empiler(self.pile_queue.depiler()) # on les dépile tous dans la pile de tête.

        return self.pile_tete.depiler()                           # Pour défiler, on dépile la pile de tête.
			

File circulaire

class FileCirculaire:

    def __init__(self):
        """ Instancie une file vide de 20 élements ( initialisés à None ) """
        self.file = [None for i in range(20)]
        self.tete = self.queue = -1

    def enfiler(self, element):
        """ Enfile ( si la file n'est pas pleine ! ) un élément en queue de file """
        assert not self.est_pleine, "File pleine !"
        
        if self.tete == -1: 	# enfilage du premier élément dans une file vide
            self.tete = 0 	# on positionne le pointeur de tete sur le premier élément du tableau

        if self.queue == 19: # le pointeur de queue est arrivé en fin de tableau ?
            self.queue = 0 	# si oui, on le replace sur le premier élément
        else:
            self.queue += 1 	# sinon, on l'incrémente de 1

        self.file[self.queue] = element # dans tout les cas, on finit par stocker l'élément au "bon" indice du tableau
        

    def defiler(self):
        """ Défile ( si la file n'est pas vide ! ) un élément en tête de file, et le renvoie """
        assert not self.est_vide(), "File vide !"

        elt =  self.file[self.tete] # on récupère l'élément en tête de file

        if (self.tete == self.queue): # la file ne contient plus qu'un seul élément ?
            self.tete = self.queue = -1 # on réinitialise les deux pointeurs à "file vide"

        elif self.tete == 19: # sinon si le pointeur de tête est arrivé en fin de tableau ?
            self.tete = 0 # si oui, on le replace sur le premier élément
      
        else:
            self.tete += 1 # sinon, on l'incrémente de 1

        return elt # dans tous les cas, on renvoie l'élément en tête

    def est_pleine(self):
        """ Renvoie True si la file est pleine, False sinon """
        return self.tete == 0 and self.queue == 19) or self.tete > self.queue

    def est_vide(self):
        """ Renvoie True si la file est vide, False sinon """
        return self.tete == -1 # condition vérifiée quand la file est vide	
			

...

def enfiler(self, element):

      if self.tete == -1: 	
          self.tete = 0 	
		
		self.queue = (self.queue + 1) % 20 # la valeur de 'self.queue' restera toujours comprise entre 0 et 19          
         
      self.file[self.queue] = element # dans tout les cas, on finit par stocker l'élément au "bon" indice du tableau
        

...				 
				 

Simulation d'une file d'attente

from file import File
from random import randint

caisse = [0, 0, 0, 0, 0]
numero_client = 1
nbClients = 0 # nombre de clients passés aux caisses
file = File()
t = 0

for i in range(len(caisse)): # premiers clients
    caisse[i] = randint(3,10)

while nbClients != 10 : # tant que 10 clients ne sont pas passés
    
    file.enfiler(numero_client) # nouveau client dans la file
    numero_client += 1
    
    for i in range(len(caisse)): # un client peut-il passer en caisse ? On parcourt la liste des caisses.
        if caisse[i] == 0: # si le temps de passage à cette caisse est écoulé...
            file.defiler() # un client sort de la file.
            nbClients += 1 # un client de plus est passé
            caisse[i] = randint(3,10) # client suivant !
        else : 
            caisse[i] -= 1 # sinon le temps de passage à la caisse diminue
    t += 1
    
print(t)