Python File d'attente : exemple FIFO, LIFO

Qu'est-ce que le Python File d'attente?

Une file d'attente est un conteneur qui contient des données. Les données saisies en premier seront supprimées en premier, c'est pourquoi une file d'attente est également appelée « Premier entré, premier sorti » (FIFO). La file d'attente a deux extrémités avant et arrière. Les articles sont saisis par l'arrière et retirés par l'avant.

Comment Python Travail en file d'attente ?

La file d'attente peut être facilement comparée à l'exemple du monde réel : la file de personnes faisant la queue au guichet, la personne debout en premier recevra le billet en premier, suivie de la personne suivante et ainsi de suite. La même logique s'applique également à la structure des données de file d'attente.

Voici une représentation schématique de la file d'attente :

Le Arrière représente le point où les éléments sont insérés dans la file d'attente. Dans cet exemple, 7 est la valeur pour cela.

Le Avant représente le point où les éléments de la file d'attente seront supprimés. Si vous supprimez un élément de la file d'attente, le premier élément que vous obtiendrez est 1, comme le montre la figure.

L'élément 1 a été le premier à être inséré dans la file d'attente, et lors de sa suppression, il est le premier à sortir. La file d'attente s'appelle donc FIRST IN FIRST OUT (FIFO).

Dans une file d'attente, les éléments sont supprimés dans l'ordre et ne peuvent pas être supprimés entre les deux. Vous ne pouvez tout simplement pas supprimer l'élément 5 au hasard de la file d'attente, pour ce faire, vous devrez supprimer tous les éléments avant 5. Les éléments de la file d'attente seront supprimés dans l'ordre dans lequel ils sont insérés.

Types de file d'attente dans Python

Il existe principalement deux types de files d'attente Python:

• File d'attente Premier entré, premier sorti : Pour cela, l'élément qui va en premier sera le premier à sortir. Pour travailler avec FIFO, il faut appeler File d'attente() classe du module de file d’attente.
• File d'attente Dernier entré, premier sorti : Ici, l'élément entré en dernier sera le premier à sortir. Pour travailler avec LIFO, vous devez appeler LifoQueue() classe du module de file d’attente.

Python Installation de la file d'attente

Il est très simple de travailler avec une file d'attente en python. Voici les étapes à suivre pour utiliser la file d'attente dans votre code.

Étape 1) Il vous suffit d'importer le module de file d'attente, comme indiqué ci-dessous :

import queue

Le module est disponible par défaut avec python et vous n'avez besoin d'aucune installation supplémentaire pour commencer à travailler avec la file d'attente. Il existe 2 types de file d'attente FIFO (premier entré, premier sorti) et LIFO (dernier entré, premier sorti).

Étape 2) Pour travailler avec la file d'attente FIFO, appelez la classe Queue à l'aide du module de file d'attente importé comme indiqué ci-dessous :

import queue
q1 = queue.Queue()

Étape 3) Pour travailler avec la file d'attente LIFO, appelez la classe LifoQueue() comme indiqué ci-dessous :

import queue
q1 = queue.LifoQueue()

Méthodes disponibles dans les classes Queue et LifoQueue

Voici les méthodes importantes disponibles dans les classes Queue et LifoQueue :

• mettre(élément): Cela placera l'élément dans la file d'attente.
• obtenir(): Cela vous renverra un élément de la file d'attente.
• vide(): Il retournera vrai si la file d'attente est vide et faux si des éléments sont présents.
• qsize() : renvoie la taille de la file d'attente.
• complet(): renvoie vrai si la file d'attente est pleine, sinon faux.

Exemple de file d'attente premier entré, premier sorti

Dans le cas du premier entré, premier sorti, l’élément qui va en premier sera le premier à sortir.

Ajouter un élément dans une file d'attente

Travaillons sur un exemple pour ajouter un élément dans une file d'attente. Pour commencer à travailler avec la file d'attente, importez d'abord la file d'attente du module, comme indiqué dans l'exemple ci-dessous.

Pour ajouter un élément, vous pouvez utiliser la méthode put() comme indiqué dans l'exemple :

import queue
q1 = queue.Queue()
q1.put(10) #this will additem 10 to the queue.

Par défaut, la taille de la file d'attente est infinie et vous pouvez y ajouter n'importe quel nombre d'éléments. Si vous souhaitez définir la taille de la file d'attente, la même chose peut être faite comme suit

import queue
q1 = queue.Queue(5) #The max size is 5.
q1.put(1)
q1.put(2)
q1.put(3)
q1.put(4)
q1.put(5)
print(q1.full()) # will return true.

Sortie :

True

Désormais, la taille de la file d'attente est de 5, et elle ne prendra pas plus de 5 éléments, et la méthode q1.full() retournera true. L’ajout d’éléments supplémentaires n’exécutera plus le code.

Supprimer un élément de la file d'attente

Pour supprimer un élément de la file d'attente, vous pouvez utiliser la méthode appelée get(). Cette méthode autorise les éléments de la file d’attente lorsqu’elle est appelée.

L'exemple suivant montre comment supprimer un élément de la file d'attente.

import queue
q1 = queue.Queue()
q1.put(10)

item1 = q1.get()

print('The item removed from the queue is ', item1)

Sortie :

The item removed from the queue is  10

Exemple de file d'attente Dernier entré, premier sorti

Dans le cas du dernier dans la file d'attente du premier sorti, l'élément entré en dernier sera le premier à sortir.

Pour travailler avec LIFO, c'est-à-dire dernier dans la file d'attente, premier sorti, nous devons importer le module de file d'attente et utiliser la méthode LifoQueue().

Ajouter un élément dans une file d'attente

Ici, nous comprendrons comment ajouter un élément à la file d'attente LIFO.

import queue
q1 = queue.LifoQueue()
q1.put(10)

Vous devez utiliser la méthode put() sur LifoQueue, comme indiqué dans l'exemple ci-dessus.

Supprimer un élément de la file d'attente

Pour supprimer un élément de la file d'attente LIFO, vous pouvez utiliser la méthode get().

import queue
q1 = queue.LifoQueue()
q1.put(10)

item1 = q1.get()

print('The item removed from the LIFO queue is ', item1)

Sortie :

The item removed from the LIFO queue is  10

Ajouter plus d'un élément dans une file d'attente

Dans les exemples ci-dessus, nous avons vu comment ajouter un seul élément et supprimer l'élément pour FIFO et LIFOqueue. Nous allons maintenant voir comment ajouter plus d’un élément et également le supprimer.

Ajouter un élément dans une file d'attente FIFO

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

Supprimer un élément de la file d'attente FIFO

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Sortie :

The value is  0
The value is  1
The value is  2
The value is  3
The value is  4
The value is  5
The value is  6
The value is  7
The value is  8
The value is  9
The value is  10
The value is  11
The value is  12
The value is  13
The value is  14
The value is  15
The value is  16
The value is  17
The value is  18
The value is  19

Ajouter un élément dans une file d'attente LIFO

import queue
q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

Supprimer un élément de la file d'attente LIFO

import queue
q1 = queue.LifoQueue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue


while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Sortie :

The value is  19
The value is  18
The value is  17
The value is  16
The value is  15
The value is  14
The value is  13
The value is  12
The value is  11
The value is  10
The value is  9
The value is  8
The value is  7
The value is  6
The value is  5
The value is  4
The value is  3
The value is  2
The value is  1
The value is  0 

File d'attente de tri

L'exemple suivant montre le tri en file d'attente. L'algorithme utilisé pour le tri est le tri à bulles.

import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

#using bubble sort on the queue
n =  q1.qsize()
for i in range(n):
    x = q1.get() # the element is removed
    for j in range(n-1):
        y = q1.get() # the element is removed
        if x > y :  
            q1.put(y)   #the smaller one is put at the start of the queue
        else:
            q1.put(x)  # the smaller one is put at the start of the queue
            x = y     # the greater one is replaced with x and compared again with nextelement
    q1.put(x)

while (q1.empty() == False): 
print(q1.queue[0], end = " ")  
        q1.get()

Sortie :

3 4 5 10 11 21

Revremplir la file d'attente

Pour inverser la file d'attente, vous pouvez utiliser une autre file d'attente et une récursivité.

L'exemple suivant montre comment inverser la file d'attente.

Exemple :

import queue
q1 = queue.Queue()

q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

def reverseQueue (q1src, q2dest) :  
    buffer = q1src.get()
    if (q1src.empty() == False) :
reverseQueue(q1src, q2dest)      #using recursion
    q2dest.put(buffer)
return q2dest

q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)

while (qReversed.empty() == False): 
print(qReversed.queue[0], end = " ")  
        qReversed.get()

Sortie :

10 3 21 4 5 11

Résumé

• Une file d'attente est un conteneur qui contient des données. Il existe deux types de file d'attente, FIFO et LIFO.
• Pour une file d'attente FIFO (First in First out Queue), l'élément qui passe en premier sera le premier à sortir.
• Pour un LIFO (Last in First out Queue), l'élément entré en dernier sera le premier à sortir.
• Un élément dans une file d'attente est ajouté à l'aide de la méthode put(item).
• Pour supprimer un élément, la méthode get() est utilisée.