Comprendre l’implémentation de la file d’attente en Python

Les structures de données sont essentielles en programmation. Elles permettent d’organiser les informations pour une utilisation efficace. La file d’attente est l’une des structures les plus élémentaires et courantes.

Cet article explore la notion de file d’attente et sa mise en œuvre en Python.

Qu’est-ce qu’une file d’attente ?

Une file d’attente est une structure de données linéaire qui suit la règle du « premier arrivé, premier servi » (FIFO). C’est l’inverse d’une pile.

On peut comparer une file d’attente à une file d’attente réelle devant un guichet. Voici une illustration pour mieux comprendre:

Si l’on observe une file d’attente, la deuxième personne ne peut accéder au guichet que lorsque la première personne a terminé son opération. Les personnes suivent l’ordre d’arrivée. Ainsi, la personne arrivée la première est la première à être servie, ce qui correspond au principe FIFO. On retrouve ce même type de files d’attente dans la vie quotidienne.

La structure de données file d’attente suit ce même principe. Vous comprenez désormais le fonctionnement des files d’attente. Examinons maintenant les opérations possibles sur cette structure.

Opérations sur une file d’attente

Comme pour les piles, deux opérations fondamentales s’appliquent aux files d’attente.

Enfiler (données)

Cette opération ajoute de nouvelles données à la fin de la file d’attente. Cette extrémité est appelée « arrière » de la file.

Défiler()

Cette opération supprime les données du début de la file d’attente. Cette extrémité est appelée « avant » de la file.

Illustrons ces opérations pour une meilleure compréhension. Une image vaut mille mots !

Il est possible de définir des fonctions auxiliaires pour obtenir plus d’informations sur la file d’attente. Le nombre de ces fonctions est illimité. Limitons-nous aux fonctions les plus utiles pour le moment.

Arrière()

Cette fonction renvoie l’élément situé à l’arrière (fin) de la file d’attente.

Avant()

Cette fonction renvoie l’élément situé à l’avant (début) de la file d’attente.

Est_vide()

Cette fonction indique si la file d’attente est vide ou non.

Les concepts théoriques peuvent paraître ennuyeux, n’est-ce pas ?

Pour moi, oui !

Cependant, il est impossible de se passer de ces notions. Il est essentiel de les comprendre avant de passer à la mise en pratique. Ne vous inquiétez pas, il est temps de mettre les mains dans le code !

Je suppose que Python est installé sur votre ordinateur. Sinon, vous pouvez aussi utiliser un compilateur en ligne.

Mise en œuvre d’une file d’attente

Un programmeur ne mettra pas plus de 15 minutes pour implémenter une file d’attente. Une fois le concept acquis, vous le constaterez par vous-même. Vous pourrez même le faire en quelques minutes après ce tutoriel.

Il existe plusieurs méthodes pour implémenter une file d’attente en Python. Examinons ces différentes méthodes pas à pas.

#1. Utilisation d’une liste

Les listes sont un type de données intégré à Python. Nous allons utiliser ce type de données pour créer une file d’attente au sein d’une classe. Nous allons mettre en œuvre la structure de données de file d’attente à partir de zéro, sans utiliser aucun module externe. C’est parti !

Étape 1 :

Définissez une classe nommée Queue.

class Queue:
	pass

Étape 2 :

Il faut une variable pour stocker les données de la file d’attente au sein de la classe. Appelons-la « éléments ». Il s’agit bien sûr d’une liste.

class Queue:

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

Étape 3 :

Pour insérer des données dans la file d’attente, il faut une méthode dans la classe. Cette méthode est appelée « enfiler », comme mentionné précédemment dans ce tutoriel.

La méthode prend des données en argument et les ajoute à la file d’attente (éléments). La méthode « append » du type « list » est utilisée pour ajouter les données à la fin de la file.

class Queue:

	# ...

	def enqueue(self, data):
		self.elements.append(data)
		return data

Étape 4 :

Une file d’attente doit également avoir une méthode de sortie. Cette méthode est appelée « défiler ». Je pense que vous avez deviné que nous allons utiliser la méthode « pop » du type « list ». Que vous ayez deviné ou non, bravo !

La méthode « pop » supprime un élément de la liste à l’index spécifié. Sans index spécifié, elle supprime le dernier élément de la liste.

Ici, nous devons supprimer le premier élément de la liste. Il faut donc passer l’index 0 à la méthode « pop ».

class Queue:

	# ...

	def dequeue(self):
		return self.elements.pop(0)

C’est suffisant pour une file d’attente de base. Mais il est nécessaire de disposer de fonctions auxiliaires pour vérifier le bon fonctionnement des opérations sur la file d’attente. Ajoutons ces fonctions auxiliaires.

Étape 5 :

La méthode « arrière() » sert à récupérer le dernier élément de la file d’attente. L’indexation négative du type « list » permet d’obtenir le dernier élément facilement.

class Queue:

	# ...

	def rear(self):
		return self.elements[-1]

Étape 6 :

La méthode « avant() » sert à obtenir le premier élément de la file d’attente. L’index de la liste permet d’accéder directement au premier élément.

class Queue:

	# ...

	def front(self):
		return self.elements[0]

Étape 7 :

La méthode « est_vide() » sert à vérifier si la file d’attente est vide ou non. La longueur de la liste permet de le savoir.

class Queue:

	# ...

	def is_empty(self):
		return len(self.elements) == 0

Ouf ! La mise en œuvre de la structure de données file d’attente est terminée. Pour utiliser cette classe, il faut créer un objet.

Faisons-le.

class Queue:

	# ...

if __name__ == '__main__':
	queue = Queue()

Nous avons maintenant un objet Queue. Testons-le en effectuant une série d’opérations.

• Vérifiez si la file d’attente est vide ou non avec la méthode « est_vide() ». Elle doit renvoyer True.
• Ajoutez les nombres 1, 2, 3, 4, 5 à la file d’attente avec la méthode « enfiler ».
• La méthode « est_vide() » doit renvoyer False. Vérifiez-le.
• Affichez les éléments avant et arrière avec les méthodes « avant() » et « arrière() ».
• Supprimez un élément de la file d’attente avec la méthode « défiler() ».
• Vérifiez l’élément avant. Il doit renvoyer l’élément 2.
• Supprimez tous les éléments de la file d’attente.
• La méthode « est_vide() » doit renvoyer True. Vérifiez-le.

Ces tests sont suffisants pour valider notre mise en œuvre de la file d’attente. Écrivez le code correspondant à chaque étape ci-dessus pour tester la file d’attente.

Avez-vous écrit le code ?

Pas de panique.

Voici le code que vous pouvez utiliser :

class Queue:

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

	def enqueue(self, data):
		self.elements.append(data)
		return data

	def dequeue(self):
		return self.elements.pop(0)

	def rear(self):
		return self.elements[-1]

	def front(self):
		return self.elements[0]

	def is_empty(self):
		return len(self.elements) == 0

if __name__ == '__main__':
	queue = Queue()

	## checking is_empty method -> True
	print(queue.is_empty())

	## adding the elements
	queue.enqueue(1)
	queue.enqueue(2)
	queue.enqueue(3)
	queue.enqueue(4)
	queue.enqueue(5)

	## again checking is_empty method -> False
	print(queue.is_empty())

	## printing the front and rear elements using front and rear methods respectively -> 1, 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing the element -> 1
	queue.dequeue()

	## checking the front and rear elements using front and rear methods respectively -> 2 5
	print(queue.front(), end=' ')
	print(queue.rear())

	## removing all the elements
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()
	queue.dequeue()

	## checking the is_empty method for the last time -> True
	print(queue.is_empty())

Vous pouvez exécuter le programme ci-dessus. Le résultat devrait ressembler à ce qui suit :

True
False
1 5
2 5
True

Nous pouvons directement utiliser le type « list » comme structure de données de file d’attente. L’implémentation précédente a pour objectif de vous aider à mieux comprendre la mise en œuvre d’une file d’attente dans d’autres langages de programmation.

Vous pouvez réutiliser l’implémentation de la classe « Queue » dans d’autres projets, en créant simplement un objet, comme nous l’avons fait précédemment.

Nous avons implémenté une file d’attente à partir de zéro en utilisant le type « list ». Existe-t-il des modules intégrés pour les files d’attente ? Bien sûr ! Il existe des implémentations de file d’attente intégrées. Examinons-les.

#2. Utilisation de « deque » de « collections »

L’objet « deque » est une file d’attente à double extrémité. Puisqu’il prend en charge l’ajout et la suppression d’éléments des deux côtés, on peut l’utiliser comme une pile ou une file d’attente. Voyons comment implémenter une file d’attente avec « deque ».

Il est implémenté avec une autre structure de données appelée liste doublement chaînée. Ainsi, les performances d’insertion et de suppression d’éléments sont constantes. Accéder aux éléments du milieu d’une liste chaînée prend un temps O(n). Cette implémentation est pertinente pour les files d’attente car il n’est pas nécessaire d’accéder aux éléments du milieu.

Voici les différentes méthodes proposées par l’objet « deque » :

• append(data) : ajout de données à la file d’attente.
• popleft() : suppression du premier élément de la file d’attente.

Il n’y a pas de méthodes alternatives pour « avant », « arrière » et « est_vide() ». On peut simplement afficher la file d’attente à la place de « avant » et « arrière ». La méthode « len » permet de vérifier si la file est vide ou non.

Nous avons suivi une série d’étapes pour tester l’implémentation de la file d’attente précédemment. Suivons ces mêmes étapes ici.

from collections import deque

## creating deque object
queue = deque()

## checking whether queue is empty or not -> True
print(len(queue) == 0)

## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## again checking whether queue is empty or not -> False
print(len(queue) == 0)

## printing the queue
print(queue)

## removing the element -> 1
queue.popleft()

## printing the queue
print(queue)

## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

Le résultat devrait ressembler à la sortie suivante :

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. Utilisation de la classe « Queue » du module « queue »

Python dispose d’un module intégré nommé « queue » qui propose une classe nommée « Queue » pour l’implémentation d’une file d’attente. Elle est similaire à celle que nous avons implémentée précédemment.

Examinons d’abord les différentes méthodes de la classe « Queue » :

• put(data) : ajoute les données à la file d’attente.
• get() : supprime le premier élément de la file et le renvoie.
• empty() : indique si la file est vide ou non.
• qsize() : retourne la taille de la file d’attente.

Implémentons une file d’attente avec les méthodes ci-dessus.

from queue import Queue

## creating Queue object
queue_object = Queue()

## checking whether queue is empty or not -> True
print(queue_object.empty())

## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## again checking whether queue is empty or not -> False
print(queue_object.empty())

## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## checking the queue size
print("Size", queue_object.qsize())

print(queue_object.get())
print(queue_object.get())

## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

Voici le résultat de l’exécution du code ci-dessus :

True
False
1
2
3
Size 2
4
5
True

La classe « Queue » propose d’autres méthodes. Vous pouvez les explorer en utilisant la fonction intégrée « dir ».

Conclusion

J’espère que vous avez compris la structure de données de file d’attente et son implémentation. C’est tout pour les files d’attente. Vous pouvez utiliser cette structure dans de nombreux cas où le traitement doit se faire selon l’ordre FIFO (premier entré, premier sorti). N’hésitez pas à utiliser les files d’attente dans la résolution de problèmes dès que le cas se présente.

Intéressé à approfondir vos connaissances en Python ? Consultez ces ressources d’apprentissage.

Bon codage ! 🙂 👨‍💻