Tableau associatif : implémenter un cache LRU

Un cache LRU (Least Recently Used) stocke les $k$ éléments les plus récemment utilisés.

Implémenter une classe CacheLRU avec :

• __init__(self, capacite) : initialise le cache de capacité donnée
• get(self, clé) : renvoie la valeur si présente, None sinon
• put(self, clé, valeur) : insère ou met à jour une entrée. Si le cache est plein, supprime l'entrée la moins récemment utilisée.

Les opérations get et put doivent être en $O(1)$.