Comme une pile, la file d'attente est une structure de données linéaire qui stocke les éléments selon un ordre premier entré, premier sorti ( FIFO ) manière. Avec une file d'attente, l'élément ajouté le moins récemment est supprimé en premier. Un bon exemple de file d'attente est n'importe quelle file d'attente de consommateurs pour une ressource dans laquelle le consommateur arrivé en premier est servi en premier.

Les opérations associées à la file d'attente sont :

• Mettre en file d'attente : Ajoute un élément à la file d'attente. Si la file d’attente est pleine, on parle alors d’une condition de débordement – ​​Complexité temporelle : O(1)
• Par conséquent: Supprime un élément de la file d'attente. Les éléments sont affichés dans le même ordre dans lequel ils ont été poussés. Si la file d’attente est vide, alors on dit qu’il s’agit d’une condition de sous-débordement – ​​Complexité temporelle : O(1)
• Devant: Récupérer l'élément de premier plan de la file d'attente – Complexité temporelle : O(1)
• Arrière: Récupère le dernier élément de la file d'attente – Complexité temporelle : O(1)

Implémenter une file d'attente en Python

Il existe différentes manières d'implémenter une file d'attente dans Python. Cet article couvre l'implémentation de la file d'attente à l'aide des structures de données et des modules de la bibliothèque Python. La file d'attente Python peut être implémentée des manières suivantes :

formater la chaîne java

• liste
• collections.deque
• queue.Queue

Implémentation à l'aide d'une liste

List est une structure de données intégrée à Python qui peut être utilisée comme file d'attente. Au lieu de mettre en file d'attente() et par conséquent () , ajouter() et populaire() fonction est utilisée. Cependant, les listes sont assez lentes à cet effet car l'insertion ou la suppression d'un élément au début nécessite de décaler tous les autres éléments d'un, ce qui nécessite un temps O(n).
Le code simule une file d'attente à l'aide d'une liste Python. Il ajoute des éléments 'un' , 'b' , et 'c' à la file d'attente, puis les retire de la file d'attente, ce qui entraîne une file d'attente vide à la fin. La sortie montre la file d'attente initiale, les éléments retirés de la file d'attente ( 'un' , 'b' , 'c' ), et l’état vide de la file d’attente.

Python3

>

>

Sortir:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements []>

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list>

Implémentation à l'aide de collections.deque

La file d'attente en Python peut être implémentée à l'aide de la classe deque du module collections. Deque est préféré à list dans les cas où nous avons besoin d'opérations d'ajout et de pop plus rapides depuis les deux extrémités du conteneur, car deque fournit une complexité temporelle O(1) pour les opérations d'ajout et de pop par rapport à list qui fournit une complexité temporelle O(n). . Au lieu de mettre en file d'attente et deque, les fonctions append() et popleft() sont utilisées.
Le code utilise undeque>ducollections>module pour représenter une file d’attente. Il ajoute 'un' , 'b' , et 'c' à la file d'attente et les retire de la file d'attente avec q.popleft()> , ce qui entraîne une file d'attente vide. Sans commentaire q.popleft()> une fois la file d'attente vide, cela déclencherait unIndexError>. Le code illustre les opérations de file d'attente et gère un scénario de file d'attente vide.

Python3

qu'est-ce qu'un double Java

trier un tableau java

>

>

Sortir:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])>

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque>

Implémentation à l'aide de queue.Queue

Queue est un module intégré de Python qui est utilisé pour implémenter une file d'attente. queue.Queue(maxsize) initialise une variable à une taille maximale de maxsize. Une taille maximale de zéro « 0 » signifie une file d'attente infinie. Cette file d'attente suit la règle FIFO.
Différentes fonctions sont disponibles dans ce module :

• taille max – Nombre d'éléments autorisés dans la file d'attente.
• vide() – Renvoie True si la file d'attente est vide, False sinon.
• complet() – Renvoie True s'il y a des éléments de taille maximale dans la file d'attente. Si la file d'attente a été initialisée avec maxsize=0 (valeur par défaut), alors full() ne renvoie jamais True.
• obtenir() – Supprimer et renvoyer un élément de la file d'attente. Si la file d'attente est vide, attendez qu'un élément soit disponible.
• get_nowait() – Renvoyez un élément s’il est immédiatement disponible, sinon augmentez QueueEmpty.
• mettre (article) – Mettez un élément dans la file d’attente. Si la file d'attente est pleine, attendez qu'un emplacement libre soit disponible avant d'ajouter l'élément.
• put_nowait (élément) – Mettez un élément dans la file d’attente sans le bloquer. Si aucun emplacement libre n’est immédiatement disponible, augmentez QueueFull.
• qsize() – Renvoie le nombre d'éléments dans la file d'attente.

Exemple: Ce code utilise leQueue>classe de laqueue>module. Il commence avec une file d'attente vide et la remplit avec ' un', 'b' , et 'c' . Après avoir été retirée de la file d'attente, la file d'attente devient vide et « 1 » est ajouté. Bien qu'il ait été vide auparavant, il reste plein, car la taille maximale est définie sur 3. Le code illustre les opérations de file d'attente, notamment la vérification du remplissage et du vide.

Python3

file d'attente et file d'attente prioritaire en Java

>

>

Sortir:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False>