Piles et files¶
Les piles et 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.
Voici une file d’attente de la Poste, avec un panneau qui affiche la gestion de la liste d’attente.
La pile¶
La pile est une structure de données qui permet de gérer un ensemble d’éléments et leurs arrivées et départs dans le temps.
Dans une pile d’assiettes, il est possible d’accéder uniquement à la dernière ajoutée: celle qui se trouve au sommet.
Il n’est donc possible d’effectuer que les opérations suivantes :
créer une nouvelle pile vide
empiler un nouvel élément
récupérer un élément au sommet de la pile
Dans une pile, le dernier élément ajouté est le premier que l’on peut enlever
Cette structure s’appelle LIFO (Last In First Out en anglais)
Ajouter un élément¶
On ajoute un élément avec la fonction append() et on le supprime avec la fonction pop(). Simulons une pile avec des livres que nous avons sur notre bureau.
Commençons avec une pile vide.
pile = []
Nous allons maintenant ajouter 3 livres sur la pile, en utilisant la fonction append().
pile.append('Zola')
pile.append('Balzac')
pile.append('Hugo')
Voici la pile actuelle
pile
['Zola', 'Balzac', 'Hugo']
Enlever un élément¶
Dans une pile, le seul livre qui peut être enlevé est le dernier ajouté. Nous utilisons la fonction pop() pour enlever un livre.
pile.pop()
'Hugo'
Mettons 3 autres livres sur la pile.
pile.append('Frisch')
pile.append('Murakami')
pile.append('Higgins')
Enlevons-en un.
pile.pop()
'Higgins'
Combien de livres restent sur la pile ?
len(pile)
4
Lesquels?
pile
['Zola', 'Balzac', 'Frisch', 'Murakami']
Exercice
Enlevez d’abord un livre et ajoutez ensuite deux nouveaux livres à vous.
Afficher les éléments¶
Essayons d’afficher la pile des livres.
for livre in pile:
print(livre)
Zola
Balzac
Frisch
Murakami
Le problème avec cette façon d’imprimer c’est que la pile n’est pas dans le bon ordre. Nous pouvons utiliser l’opérateur de tranche [::-1] pour inverser l’ordre d’une liste.
for livre in pile[::-1]:
print(livre)
Murakami
Frisch
Balzac
Zola
Exercice
Enlevez un livre de la pile avec pop et affichez la pile qui reste avec l’opérateur de tranche [::-1].
La file d’attente¶
La file d’attente est une structure de données qui permet de gérer les arrivées et les départs.
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
Dans une file, le premier élément ajouté est le dernier que l’on peut enlever
En anglais une file d’attente est connu sous le nom FIFO (First In First Out).
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.
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)
file.pop(0)
'Anna'
La file est devenu plus petite.
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
file
['Léa', 'Jim', 'Noa', 'Elsa']
Exercice
Utilisez la fonction pop() pour enlever les personnes dans le bon ordre.
A la poste¶
Nous sommes à la Poste de Renens et il est 14h. Trois guichets sont ouverts et deux personnes attendent dans la file. La machine à tickets indique que le prochain ticket délivré sera le 544.
file = [542, 543]
L’indice du dernier numéro (543) est [-1]. En ajoutant 1 à la valeur contenue dans file[-1], on trouve 544
Le prochain numéro sera donc
file[-1] + 1
544
Si une personne entre, elle prend son numéro et elle s’insére dans la liste d’attente.
suivant = file[-1] + 1
file.append(suivant)
La file d’attente comprend maintenant:
file
[542, 543, 544]
Ensuite deux personnes entrent.
file.append(file[-1] + 1)
file.append(file[-1] + 1)
file
[542, 543, 544, 545, 546]
Le guichet¶
Il y a trois guichets A, B, et C, qui vont se libérer de façon alétoire.
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')
'B'
Le prochain guichet qui se libère
random.choice('ABC')
'C'
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 A
Exercice¶
Traduisez en python les étapes suivantes :
Une femme entre dans la poste, elle va chercher son ticket.
Le guichet 1 et le guichet 3 se libèrent. Deux personnes de la file les occupent ensuite
Une femme suivie d’un homme pressé entrent dans la poste et vont chercher leurs ticket.
Le guichet 2 se libère
L’homme pressé quitte la poste, il en a marre d’attendre
Après les étapes, quel est l’état des de la file ? Quel est le prochain numéro délivré par la machine à tickets ?