Piles, files et listes

Une pile et une file rangent des éléments les uns à la suite des autres. Ce qui les distingue, c'est l'élément que l'on retire :

• Pile (comme une pile d'assiettes) : on empile au sommet et on dépile le sommet. Le dernier entré est le premier sorti (mode LIFO, de l'anglais last in, first out).
• File (comme une file d'attente) : on enfile en queue et on défile la tête. Le premier entré est le premier sorti (mode FIFO, first in, first out).

Une liste Python peut jouer les deux rôles. En pile : append empile, pop() dépile le dernier élément.

pile = []
pile.append(3)
pile.append(7)
pile.append(5)
print(pile.pop())
print(pile)
print(len(pile) == 0)

5
[3, 7]
False

En file : append enfile en queue, pop(0) défile le premier élément.

file = []
file.append(3)
file.append(7)
file.append(5)
print(file.pop(0))
print(file)

3
[7, 5]

Tester si la structure est vide avant de retirer un élément : len(pile) == 0. Retirer d'une pile vide provoque une erreur :

pile = []
print(pile.pop())

IndexError: pop from empty list

Liste. Une liste se décrit par sa tête (le premier élément) et sa queue (la liste des éléments suivants). Pour savoir si une valeur y figure, il faut la parcourir : la recherche est linéaire.

Dictionnaire. Il associe des valeurs à des clés : on lit une valeur directement par sa clé, sans parcourir les éléments.

ages = {"Alice": 16, "Bilal": 17, "Chloé": 16}
print(ages["Bilal"])
print("Emma" in ages)

17
False

Choisir la structure. Annuler la dernière action (bouton « Annuler », retour arrière d'un navigateur) : une pile. Traiter des demandes dans leur ordre d'arrivée (impressions, clients au guichet) : une file. Retrouver une information par un identifiant : un dictionnaire.

Énoncé. La liste s est utilisée comme une pile. Quel nombre ce programme affiche-t-il ?

s = []
s.append(12)
s.append(4)
s.append(9)
x = s.pop()
s.append(20)
x = s.pop()
x = s.pop()
print(x)

Méthode : écrire le contenu de s après chaque instruction.

4

Même suite en file, avec pop(0) : les retraits donnent 12, puis 4, puis 9.

s = []
s.append(12)
s.append(4)
s.append(9)
x = s.pop(0)
s.append(20)
x = s.pop(0)
x = s.pop(0)
print(x)

9