Travailler 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 inséré est le premier retiré

Files d’attente

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

Files d’attente

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

Files d’attente - structure

Représentation schématique d’une file avec des noms de plats internationaux.

Files d’attente - structure

Représentation schématique d’une file avec des noms de plats internationaux. Le mot « head » pointe le début de la file.

Début : head

Files d’attente - structure

Représentation schématique d’une file avec des noms de plats internationaux. Le mot « tail » pointe la fin de la file.

Début : head
Fin : tail

Files d’attente - caractéristiques

Représentation schématique d’une file avec les noms de deux plats internationaux. Le mot « head » pointe le début de la file et « tail » la fin.

Files d’attente - caractéristiques

Représentation schématique d’une file. Un nouvel élément a été inséré en fin de file (tail).

Insertion uniquement à la fin
- Enqueue

Files d’attente - caractéristiques

Représentation schématique d’une file. Le premier élément est barré car il va être retiré.

Insertion uniquement à la fin
- Enqueue
Retrait uniquement au début

Files d’attente - caractéristiques

Représentation schématique d’une file. La file n’a plus que deux éléments car le premier a été retiré.

Insertion uniquement à la fin
- Enqueue
Retrait uniquement au début
- Dequeue
Autres types de files :
- Files à double extrémité
- Files circulaires
- Files à priorité

Files d’attente - cas d’usage réels

Tâches d’impression sur une imprimante
- Les documents sont imprimés dans l’ordre de réception
Applications où l’ordre des requêtes compte
- Billets de concert
- Services de taxi

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

Files d’attente - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Représentation schématique d’une file avec un élément. La file est implémenté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

Représentation schématique d’une file avec un élément. Implémentée avec un nœud. Les mots « head » et « tail » pointent vers 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:

Représentation schématique d’une file avec deux éléments. Implémentée avec des nœuds. 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

Représentation schématique d’une file 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

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

Files d’attente - dequeue

Représentation schématique d’une file avec trois éléments. Le mot « head » pointe le premier nœud et « tail » le dernier.

def dequeue(self):

  if self.head:

Files d’attente - dequeue

Représentation schématique d’une file avec trois éléments. Les mots « head » et « current_node » pointent le premier nœud et « tail » le dernier.

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

Files d’attente - dequeue

Représentation schématique d’une file avec trois éléments. Le mot « 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

Représentation schématique d’une file avec deux éléments. Le mot « head » pointe le premier nœud et « tail » le dernier. Un autre nœud à part est pointé par « 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 les mots « current_node » et « tail » pointant dessus. Le mot « 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 pointé par « current_node ». Les mots « 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