Travailler avec les files d'attente

Structures de données et algorithmes en Python

Miriam Antona

Software Engineer

Files d'attente

FIFO : First-In First-Out
- Le premier inséré est le premier à être retiré

Files d'attente

FIFO : First-In First-Out
- Le premier inséré est le premier à être retiré

Files d'attente

FIFO : First-In First-Out
- Le premier inséré est le premier à être retiré

Files d'attente – structure

Schéma d'une file d'attente avec des noms de plats internationaux.

Files d'attente – structure

Schéma d'une file d'attente avec des noms de plats internationaux. Le mot « head » pointe le début de la file.

Début : head

Files d'attente – structure

Schéma d'une file d'attente avec des noms de plats internationaux. Le mot « tail » pointe la fin de la file.

Début : head
Fin : tail

Files d'attente – propriétés

Schéma d'une file d'attente avec les mots « head » au début et « tail » à la fin.

Files d'attente – propriétés

Schéma d'une file d'attente. Un nouvel élément est inséré à la fin (tail).

Insérer seulement à la fin
- Enqueue

Files d'attente – propriétés

Schéma d'une file d'attente. Le premier élément est barré car il sera retiré.

Insérer seulement à la fin
- Enqueue
Retirer seulement au début

Files d'attente – propriétés

Schéma d'une file d'attente avec deux éléments après retrait du premier.

Insérer seulement à la fin
- Enqueue
Retirer seulement au début
- Dequeue
Autres types de files :
- Doubles extrémités
- Circulaires
- À priorité

Files d'attente – cas d'usage concrets

Tâches d'impression sur une imprimante
- Les documents s'impriment selon l'ordre reçu
Applications où l'ordre des requêtes compte
- Billets de concert
- Services de taxi

Files d'attente – implantation

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Queue:
  def __init__(self):
    self.head = None
    self.tail = None

Files d'attente – enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Schéma d'une file d'attente avec un élément, implantée avec un nœud.

Files d'attente – enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

Schéma d'une file d'attente avec un élément. Les mots « head » et « tail » pointent le nœud.

Files d'attente – enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:

Schéma d'une file d'attente avec deux éléments. Un nouveau nœud est prêt à être inséré.

Files d'attente – enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node

Schéma d'une file d'attente avec trois éléments. Le mot « tail » pointe encore le deuxième nœud.

Files d'attente – enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node
    self.tail = new_node

Schéma d'une file d'attente avec trois éléments. Le mot « tail » pointe le dernier nœud inséré.

Files d'attente – dequeue

Schéma d'une file d'attente avec trois éléments. « head » pointe le premier nœud et « tail » le dernier.

def dequeue(self):

  if self.head:

Files d'attente – dequeue

Schéma d'une file d'attente avec trois éléments. « head » et « current_node » pointent le premier nœud; « tail » pointe le dernier.

def dequeue(self):
  if self.head:
    current_node = self.head

Files d'attente – dequeue

Schéma d'une file d'attente avec trois éléments. « head » pointe le premier nœud, « current_node » le deuxième, et « tail » le dernier.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next

Files d'attente – dequeue

Schéma d'une file d'attente avec deux éléments. « head » pointe le premier, « tail » le dernier. Un nœud à part est indiqué « current_node ».

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

Files d'attente – dequeue

Un nœud avec « current_node » et « tail » pointant dessus. « head » pointe vers null.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None


    if self.head == None:

Files d'attente – dequeue

Un nœud avec « current_node » pointant dessus. « head » et « tail » pointent vers null.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

    if self.head == None:
      self.tail = None

SimpleQueue en Python

Module : queue
- Queue
- SimpleQueue

import queue


orders_queue = queue.SimpleQueue()


orders_queue.put("Sushi")
orders_queue.put("Lasagna")
orders_queue.put("Paella")


print("The size is: ", orders_queue.qsize())

The size is: 3

print(orders_queue.get())
print(orders_queue.get())
print(orders_queue.get())

Sushi
Lasagna
Paella

print("Empty queue: ", orders_queue.empty())

Empty queue: True

Passons à la pratique !

Structures de données et algorithmes en Python