Comprendre l'implémentation des files d'attente en Python

Les structures de données jouent un rôle clé dans le monde de la programmation. Elles nous aident à organiser nos données de manière à ce qu'elles puissent être utilisées efficacement. La fichier d'attente est l'une des structures de données les plus simples qui soient

Dans cet article, nous allons découvrir la fichier d'attente et son implémentation en Python

Qu'est-ce qu'un fichier d'attente ?

Une fichier d'attente est une structure de données linéaire qui suit le principe FIFO (premier entré/premier sorti) ). Elle est opposée à la structure de données Stack

Nous pouvons comparer la fichier d'attente à une fichier d'attente réelle au guichet d'un cinéma. Voici l'illustration d'une file d'attente

Si vous observez la fiche d'attente au guichet, la deuxième personne ne peut se rendre au guichet que lorsque la première personne a terminé son travail. Ici, la première personne se présente au guichet, puis la seconde. Les personnes suivent donc le principe FIFO (premier entré/premier sorti) . La personne qui arrive en premier termine son travail en premier. Nous pouvons voir des fichiers d'attente similaires dans notre vie quotidienne

La structure de données des fichiers d'attente suit le même principe. Vous savez maintenant ce que sont les fichiers d'attente et leur principe. Voyons maintenant les opérations qui peuvent être effectuées sur une structure de données de fichier d'attente

Opérations dans un fichier d'attente

Comme pour la pile, nous trouvons deux opérations principales dans une structure de données de fichier d'attente

enqueue(données)

Ajoute de nouvelles données à la file d'attente à la fin. Le côté est appelé l'arrière

dequeue()

Supprimez les données de l'avant de la file d'attente. Le côté est appelé l'avant

Voyons les illustrations des opérations de file d'attente pour une meilleure compréhension. Une image est plus parlante qu'un millier de mots

Nous pouvons écrire quelques fonctions d'aide pour obtenir plus d'informations sur la file d'attente. Il n'y a pas de limite au nombre de fonctions d'aide que vous pouvez avoir. Pour l'instant, nous nous en tiendrons aux fonctions les plus importantes mentionnées ci-dessous

arrière()

Renvoie le premier élément à l'extrémité de la file d'attente

front()

Renvoie le premier élément du début de la file d'attente

is_empty()

Retourne si la file d'attente est vide ou non

N'est-ce pas ennuyeux pour vous ? Je parle des sujets conceptuels

Pour moi, oui !

Mais nous ne pouvons rien faire sans connaître les concepts. Nous devons les connaître complètement avant de les mettre en œuvre. Ne vous inquiétez pas, il est temps de se salir les mains avec du code

Je suppose que vous avez installé Python sur votre PC ; si ce n'est pas le cas, vous pouvez également essayer le compilateur en ligne

Mise en œuvre de la file d'attente

L'implémentation d'une file d'attente ne prendra pas plus de 15 minutes à un programmeur. Une fois que vous aurez appris, vous le direz. Peut-être pourrez-vous l'implémenter en quelques minutes après ce tutoriel

Il y a plusieurs façons d'implémenter un fichier d'attente en Python. Voyons les différentes implémentations de file d'attente étape par étape

#1. Liste

La liste est un type de données intégré à Python. Nous allons utiliser ce type de données pour implémenter une fichier d'attente dans une classe. Nous allons vous guider à travers différentes étapes pour mettre en œuvre la structure de données de la file d'attente à partir de zéro sans aucun module. Nous allons donc nous y mettre

Étape 1

Écrivez une classe appelée File d'attente

classe Queue :
pass

Étape 2

Il doit y avoir une variable pour stocker les données de la file d'attente dans la classe. Appelons-la éléments. Et c'est une liste bien sûr

class Queue :

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

Étape 3

Pour insérer des données dans la file d'attente, nous avons besoin d'une méthode dans la classe. Cette méthode s'appelle enqueue , comme nous l'avons déjà vu dans la section précédente du tutoriel

La méthode prend des données et les ajoute à la file d'attente (éléments). Nous pouvons utiliser la méthode ajouter du type de données list pour ajouter des données à la fin de la file d'attente

class Queue :

# ...

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

Étape 4

La file d'attente doit avoir une sortie. Et cela s'appelle dequeue. Je pense que vous avez déjà deviné que nous allons utiliser la méthode pop du type de données list. Si vous avez deviné ou non, bravo!

La méthode pop du type de données list supprime un élément de la liste à l'index donné. Si nous n'avons pas donné d'index, elle supprime le dernier élément de la liste

Ici, nous devons supprimer le premier élément de la liste. Nous devons donc passer l'index 0 à la méthode pop

class Queue :

# ...

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

C'est suffisant pour un fichier d'attente. Mais nous avons besoin de fonctions d'aide pour tester si les opérations de la file d'attente fonctionnent correctement ou non. Ecrivons également les fonctions d'aide

Étape 5

La méthode arrière() est utilisée pour obtenir le dernier élément de la file d'attente. L'indexation négative dans le type de données liste nous aide à obtenir le dernier élément de la file d'attente

class Queue :

# ...

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

Étape 6

La méthode front() est utilisée pour obtenir le premier élément de la fiche d'attente. Nous pouvons obtenir le premier élément de la file d'attente en utilisant l'index de la liste

class Queue :

# ...

def front(self) :
return self.elements<x>[0]</x>

Étape 7

La méthode is_empty() est utilisée pour vérifier si le fichier d'attente est vide ou non. Nous pouvons vérifier la longueur de la liste

class Queue :

# ...

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

Nous avons terminé la partie implémentation de la structure de données de la fichier d'attente . Nous devons créer un objet pour que la classe File d'attente puisse l'utiliser

C'est ce que nous allons faire

class Queue :

# ...

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

Nous avons maintenant un objet File d'attente . Testons-le avec une série d'opérations

• Vérifiez si le fichier d'attente est vide ou non en utilisant la méthode est_vide . Elle doit renvoyer True.
• Ajoutez les nombres 1, 2, 3, 4, 5 à la fichier d'attente à l'aide de la méthode enqueue .
• La méthode est_vide doit renvoyer Faux. Vérifiez-le.
• Imprimez les éléments avant et arrière à l'aide des méthodes avant et arrière de l'entreprise.
• Retirez l'élément de la file d'attente à l'aide de la méthode dequeue .
• Vérifiez l'élément avant . Il doit renvoyer l'élément 2.
• Retirez maintenant tous les éléments de la file d'attente.
• La méthode est_vide doit renvoyer True. Vérifiez-le.

Je pense que c'est suffisant pour tester l'implémentation de notre fichier d'attente. Écrivez le code pour chaque étape mentionnée ci-dessus afin de tester la file d'attente

Avez-vous écrit le code ?

Non, ne vous inquiétez pas

Vérifiez le code ci-dessous

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<x>[0]</x>

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

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

## vérification de la méthode is_empty -> True
print(queue.is_empty())

## ajout des éléments
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)

## vérifiant à nouveau la méthode is_empty -> False
print(queue.is_empty())

## impression des éléments avant et arrière en utilisant respectivement les méthodes front et rear -> 1, 5
print(queue.front(), end=' ')
print(queue.rear())

## suppression de l'élément -> 1
queue.dequeue()

## vérification des éléments avant et arrière en utilisant respectivement les méthodes front et rear -> 2 5
print(queue.front(), end=' ')
print(queue.rear())

## suppression de tous les éléments
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()

## vérification de la méthode is_empty pour la dernière fois -> True
print(queue.is_empty())

Je pense que vous avez exécuté le programme ci-dessus. Vous pouvez obtenir une sortie similaire au résultat suivant

True
False

1

5

2

5
True

Nous pouvons directement utiliser le type de données liste comme structure de données de fichier d'attente . L'implémentation ci-dessus de la file d'attente vous aide à mieux comprendre l'implémentation de la file d'attente dans d'autres langages de programmation

Vous pouvez également utiliser l'implémentation de la classe de fichier d'attente ci-dessus dans un autre programme d'un projet en créant simplement l'objet comme nous l'avons fait précédemment

Nous avons implémenté la fichier d'attente à partir de zéro en utilisant le type de données liste. Existe-t-il des modules intégrés pour la file d'attente ? Oui, nous avons des implémentations de file d'attente intégrées. Voyons-les

#2. deque from collections

Elle est implémentée comme une file d'attente à double extrémité. Puisqu'elle supporte l'ajout et le retrait d'éléments aux deux extrémités, nous pouvons l'utiliser comme une pile et une fichier d'attente. Voyons l'implémentation de la file d'attente à l'aide de dequeue

Elle est mise en œuvre à l'aide d'autres structures de données appelées listes doublement liées. Ainsi, les performances d'insertion et de suppression d'éléments sont cohérentes. L'accès aux éléments de la liste doublement liée prend O(n) temps. Nous pouvons l'utiliser comme une fichier d'attente car il n'est pas nécessaire d'accéder aux éléments du milieu à partir de la fichier d'attente

Examinons les différentes méthodes offertes par la fichier d'attente

• append(data) - utilisée pour ajouter des données à la file d'attente
• popleft() - permet de retirer le premier élément de la file d'attente

Il n'y a pas d'autres méthodes pour avant, arrière et est_vide. Nous pouvons imprimer toute la file d'attente à la place des méthodes avant et arrière . Ensuite, nous pouvons utiliser la méthode len pour vérifier si la fichier d'attente est vide ou non

Nous avons suivi une série d'étapes pour tester l'implémentation de la fichier d'attente dans la section précédente. Suivons la même série d'étapes ici aussi

from collections import deque

## création de l'objet deque
queue = deque()

## vérification si la queue est vide ou non -> True
print(len(queue) == 0)

## pousser les éléments
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

## vérifie à nouveau si la file est vide ou non -> False
print(len(queue) == 0)

## imprime la file
print(queue)

## supprime l'élément -> 1
queue.popleft()

## impression de la file d'attente
print(queue)

##

suppression de tous les éléments
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()

##

vérification du fait que la file d'attente est vide ou non pour la dernière fois -> True
print(len(queue) == 0)

Vous obtiendrez un résultat similaire à la sortie suivante

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

#3. File d'attente de la file d'attente

Python possède un module intégré appelé file d'attente qui utilise une classe appelée File d'attente pour l'implémentation de la file d'attente. Elle est similaire à celle que nous avons implémentée précédemment

Tout d'abord, vérifions les différentes méthodes de la classe File d'attente

• put(data) - ajoute ou pousse les données dans la file d'attente
• get() - retire le premier élément de la file d'attente et le renvoie
• vide( ) - Indique si la pile est vide ou non
• qsize( ) - renvoie la longueur de la file d'attente.

Implémentons le fichier d'attente avec les méthodes ci-dessus

from queue import Queue

## création de l'objet Queue
queue_object = Queue()

## vérification si la queue est vide ou non -> True
print(queue_object.empty())

## ajout des éléments
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)

## vérifie à nouveau si la file est vide ou non -> False
print(queue_object.empty())

## suppression de tous les éléments
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())

## vérification de la taille de la file d'attente
print("Size", queue_object.qsize())

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

##

vérification du fait que l'objet de la file d'attente est vide ou non pour la dernière fois -> True
print(queue_object.empty())

Vérifiez la sortie du code ci-dessus

True
False

1

2

3

Size 2

4

5

True

Il existe d'autres méthodes dans la classe File d'attente . Vous pouvez les explorer en utilisant la fonction intégrée dir

Conclusion

J'espère que vous avez appris à connaître la structure de données de la file d'attente et son implémentation. C'est tout pour la file d'attente. Vous pouvez utiliser le fichier d'attente à différents endroits où les données doivent être traitées dans l'ordre FIFO (premier entré/premier sorti) . Utilisez la fiche d'attente dans la résolution de problèmes chaque fois que vous en avez l'occasion

Vous souhaitez maîtriser Python ? Consultez ces ressources d'apprentissage

Bon codage 🙂 👨‍💻