• Assurez la sécurité des applications de la bonne manière! Détectez, protégez, surveillez, accélérez et plus encore…
  • Les structures de données jouent un rôle clé dans le monde de la programmation. Ils nous aident à organiser nos données d'une manière qui peut être utilisée efficacement. le Queue est l'une des structures de données les plus simples disponibles.

    Dans cet article, nous découvrirons les Queue et son implémentation en Python.

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

    Queue est une structure de données linéaire qui suit la Premier entré / premier sorti (FIFO) principe. C'est l'opposé du Structure de données de la pile.

    Nous pouvons comparer les file avec une vraie vie file d'attente au guichet du cinéma. Voyons l'illustration d'une file d'attente comme suit.

    Si vous observez la file d'attente au comptoir, la deuxième personne ne peut se rendre au comptoir qu'après que la première personne a terminé son travail. Ici, la première personne vient au comptoir, puis la deuxième personne. Alors, ici, les gens suivent le FIFO (premier entré / premier sorti) principe. Celui qui vient en premier, il / elle terminera le travail en premier. Nous pouvons voir le même genre de files d'attente dans notre vie de tous les jours.

    La Queue la structure des données suit également le même principe. Maintenant, vous savez ce que sont les files d'attente et son principe. Voyons les opérations qui peuvent être effectuées sur un file Structure de données.

    Opérations dans la file d'attente

    Similaire à stack, nous trouverons deux opérations principales dans un file Structure de données.

    mettre en file d'attente (données)

    Ajoute de nouvelles données à la file d'attente à la fin. Le côté s'appelle le arrière.

    retirer la file d'attente ()

    Supprime les données du début de la file d'attente. Le côté s'appelle le avant.

    Voyons les illustrations des opérations de file d'attente pour une meilleure compréhension. Une image vaut mille mots.

    Nous pouvons écrire des fonctions d'assistance pour obtenir plus d'informations sur la file d'attente. Il n'y a pas de limite au nombre de fonctions d'assistance que vous aurez. Tenons-nous en au plus important une fois mentionné ci-dessous pour le moment.

    arrière()

    Renvoie le premier élément de la fin de la file d'attente.

    de face()

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

    est vide()

    Renvoie si la file d'attente est vide ou non.

    N'est-ce pas ennuyeux pour vous? Je veux dire les sujets conceptuels.

    Pour moi Oui!

    Mais nous ne pouvons rien faire sans connaître les concepts. Nous devons terminer le savoir avant la mise en œuvre. Ne vous inquiétez pas, il est temps de nous salir les mains avec du code.

    Je suppose que tu as python installé sur votre PC sinon vous pouvez également essayer le compilateur en ligne.

    Implémentation de file d'attente

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

    Il existe plusieurs façons d'implémenter la file 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 le type de données list pour implémenter un file dans une classe. Nous vous guiderons à travers différentes étapes pour implémenter la structure de données de file d'attente à partir de zéro sans aucun module. Sautons dedans.

    Step1: 

    Écrivez une classe appelée Queue.

    class Queue:
    	pass

    Step2:

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

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

    Step3:

    Pour insérer des données dans la file d'attente, nous avons besoin d'une méthode dans la classe. La méthode s'appelle Enqueue comme nous l'avons déjà discuté 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 le ajouter méthode du type de données liste pour ajouter des données à la fin de la file d'attente.

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

    Step4: 

    La file d'attente doit avoir une sortie. Et ça s'appelle retirer la file d'attente. Je pense que vous avez déjà deviné que nous allons utiliser la méthode pop du type de données liste. Si vous avez deviné ou non, à votre santé!

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

    Ici, nous devons supprimer le premier élément de la liste. Donc, il faut passer l'index à la méthode pop.

    class Queue:
    
    	# ...
    
    	def dequeue(self):
    		return self.elements.pop(0)
    

    Cela suffit pour une file d'attente. Mais nous avons besoin des fonctions d'assistance pour tester si les opérations de file d'attente fonctionnent correctement ou non. Écrivons également les fonctions d'assistance.

    Step5: 

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

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

    Step6: 

    Procédé de face() est utilisé pour obtenir le premier élément de la file 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[0]
    

    Step7: 

    Procédé est vide() est utilisé pour vérifier si la file 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
    

    Phew! a terminé la partie mise en œuvre du file Structure de données. Nous devons créer un objet pour le Queue classe à utiliser.

    Faisons le.

    class Queue:
    
    	# ...
    
    if __name__ == '__main__':
    	queue = Queue()

    Maintenant, nous avons un Queue objet. Testons-le avec quelques séries d'opérations.

    • Vérifiez si la file d'attente est vide ou non en utilisant le est vide méthode. Il devrait revenir Vrai.
    • Additionnez les nombres 1, 2, 3, 4, 5 au file utilisant l' Enqueue méthode.
    • La est vide la méthode doit retourner Faux. Vérifie ça.
    • Imprimer le avant et arrière éléments utilisant le avant et arrière méthodes respectivement.
    • Supprimez l'élément de la file d'attente à l'aide du retirer la file d'attente méthode.
    • Vérifiez la avant élément. Il devrait renvoyer l'élément 2.
    • Maintenant, supprimez tous les éléments de la file d'attente.
    • La est vide la méthode doit retourner Vrai. Vérifie ça.

    Je pense que cela suffit pour tester notre implémentation de file d'attente. Écrivez le code de chaque étape mentionnée ci-dessus pour tester la file d'attente.

    Avez-vous écrit le code?

    Non, ne t'inquiète 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[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())

    Je pense que vous exécutez 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 liste type de données en tant que file Structure de données. 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 classe ci-dessus d'un file dans un programme différent d'un projet en créant simplement l'objet comme nous le faisions précédemment.

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

    # 2. deque des collections

    Il est implémenté sous la forme d'une file d'attente à deux extrémités. Puisqu'il prend en charge l'ajout et la suppression d'éléments des deux extrémités, nous pouvons l'utiliser comme un empiler et file. Voyons l'implémentation de la file d'attente en utilisant retirer la file d'attente.

    Il est implémenté à l'aide d'autres structures de données appelées doublement lié liste. Ainsi, les performances d'insertion et de suppression d'éléments sont cohérentes. L'accès aux éléments de la liste chaînée du milieu a pris O (n) temps. Nous pouvons l'utiliser comme un file car il n'est pas nécessaire d'accéder aux éléments du milieu depuis le file.

    Vérifions les différentes méthodes que le retirer la file d'attente nous offre.

    • ajouter (données) - utilisé pour ajouter les données à la file d'attente
    • popleft () - utilisé pour supprimer le premier élément de la file d'attente

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

    Nous avons suivi une série d'étapes pour tester le file mise en œuvre dans le précédent. Suivons ici également la même série d'étapes.

    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)

    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 a un module intégré appelé file qui dessert une classe appelée Queue pour l'implémentation de la file d'attente. C'est similaire à celui que nous avons implémenté auparavant.

    Commençons par vérifier les différentes méthodes de Queue classe.

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

    Implémentons la 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())
    

    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 le Queue classe. Vous pouvez les explorer en utilisant le dir fonction intégrée.

    Conclusion

    J'espère que vous avez appris la structure des données de file d'attente et sa mise en œuvre. C'est tout pour la file d'attente. Vous pouvez utiliser la file d'attente à différents endroits où il doit être traité dans FIFO (premier entré / premier sorti) ordre. Utilisez la file d'attente dans la résolution de problèmes chaque fois que vous obtenez le cas pour l'utiliser.

    Intéressé par la maîtrise de Python? Découvrez ces ressources d'apprentissage.

    Codage heureux 🙂 👨‍💻