Pile (Stack)
La pile (stack) est l’une des structures de données les plus utilisées dans les algorithmes. Lorsqu’on emploie une pile, les derniers éléments ajoutés sont les premiers à être retirés. C’est comme une pile d’assiettes : tant qu’on n’a pas enlevé l’assiette du dessus, on ne peut pas accéder à celles qui se trouvent en dessous.
Une pile peut servir dans de nombreuses situations concrètes. Par exemple, dans un navigateur web, vous pouvez cliquer sur le bouton « Retour » pour revenir à la page précédente. L’historique des pages peut être stocké dans une pile et, dès que vous appuyez sur « Retour », vous accédez à l’élément qui est au sommet de cette pile. Si vous cliquez à nouveau sur « Retour », l’élément du haut de la pile est retiré et vous retournez ainsi sur le suivant.
Il existe plusieurs manières d’implémenter une pile dans un langage de programmation comme Python :
- En utilisant
list– l’élément du haut de la pile sera le dernier élément de la liste. Nous pouvons l’ajouter avecappend, le retirer avecpopet l’obtenir grâce à[-1].
- En utilisant
dequedepuiscollections– cette structure permet d’ajouter et de retirer des éléments aussi bien au début qu’à la fin.
LifoQueuedepuisqueue– il s’agit d’une file d’attente LIFO (Last-in-first-out), ce qui correspond précisément à la définition d’une pile.
from queue import LifoQueue
stack = LifoQueue()
# push
stack.put(1)
stack.put(2)
stack.put(3)
# pop
print(stack.get()) # affiche 3
print(stack.get()) # affiche 2
# peek
print(stack.queue[-1]) # affiche 1
print(stack.empty()) # vérifie si elle est vide -> affiche False# En utilisant une simple list
stack = []
# push
stack.append(1)
stack.append(2)
stack.append(3)
# pop
print(stack.pop()) # affiche 3
print(stack.pop()) # affiche 2
# peek
print(stack[-1]) # affiche 1
print(len(stack) == 0) # vérifie si elle est vide -> affiche FalseDéfi : Vérifier si la séquence de parenthèses est valide
Étant donné une séquence de parenthèses d’une expression mathématique (par exemple
(()())), vous devez vérifier si cette séquence est valide. Une séquence de parenthèses est considérée valide si chaque parenthèse ouvrante a sa parenthèse fermante correspondante et qu’il n’y a pas de parenthèses en trop (ni ouvrantes ni fermantes).Entrée
La seule ligne d’entrée contient une unique ligne
b (1 ≤ |b| ≤ ) contenant la séquence de parenthèses.Sortie
Le programme doit afficher
Yes si la séquence de parenthèses est valide, et No sinon.Exemples
Entrée | Sortie |
()() | Yes |
())()( | No |
((()())()) | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB