Travail avec des 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 élément inséré est le premier à être supprimé

      Une image d’une file d’attente de supermarché avec trois personnes.

Structures de données et algorithmes en Python

Files d’attente

  • FIFO: First-In First-Out

    • Le premier élément inséré est le premier à être supprimé

      Une image d’une file d’attente de supermarché avec deux personnes, car la première a quitté la file.

Structures de données et algorithmes en Python

Files d’attente

  • FIFO: First-In First-Out

    • Le premier élément inséré est le premier à être supprimé

      Une photo d’une file d’attente de supermarché avec une seule personne, car la première et la deuxième personnes ont quitté la file.

Structures de données et algorithmes en Python

Files d’attente - structure

Représentation schématique d’une file d’attente avec les noms de quelques plats internationaux.

Structures de données et algorithmes en Python

Files d’attente - structure

Représentation schématique d’une file d’attente avec les noms de quelques plats internationaux. Le mot "tête" désigne le début de la file d’attente.

  • Début : tête
Structures de données et algorithmes en Python

Files d’attente - structure

Représentation schématique d’une file d’attente avec les noms de quelques plats internationaux. Le mot « queue » pointe vers la fin de la file.

  • Début : tête
  • Fin : queue
Structures de données et algorithmes en Python

Files d’attente - fonctionnalités

Représentation schématique d’une file d’attente avec les noms de deux plats internationaux. Le mot « tête » désigne le début de la file et le mot « queue » la fin.

Structures de données et algorithmes en Python

Files d’attente - fonctionnalités

Représentation schématique d’une file d’attente. Un nouvel élément a été inséré à la fin de la file d’attente.

  • Peut s’insérer à la fin
    • Mettre en file d’attente
Structures de données et algorithmes en Python

Files d’attente - fonctionnalités

Représentation schématique d’une file d’attente. Le premier élément de la file est barré car il sera supprimé.

  • Peut s’insérer à la fin
    • Mettre en file d’attente
  • Peut être retiré de la tête
Structures de données et algorithmes en Python

Files d’attente - fonctionnalités

Représentation schématique d’une file d’attente. La file d’attente ne contient que deux éléments, car le premier élément a été supprimé.

  • Peut s’insérer à la fin
    • Mettre en file d’attente
  • Peut être retiré de la tête
    • Retirer de la file d'attente
  • Autres types de files d’attente :
    • Files d’attente à double extrémité
    • Files d’attente circulaires
    • Files d’attente prioritaires
Structures de données et algorithmes en Python

Files d’attente - cas réels

  • Tâches d’impression dans une imprimante
    • Les documents sont imprimés dans l’ordre de réception
  • Applications où l’ordre compte
    • Billets pour un concert
    • Services de taxi
Structures de données et algorithmes en Python

Files d’attente - implémentation

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

class Queue:
  def __init__(self):
    self.head = None
    self.tail = None
Structures de données et algorithmes en Python

Files d’attente - mise en file d’attente

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Représentation schématique d’une file contenant un élément. La file d’attente a été implémentée avec un nœud.

Structures de données et algorithmes en Python

Files d’attente - mise en file d’attente

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

Représentation schématique d’une file contenant un élément. La file d’attente a été implémentée avec un nœud. Les mots « tête » et « queue » pointent vers le nœud.

Structures de données et algorithmes en Python

Files d’attente - mise en file d’attente

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

  else:

Représentation schématique d’une file d’attente comportant deux éléments. La file d’attente a été implémentée avec des nœuds. Un nouveau nœud est préparé pour être inséré.

Structures de données et algorithmes en Python

Files d’attente - mise en file d’attente

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

Représentation schématique d’une file d’attente comportant trois éléments. Le mot « queue » pointe toujours vers le deuxième nœud.

Structures de données et algorithmes en Python

Files d’attente - mise en file d’attente

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

Représentation schématique d’une file d’attente comportant trois éléments. Le mot « queue » pointe vers le dernier nœud inséré.

Structures de données et algorithmes en Python

Files d’attente - retrait de la file d'attente

Représentation schématique d’une file d’attente comportant trois éléments. Le mot « tête » désigne le premier nœud et le mot « queue » désigne le dernier nœud.

def dequeue(self):

  if self.head:
Structures de données et algorithmes en Python

Files d’attente - retrait de la file d'attente

Représentation schématique d’une file d’attente comportant trois éléments. Les mots « tête » et « noeud_actuel » pointent vers le premier nœud et le mot « queue » pointe vers le dernier nœud.

def dequeue(self):
  if self.head:
    current_node = self.head
Structures de données et algorithmes en Python

Files d’attente - retrait de la file d'attente

Représentation schématique d’une file d’attente comportant trois éléments. Le mot "tête" pointe vers le premier nœud, le mot "noeud_actuel" pointe vers le deuxième mot, et le mot "queue" pointe vers le dernier nœud.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
Structures de données et algorithmes en Python

Files d’attente - retrait de la file d'attente

Représentation schématique d’une file d’attente comportant deux éléments. Le mot "tête" pointe vers le premier nœud, et le mot "queue" pointe vers le dernier nœud. Il existe un autre nœud, distinct de la file d’attente, vers lequel pointe le mot "noeud_actuel".

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None
Structures de données et algorithmes en Python

Files d’attente - retrait de la file d'attente

Un nœud avec les mots "noeud_actuel" et "queue" pointant vers lui. Le mot "tête" 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:
Structures de données et algorithmes en Python

Files d’attente - retrait de la file d'attente

Un nœud avec le mot "noeud_actuel" pointant vers lui. Le mot "tête" et "queue" 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
Structures de données et algorithmes en Python

SimpleQueue en Python

  • Module : file d’attente
    • File d’attente
    • 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
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...