Qu'est-ce que la structure des données de file d'attente en Python?

Comme vous l'avez déjà étudié sur l'importance des structures de données dans l'article précédent, plongeons directement dans le sujet de l'article, à savoir la structure des données de la file d'attente. Je vais aborder les sujets suivants:

• Besoin d'une structure de données de file d'attente
• Exemples de file d'attente de la vie quotidienne
• Création d'une structure de données de file d'attente
• En file d'attente
• De-queue
• Applications de la file d'attente

Besoin d'une structure de données de file d'attente

Supposons que vous vouliez un film un jour. Dans le multiplex, les billets étaient émis sur la base du premier arrivé, premier servi et les gens se tenaient les uns derrière les autres en attendant leur tour. Donc que feras-tu?? Vous devez être allé à l'arrière et vous tenir derrière la dernière personne à attendre le billet.

Ici, les gens se tiennent les uns derrière les autres et ils sont servis en fonction du Premier entré, premier sorti (FIFO) mécanisme. Un tel arrangement est connu comme un Queue.

Exemples de file d'attente de la vie quotidienne

Prenons quelques exemples où le type de file d'attente fonctionne dans la vie quotidienne:

• Répondeur téléphonique La personne qui appelle en premier sur votre gadget est la première à être suivie.
• Machine de vérification des bagages - Vérifie les bagages qui ont été conservés en premier sur le tapis roulant.
• Véhicules sur le pont de péage - Les véhicules arrivant tôt partent en premier.
• Centre d'appel - les systèmes téléphoniques utiliseront les files d'attente, pour mettre en ordre les personnes qui les appellent, jusqu'à ce qu'un représentant de service soit libre.

Tous ces exemples suivent Premier entré dernier sorti stratégie.

Création d'une structure de données de file d'attente

Outre les opérations complémentaires, je peux dire que les principales opérations possibles sur la file d'attente sont:

un. En file d'attente ou ajoutez un élément à la fin de la file d'attente.

2. De-queue ou supprimer un élément du début de la file d'attente

Maintenant, commençons par créer une file d'attente de classe en Python:

class File d'attente: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ back = -1 self .__ front = 0

• taille max est le nombre maximum d'éléments attendus dans la file d'attente.
• Les éléments de la file d'attente sont stockés dans la liste python
• back indique la position d'index du dernier élément de la file d'attente.
• L'arrière est initialement considéré comme -1 car la file d'attente est vide
• Front indique la position du premier élément dans la file d'attente.
• Le front est pris à 0 au départ car il pointera toujours vers le premier élément de la file d'attente

Mettre en file d'attente

Maintenant, lorsque vous essayez de mettre des éléments en file d'attente dans la file d'attente, vous devez vous rappeler les points suivants:

• S'il reste de l'espace dans la file d'attente ou non, c'est-à-dire si l'arrière est égal à max_size -1
• L'arrière indiquera le dernier élément inséré dans la file d'attente.

Alors, quel sera l'algorithme ??

#returns max_size de la file def get_max_size (self): return self .__ max_size #returns bool value si la file est pleine ou non, True si pleine et False sinon def is_full (self): return self .__ back == self .__ max_size-1 # insère / met en file d'attente des données dans la file d'attente si elle n'est pas complète def met en file d'attente (self, data): if (self.is_full ()): print ('La file d'attente est pleine. __elements [self .__ arrière] = données # afficher tout le contenu de la file def affichage (self): for i in range (0, self .__ back + 1): print (self .__ elements [i]) #Vous pouvez utiliser le ci-dessous __str __ () pour imprimer les éléments de l'objet DS lors du débogage def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg

Maintenant, lorsque vous exécutez ce qui suit:

queue1 = File d'attente (5)

#Enqueue tous les éléments requis.

queue1.enqueue («A»)

queue1.enqueue («B»)

qu'est-ce que sérialiser en java

queue1.enqueue («C»)

queue1.enqueue («D»)

queue1.enqueue («E»)

queue1.display ()

queue1.enqueue («F»)

impression (file d'attente1)

Production:

À

B

C

ré

EST

La file d'attente est pleine. Pas de mise en file d'attente possible

Données de la file d'attente (de l'avant vers l'arrière): A B C D E

Supprimer la file d'attente

Maintenant, comme vous avez inséré / mis en file d'attente les éléments dans la file d'attente, vous voulez les retirer / supprimer de la file d'attente, vous devez donc prendre soin de ce qui suit:

• Il y a des éléments dans la file d'attente, c'est-à-dire que l'arrière ne doit pas être égal à -1.
• Deuxièmement, vous devez vous rappeler que, comme les éléments sont supprimés du front, après la suppression du front, il faut incrémenter pour pointer le front suivant.
• Le front ne doit pas pointer vers la fin de la file d'attente, c'est-à-dire égal à max_size.

Alors, quel sera l'algorithme ??

#fonction pour vérifier si la file d'attente est vide ou non def is_empty (self): if (self .__ back == - 1 ou self .__ front == self .__ max_size): return True else: return False #fonction pour déque un élément et retourner il def dequeue (self): if (self.is_empty ()): print ('queue is already empty') else: data = self .__ elements [self .__ front] self .__ front + = 1 retourne les données #fonction pour afficher les éléments de de l'avant vers l'arrière si la file d'attente n'est pas vide def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ back + 1): print (self .__ elements [i]) else : print ('file vide')

Maintenant, lorsque vous exécutez ce qui suit:

queue1 = File d'attente (5)

#Enqueue tous les éléments requis

queue1.enqueue («A»)

queue1.enqueue («B»)

queue1.enqueue («C»)

queue1.enqueue («D»)

queue1.enqueue («E»)

impression (file d'attente1)

#Dequeue tous les éléments requis

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

#Affichez tous les éléments de la file d'attente.

queue1.display ()

Production:

Données de la file d'attente (de l'avant vers l'arrière): A B C D E

Retiré de la file d'attente: A

Retiré de la file d'attente: B

Retiré de la file d'attente: C

Retiré de la file d'attente: D

Retiré de la file d'attente: E

la file d'attente est déjà vide

Retiré de la file d'attente: aucun

file d'attente vide

Applications de la file d'attente

À partir de maintenant, vous avez déjà compris les bases de la file d'attente. Maintenant, pour approfondir, nous examinerons certaines de ses applications.

• Exemple 1:

File d'attente d'impression sous Windows utilise une file d'attente pour stocker tous les travaux d'impression actifs et en attente. Lorsque nous voulons imprimer des documents, nous émettons des commandes d'impression l'une après l'autre. En fonction des commandes d'impression, les documents seront alignés dans la file d'attente d'impression. Lorsque l'imprimante est prête, le document sera envoyé dans l'ordre premier entré premier sorti pour l'imprimer.

Supposons que vous ayez émis des commandes d'impression pour 3 documents dans l'ordre doc1, suivi de doc2 et doc3.
La file d'attente d'impression sera remplie comme indiqué ci-dessous:

doc-n, où le doc est le document envoyé pour impression et n, est le nombre de pages du document. Par exemple, doc2-10 signifie que doc2 doit être imprimé et qu'il a 10 pages. Voici un code qui simule le fonctionnement de la file d'attente d'impression. Parcourez le code et observez comment la file d'attente est utilisée dans cette implémentation.

class File d'attente: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ arrière = -1 self .__ front = 0 def is_full (self): if (self .__ arrière = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ arrière): return True return False def mettre en file d'attente (self, data): if (self.is_full ()): print ('La file d'attente est pleine !!!') else: self .__ arrière + = 1 self .__ éléments [self .__ arrière] = données def dequeue (self): if (self.is_empty ()): print ('La file d'attente est vide! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): pour l'index dans la plage (self .__ front, self .__ back + 1): print (self .__ elements [index]) def get_max_size (self): return self .__ max_size #Vous pouvez utiliser le __str __ () ci-dessous pour imprimer les éléments de l'objet DS pendant #debugging def __str __ (self): msg = [] index = self .__ front while (indice<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()

Production:

doc1-5 envoyé pour impression

doc2-3 envoyé pour impression

doc3-6 envoyé pour impression

doc1-5 imprimé

Restant non. de pages dans l'imprimante: 7

code fibonacci c ++

doc2-3 imprimé

Restant non. de pages dans l'imprimante: 4

Impossible d'imprimer le doc3. Pas assez de pages dans l'imprimante

• Exemple 2:

Essayons de comprendre un autre exemple qui utilise la structure de données de file d’attente. Pouvez-vous essayer de comprendre le code et dire ce que fait la fonction suivante?

1. def amusant (n):
2. aqueue = File d'attente (100)
3. pour num dans la plage (1, n + 1):
4. mettre en file d'attente (num)
5. résultat = 1
6. while (not (aqueue.is_empty ())):
7. num = AQUUE.DEQUEUE ()
8. résultat * = num
9. imprimer (résultat)

Lorsque la fonction fun () est invoquée en passant n,

• les lignes 2 à 4 mettent en file d'attente les éléments de 1 à n
• les lignes 5 à 8 trouve le produit de ces éléments en le désalignant un par un

Avec cela, nous arrivons à la fin de cet article sur la structure des données de file d'attente. Si vous avez bien compris et exécuté les codes par vous-même, vous n'êtes plus un débutant dans la structure des données de file d'attente.

Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de cet article et nous vous répondrons dans les plus brefs délais.

Pour obtenir des connaissances approfondies sur Python ainsi que sur ses différentes applications, vous pouvez vous inscrire en direct avec une assistance 24/7 et un accès à vie.