I. Structure de données abstraite

Une structure de données est un objet informatique permettant de stocker une collection d'objets. Vous en connaissez déjà deux : les listes et les dictionnaires.

On distingue la structure de données de son implémentation : lorsque vous utilisez une liste ou un dictionnaire en Python, vous utilisez par exemple la méthode .append(...), ou bien l'opérateur d[obj]. En revanche, vous ne vous intéressez pas à ce qu'il se passe, concrètement, quand vous les utilisez : ils fonctionnent et c'est ce qui compte.

Dans ce cas, vous utilisez la structure de données, sans vous soucier de son implémentation.

Par exemple, on peut définir la liste comme une collection d'éléments munie des opérations suivantes :

• accéder et modifier un élément par son indice ;
• ajouter un élément à la fin ;
• retirer un élément à la fin ;
• connaître la longueur de la liste.

De même, on peut définir le dictionnaire comme une collection d'éléments munie des opérations suivantes :

• accéder, modifier ou insérer une valeur par sa clé ;
• itérer sur toutes les clés ;
• connaître le nombre d'éléments dans le dictionnaire.

Le code suivant mesure le temps pris pour ajouter un élément à 10000 listes, en fonction de leur taille : il reste à peu près constant.

import matplotlib.pyplot as plt
from time import time

L = [[] for i in range(10000)]
t = []
for i in range(500):
    t1 = time()
    for l in L:
        l.append(i)
    t2 = time()
    t.append(t2 - t1)
plt.plot(L[0], t)
plt.show()

II. Pile

Image : une pile d'assiettes. On peut en poser une par-dessus, ou enlever celle du dessus, mais c'est tout !

Pour implémenter une pile de manière efficace, on peut simplement utiliser... une liste ! Avec la correspondance suivante :

• empiler : P.append(...) en ;
• dépiler : P.pop() en ;
• regarder l'élément en haut de la pile : P[-1] en ;
• connaître la hauteur de la pile : len(P) en .

Vous pouvez manipuler une pile ci-dessous :

III. File

Image : une file d'attente. On peut ajouter un élément à la fin de la file, et enlever un élément au début de la file (mais on ne double pas !).

On peut à nouveau utiliser les listes pour implémenter une file, mais ça ne sera pas très efficace...

• enfiler : F.append(...) en ;
• défiler : F.pop(0) en (!) ;
• regarder l'élément au début de la file : F[0] en ;
• connaître la taille de la file : len(F) en .

Il est possible d'implémenter une file avec toutes ses opérations en . C'est par exemple le cas de la structure deque de Python (si on attend que vous utilisiez deque, tout vous sera rappelé dans le sujet) :

from collections import deque

file = deque()
print(file)
for i in range(10):
    file.append(i)
print(file)
file.popleft()
print(file)
file.appendleft(10)
print(file)

IV. File de priorité

Image : l'attente à l'hôpital, où le plus urgent est traité en premier.

Dans cette collection, on va associer à chaque élément une priorité (en général un nombre).

Il y a deux implémentations "naïves" de files de priorité au programme :

• la liste non triée :
  • ajouter : append, en ;
  • supprimer : chercher l'élément de priorité maximale dans la liste, le supprimer, en ;
  • regarder l'élément de priorité maximale : le chercher, en ;
• la liste triée, où on maintient toujours les éléments triés par ordre de priorité croissant :
  • ajouter : insérer l'élément à sa place dans la liste, en ;
  • supprimer : .pop(), en ;
  • regarder l'élément de priorité maximale : en .

En pratique, ce ne sont pas de très bonnes implémentations, mais on s'en contentera.

Il peut être utile de savoir qu'il est possible d'implémenter une file de priorité avec toutes les opérations en (les options verront comment !).

On utilisera ces structures dans le chapitre suivant, pour parcourir des graphes : les parcours en profondeur utilisent une pile, les parcours en largeur une file, et l'algorithme de Dijkstra une file de priorité.