File d'attente Python : comprendre FIFO et LIFO avec exemples pratiques

File d'attente Python : comprendre FIFO et LIFO avec exemples pratiques

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

Une file d'attente est une structure de données qui stocke les éléments dans un ordre linéaire. Les éléments sont ajoutés à l'arrière et retirés de l'avant, suivant le principe Premier Entré, Premier Sorti (FIFO). La file expose deux extrémités logiques : front (avant) et rear (arrière) — enfiler à l'arrière, défiler de l'avant.

Dans ce tutoriel, vous apprendrez :

• Comment fonctionne le module queue de Python.
• Types de files disponibles en Python.
• Comment installer et importer le module.
• Méthodes clés sur les objets Queue et LifoQueue.
• Exemples pratiques pour files FIFO et LIFO.
• Opérations par lot, tri et inversion de files.

Comment fonctionne le module Queue ?

Le comportement est analogue à une file physique : la première personne dans la file est la première servie. Dans la structure de données file, l'élément enfilé en premier sera défilé en premier.

Le point rear (arrière) est où les nouveaux éléments sont insérés (ex. : valeur 7). Le point front (avant) est où les éléments quittent la file ; retirer le premier élément donne la valeur 1.

Comme la file est linéaire, vous ne pouvez pas retirer un élément arbitraire au milieu ; vous devez défiler tous les éléments précédents d'abord.

Types de files en Python

Le module queue de Python offre deux classes de file principales :

• File FIFO – utilisez Queue(). L'élément le plus ancien est toujours le premier retiré.
• File LIFO – utilisez LifoQueue(). L'élément le plus récemment ajouté est retourné en premier.

Démarrage : Importation du module

Python inclut le module queue par défaut ; aucune installation externe n'est requise.

import queue

Instancier une file FIFO :

q1 = queue.Queue()

Instancier une file LIFO :

q1 = queue.LifoQueue()

Méthodes clés

Les classes Queue et LifoQueue exposent la même API de base :

• put(item) – enfiler un élément.
• get() – défiler et renvoyer l'élément suivant.
• empty() – renvoie True si la file n'a pas d'éléments.
• full() – renvoie True si la file a atteint sa taille maximale.
• qsize() – renvoie le nombre actuel d'éléments.

Exemple file FIFO

Enfiler un seul élément

import queue
q1 = queue.Queue()
q1.put(10)  # ajouter 10 à la file

Enfiler plusieurs éléments avec une limite de taille

q1 = queue.Queue(maxsize=5)  # maximum 5 éléments
for i in range(1, 6):
    q1.put(i)
print(q1.full())  # → True

Sortie :

True

Défiler un élément

element = q1.get()
print('Élément défilé :', element)

Sortie :

Élément défilé : 10

Exemple file LIFO

Enfiler un seul élément

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

Défiler un élément

element = q1.get()
print('Défiler depuis LIFO :', element)

Sortie :

Défiler depuis LIFO : 10

Opérations par lot

FIFO – Enfiler 20 nombres

q1 = queue.Queue()
for i in range(20):
    q1.put(i)

FIFO – Défiler tous

while not q1.empty():
    print('Valeur :', q1.get())

Sortie :

Valeur : 0
Valeur : 1
...
Valeur : 19

LIFO – Enfiler 20 nombres

q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i)

LIFO – Défiler tous

while not q1.empty():
    print('Valeur :', q1.get())

Sortie :

Valeur : 19
Valeur : 18
...
Valeur : 0

Tri d'une file (tri à bulles)

q1 = queue.Queue()
for item in [11, 5, 4, 21, 3, 10]:
    q1.put(item)

n = q1.qsize()
for i in range(n):
    x = q1.get()
    for j in range(n-1):
        y = q1.get()
        if x > y:
            q1.put(y)
        else:
            q1.put(x)
        x = y
    q1.put(x)

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

Sortie :

3 4 5 10 11 21

Inverser une file en utilisant la récursion

def inverser_file(source, destination):
    element = source.get()
    if not source.empty():
        inverser_file(source, destination)
    destination.put(element)
    return destination

q1 = queue.Queue()
for item in [11, 5, 4, 21, 3, 10]:
    q1.put(item)

q2 = queue.Queue()
inverser_file(q1, q2)

while not q2.empty():
    print(q2.queue[0], end=' ')
    q2.get()

Sortie :

10 3 21 4 5 11

Résumé rapide

• queue.Queue de Python implémente FIFO ; queue.LifoQueue implémente LIFO.
• Utilisez put() pour enfiler et get() pour défiler.
• Les deux classes exposent empty(), full() et qsize() pour l'inspection d'état.
• Vous pouvez définir une taille maximale sur une file FIFO ; tenter de put() au-delà bloquera jusqu'à ce qu'un espace se libère.
• Le tri et l'inversion sont possibles avec des algorithmes standards, bien que deque de collections offre souvent plus de flexibilité.