Prépa Code Connexion Inscription

On souhaite implementer une pile qui supporte, en plus des operations classiques, une operation minimum renvoyant le plus petit element actuellement dans la pile, avec une complexite en temps constante.

Ecrire une fonction min_pile_ops(operations) qui prend une liste d'operations et renvoie la liste des resultats produits par les operations depiler et minimum. L'operation empiler ne produit rien.

Chaque operation est un tuple : - ("empiler", valeur) : empile valeur sur la pile. - ("depiler",) : retire et renvoie le sommet de la pile. - ("minimum",) : renvoie le minimum de la pile sans la modifier.

On garantit qu'aucun depiler ou minimum n'est appele sur une pile vide.

Remarque : une structure naive (parcours complet pour trouver le min) fonctionne mais n'est pas en O(1). Cherchez une astuce avec une seconde pile qui suit les minima successifs.