Une file est une structure de données abstraite.

On reprend l'idée de la file d'attente et on précise les opérations permises:

• On peut enfiler un élément (une personne arrive en queue de file)
• On peut défiler un élément (la personne en début de file sort de la file).
• On peut savoir si la file est vide ou non.

Avec le type liste:

class File:
	
	def __init__(self):
		self.valeurs = []
		
	def enfiler(self, valeur):
		self.valeurs.append(valeur)
		
	def defiler(self):
		if self.valeurs:
			return self.valeurs.pop(0)
			
	def estVide(self):
		return self.valeurs == []
		
	@property
	def longueur(self):
		return len(self.valeurs)
		
		
	def __str__(self):
		ch = "\nEtat de la file:\n"  
		for x in self.valeurs:
			ch +=  str(x) + " "    
		return ch
			
			
			
q = File()
q.enfiler(9)
q.enfiler(2)
q.enfiler(5)

print(q)

q.defiler()
q.enfiler(7)

print("La file est-elle vide: ", q.estVide())

print(q)
print("Longueur de la file:", q.longueur)

L'affichage obtenu est ici:

Etat de la file:
9 2 5 
La file est-elle vide:  False

Etat de la file:
2 5 7 
Longueur de la file: 3

La structure de liste doublement chaînée est bien adaptée pour une implémentation de file.

Vous pouvez chercher sur le web la notion de liste doublement chaînée si vous ne connaissez pas. L'idée est d'utiliser une suite de maillons, chaque maillon contenant d'une part une donnée et d'autre part un lien sur le maillon suivant de la chaîne et un lien sur le maillon précédent.

Une représentation classique est la suivante:

Chaque boîte contient une donnée, la flèche à droite de la boîte est le lien sur la donnée suivante, la flèche à gauche le lien sur la donnée précédente. Le dernier maillon a un suivant "vide", le premier maillon a un prédécesseur vide (on utilisera None en python). La flèche violette à gauche peut être associée dans le code python ci-dessous à la variable q (la variable q de type File "pointe" sur le premier maillon et permet de le récupérer avec la syntaxe q.debut).

Un code possible:

class Maillon:
	
	def __init__(self, valeur, precedent=None, suivant=None):
		self.valeur = valeur
		self.precedent = precedent
		self.suivant = suivant
		
		


class File:
	
	def __init__(self):
		self.longueur = 0
		self.debut = None
		self.fin = None
		
	def enfiler(self, valeur):
		if self.longueur == 0:
			self.debut = self.fin = Maillon(valeur)
		else:
			self.fin = Maillon(valeur, self.fin)
			self.fin.precedent.suivant = self.fin
		self.longueur += 1
			
		
	def defiler(self):
		if self.longueur > 0:
			valeur = self.debut.valeur
			if self.longueur > 1:
				self.debut = self.debut.suivant
				self.debut.precedent = None
			else:
				self.debut = self.fin = None
			self.longueur -= 1
		return valeur
			
	 
	def estVide(self):
		return self.longueur == 0
		
	 
		
		
	def __str__(self):
		ch = "\nEtat de la file:\n"  
		maillon = self.debut
		while maillon != None:
			ch +=  str(maillon.valeur) + " "    
			maillon = maillon.suivant
		return ch
			
			
			
q = File()
q.enfiler(9)
q.enfiler(2)
q.enfiler(5)

print(q)

q.defiler()
q.enfiler(7)

print("La file est-elle vide: ", q.estVide())

print(q)
print("Longueur de la file:", q.longueur)

L'affichage obtenu:

Etat de la file:
9 2 5 
La file est-elle vide:  False

Etat de la file:
2 5 7 
Longueur de la file: 3

On place en cercle les joueurs. On décide d'un joueur point de départ. Puis on compte 7 joueurs en partant du premier et on élimine le 7ème. On compte ensuite 7 joueurs en partant du suivant et on élimine...etc. Le problème est de prévoir le gagnant.

Illustration avec 5 joueurs et un compte de 3 en 3:

1. On compte 3 à partir du joueur A. Et on élimine le numéro 3:
   
2. On compte 3 à partir du joueur D. Et on élimine le numéro 3:
   
3. On compte 3. Et on élimine le numéro 3:
   
4. On compte 3. Et on élimine le numéro 3:
   

Le joueur D est le gagnant.

Proposer une fonction prenant en paramètres la liste des joueurs et le module (dans l'exemple, le module est 3) et qui renvoie le gagnant. On utilisera une file.

class Maillon:

	def __init__(self, valeur, precedent=None, suivant=None):
		self.valeur = valeur
		self.precedent = precedent
		self.suivant = suivant




class File:

	def __init__(self):
		self.longueur = 0
		self.debut = None
		self.fin = None

	def enfiler(self, valeur):
		if self.longueur == 0:
			self.debut = self.fin = Maillon(valeur)
		else:
			self.fin = Maillon(valeur, self.fin)
			self.fin.precedent.suivant = self.fin
		self.longueur += 1


	def defiler(self):
		if self.longueur > 0:
			valeur = self.debut.valeur
			if self.longueur > 1:
				self.debut = self.debut.suivant
				self.debut.precedent = None
			else:
				self.debut = self.fin = None
			self.longueur -= 1
		return valeur


	def estVide(self):
		return self.longueur == 0




	def __str__(self):
		ch = "\nEtat de la file:\n"
		maillon = self.debut
		while maillon != None:
			ch +=  str(maillon.valeur) + " "
			maillon = maillon.suivant
		return ch



 
def josephe(listePersonnes, module):
	f = File()
	for personne in listePersonnes:
		f.enfiler(personne)
	
	while not(f.estVide()):
		for _ in range(module-1):
			f.enfiler(f.defiler())
		p = f.defiler()
		
	return p
	
	
print(josephe( ['Antoine', 'Béatrice', 'Camille', 'Damien', 'Emile'], 3))

Damien