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 __str__(self):
        return str(self.file)

    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):
        assert not self.est_vide(), "File vide !"
        """ Défile ( si la file n'est pas vide ! ) un élément en tête de file, et le renvoie """

        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 # = indice du dernier élément d'un tableau de n éléments


class FileDyna:

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

    def __str__(self):
        return "-> " + str(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


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
        self.tete = self.tete.suivant       # Sinon, on fait juste pointer la tête vers son maillon suivant.
        return v

## TESTS
if __name__ == "__main__":
    f1 = FileStat(20)
    f2 = FileDyna()
    f3 = FileOptim()

    print("Enfilage de 20 éléments et affichage des files :")
    for i in range(20):
        f1.enfiler(i)
        f2.enfiler(i)
        f3.enfiler(i)
    print("f1 =", f1)
    print("f2 =", f2)
    print("f3 =", f3)
    print()

    # f1.enfiler(20) # File pleine !
    f2.enfiler(20) # pas de problème...
    f3.enfiler(20) # là non plus...

    print("Défilage complet des files, et tests si elles sont bien vides :")
    while not f1.est_vide():
        print(f1.defiler(), end =' ')
    print(f1.est_vide())
    while not f2.est_vide():
        print(f2.defiler(), end = ' ')
    print(f2.est_vide())
    while not f3.est_vide():
        print(f3.defiler(), end = ' ')
    print(f3.est_vide())

    # print(f1.defiler()) # File vide !
    # print(f2.defiler()) # File vide !
    # print(f3.defiler()) # File vide !