File d'attente

7.1 Définition de la file d'attente et ses propriétés

File d'attente — c'est une structure de données abstraite qui représente une collection ordonnée d'éléments, organisée selon le principe "premier arrivé - premier parti" (First In, First Out, FIFO). Une file d'attente peut être comparée à une file de personnes dans un magasin : la première personne dans la file est la première à être servie.

Propriétés de la file d'attente :

• FIFO (First In, First Out) : Le premier élément ajouté sera le premier élément supprimé.
• Opérations limitées : La file d'attente prend en charge un ensemble limité d'opérations — ajout (enqueue), suppression (dequeue) et visualisation (peek) de l'élément en première position.
• Accès unidirectionnel : L'accès aux éléments est possible uniquement à partir des côtés avant (front) et arrière (rear).
• Simplicité de mise en œuvre : La file d'attente peut être facilement réalisée à l'aide d'un tableau ou d'une liste chaînée.

Principe de fonctionnement FIFO :

• Ajout d'un élément (enqueue) : Un nouvel élément est ajouté à la fin de la file d'attente.
• Suppression d'un élément (dequeue) : Le premier élément ajouté est retiré du début de la file d'attente.
• Visualisation de l'élément en tête (peek) : Permet de voir l'élément en première position de la file d'attente sans le supprimer.

Les éléments de la file d'attente sont ajoutés d'un côté (arrière) et supprimés de l'autre côté (avant). Ainsi, le premier élément ajouté est le premier retiré.

7.2 Opérations principales

Opérations principales : enqueue, dequeue, peek

Opération enqueue : Ajoute un nouvel élément à la fin de la file d'attente.

Complexité temporelle : O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Sortie: deque([10, 20])

Opération dequeue : Supprime et retourne l'élément du début de la file d'attente.

Complexité temporelle : O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Sortie: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Sortie: 10
print(queue)  # Sortie: deque([20])

Opération peek : Retourne l'élément en première position de la file d'attente sans le supprimer.

Complexité temporelle : O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Sortie: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Sortie: 10

7.3 Exemples d'utilisation de la file d'attente

Examinons quelques exemples d'utilisation de la file d'attente.

1 Gestion des tâches d'impression

La file d'attente est utilisée pour gérer les tâches d'impression, où les documents sont ajoutés à la file et imprimés dans l'ordre de leur arrivée.

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_job(self, job):
        self.queue.append(job)

    def print_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"Impression : {job}")

# Exemple d'utilisation :
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Sortie: Impression : Document1.pdf
printer_queue.print_job()  # Sortie: Impression : Document2.pdf

2 Traitement des requêtes sur un serveur web

La file d'attente est utilisée pour gérer les requêtes des clients arrivant sur un serveur web. Les requêtes sont traitées dans l'ordre de leur arrivée.

class RequestQueue:
    def __init__(self):
        self.queue = deque()

    def add_request(self, request):
        self.queue.append(request)

    def process_request(self):
        if self.queue:
            request = self.queue.popleft()
            print(f"Traitement de la requête : {request}")

# Exemple d'utilisation :
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Sortie: Traitement de la requête : GET /index.html
request_queue.process_request()  # Sortie: Traitement de la requête : POST /submit-form

3 File de messages dans les systèmes d'échange de messages

La file d'attente est utilisée pour gérer les messages dans les systèmes d'échange d'informations (par exemple, dans les courtiers de messages). Les messages sont traités dans l'ordre de leur arrivée.

class MessageQueue:
    def __init__(self):
        self.queue = deque()

    def send_message(self, message):
        self.queue.append(message)

    def receive_message(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"Message reçu : {message}")

# Exemple d'utilisation :
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Sortie: Message reçu : Hello
message_queue.receive_message()  # Sortie: Message reçu : World