fileattente

TP1-PROG-09 - Les Files#

Les files sont des structures de données proches des listes. Elles permettent de gérer l’arrivé et le départ de ses éléments.

La file d’attente#

La file d’attente est une structure de donnée qui permet de gérer des entrées et des sorties dans un ordre précis : le premier élément ajouté est le dernier que l’on peut enlever. En anglais une file est connue sous le nom FIFO (First In First Out).

Les opérations d’une file sont :

  • créer une nouvelle file vide

  • ajouter un nouvel élément à la file

  • supprimer un élément de la file

Ajouter un élément#

Nous ajoutons un élément dans la file avec la fonction append()

Simulons une file d’attente à la caféteria.

Nous commençons avec une file vide.

file = []

C’est midi et les personnes commençent à arriver.

La fonction append() permet de les ajouter à la liste file.

file.append('Anna')
file.append('Tom')
file.append('Léa')

Nous avons maintenant les personnes suivantes dans la file d’attente.

print(file)

['Anna', 'Tom', 'Léa']

Enlever un élément#

La première personne à être servie, est enlevée de la liste avec la fonction pop(0).

En d’autres termes, les éléments sont

  1. ajoutés à droite de la file (la liste)

  2. supprimés à gauche : c’est le premier élément (d’index 0) qui est supprimé

file.pop(0)

'Anna'

La file est devenu plus petite.

print(file)

['Tom', 'Léa']

Des nouvelles personnes arrivent.

file.append('Jim')
file.append('Noa')
file.append('Elsa')

Une nouvelle personne est servie.

file.pop(0)

'Tom'

Combient de personne sont en attente ?

len(file)

4

Qui est dans la file d’attente

print(file)

['Léa', 'Jim', 'Noa', 'Elsa']

Exercice 1#

Utilisez la fonction pop() pour enlever les personnes dans le bon ordre.

Exercice 2 : fonctions#

Il est possible de simplifier les deux primitives

  1. ajouter un élément

  2. enlever un élément

à l’aide d’une fonction (un sous-programme). Chaque fonction prendra comme argument une file. Cela permet

  • de pouvoir gérer plusieurs files en même temps

  • de s’affranchir de la notion d’index

A vous de définir les deux fonctions ayant les signatures suivantes :

def ajouter(file,element):
    # Modifier la méthode suivante
    file.extend(element)

def supprimer(file):
    # modifier les méthodes suivantes
    element = file[len(file)]
    print("Element supprimé : ",element)
    file.pop(1)

Que se passe-t-il si vous tentez de supprimer un élément dans une file vide ?

Modifiez la fonction supprimer(file) pour qu’il gère une file vide

migros

Exercice 3 : A la Migros#

Vous êtes maintenant capable de gérer plusieurs files indépendemment. Dans cet exercice, nous imaginons que nous voulons simuler le comportement des clients dans un magasin Migros où trois caisses sont ouvertes (et qu’il n’existe pas de système de self checking).

  1. Déclarez trois files distinctes : caisse1, caisse2, caisse3

  2. Testez vos fonctions ajouter(file, element) et supprimer(file sur vos trois files avec des clients (à vous de choisir les prénoms)

Question subsidiaire : est-il possible de compter l’ensemble des clients qui sont passés ce jour-là dans votre magasin Migros ?

poste

A la poste#

Nous allons maintenant simuler le système informatique de gestion de l’attente dans une poste.

  1. Le client entre dans la poste

  2. Il se dirige vers un distributeur de tickets

  3. Le distributeur imprime un numéro

  4. Lorsqu’un guichet est libre, l’employé se déclare libre et le système affiche la lettre du guichet au premier client de la file (en position 0)

Nous sommes à la Poste de Renens et il est 14h. Trois guichets sont ouverts A, B et C, deux personnes attendent dans la file. La machine à tickets indique que le prochain ticket délivré sera le 544.

file = [542, 543]

Si une personne entre, elle prend son numéro et elle s’insére dans la liste d’attente. Le numéro suivant est le 544

file.append(544)

La file d’attente comprend maintenant:

print(file)

[542, 543, 544]

Deux nouveaux clients entrent et prennent un ticket.

file.append(545)
file.append(546)
print(file)

[542, 543, 544, 545, 546]

Simulation des guichets#

Il y a trois guichets A, B, et C, qui vont se libérer de façon alétoire. Le temps de libération dépend de l’opération postale du client.

Nous importons le module random et utilisons la fonction choice() pour choisir un des trois guichets de façon aléatoire.

import random
random.choice('ABC')

'A'

Le prochain guichet qui se libère

random.choice('ABC')

'A'

C’est la personne entrée en premier qui peut se diriger vers le guichet qui se libère

suivant = file.pop(0)
guichet = random.choice('ABC')
print(suivant, guichet)

542 C

Exercice 4#

Traduisez en python les étapes suivantes :

  1. Une femme entre dans la poste, elle va chercher son ticket.

  2. Deux guichets se libèrent.

  3. Deux clients de la file les occupent.

  4. Trois nouveaux clients entrent dans la poste et vont chercher leurs ticket.

  5. Un guichet se libère

  6. L’homme pressé quitte la poste, il en a marre d’attendre

Après ces étapes, quel est l’état de la file ?

Quel est le prochain numéro délivré par le distributeur ?

Conseil : utilisez les fonction ajouter(file, element)et supprimer(file) que vous avez défini à l’exercice 2