Piles

Une pile expose en premier l’élément ajouté le plus récemment : dernier entré, premier sorti. Ses opérations minimales sont push, pop, peek et un test de vacuité.

stack: list[str] = []
stack.append("first")
stack.append("second")
top = stack[-1]
removed = stack.pop()

Employer la fin d’un tableau dynamique donne un empilement et un dépilement amortis en $O(1)$, et une consultation en $O(1)$. Une implémentation chaînée peut assurer des mises à jour d’extrémité en $O(1)$ dans le pire cas, mais ajoute une allocation et un lien par élément.

Invariant

Seul le sommet peut être retiré directement. Restreindre l’accès exprime le travail inachevé : le sommet représente souvent le dernier délimiteur ouvert, l’état de recherche actif, l’opérateur en attente ou l’action annulable.

Usages courants

• parcours en profondeur itératif et backtracking ;
• analyse d’expressions et appariement de délimiteurs ;
• historiques d’annulation et portées imbriquées ;
• simulation de la récursion lorsqu’un contrôle explicite de l’état est utile.

La pile d’appels du moteur d’exécution est apparentée, mais stocke aussi des adresses de retour, des variables locales et des métadonnées d’exécution ; ce n’est pas seulement une pile de valeurs au niveau utilisateur.

Échecs et capacité

Dépiler une pile vide est un sous-dépassement dont le contrat doit être explicite. Une pile bornée peut aussi déborder ; une implémentation dynamique rencontre plutôt un échec d’allocation ou une limite de politique.

N’utilisez pas l’insertion et la suppression au début d’un tableau dynamique pour modéliser une pile : cela ajoute des décalages inutiles.

Exemple : délimiteurs imbriqués

def balanced(text: str) -> bool:
    opening: list[str] = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in text:
        if char in "([{":
            opening.append(char)
        elif char in pairs:
            if not opening or opening.pop() != pairs[char]:
                return False
    return not opening

assert balanced("a * (b + [c])")
assert balanced("")
assert not balanced("([)]")
assert not balanced(")(")
assert not balanced("((")

Après chaque caractère accepté, la pile contient exactement les délimiteurs ouvrants non appariés, dans leur ordre d’apparition. Un délimiteur fermant doit correspondre au sommet, pas simplement à une ouverture antérieure : ([)] présente des comptes égaux, mais des imbrications croisées. Une pile vide à la fin signifie qu’aucune ouverture ne reste inachevée. Pour $n$ caractères, le temps est en $O(n)$ et l’espace supplémentaire en $O(d)$, où $d$ est la profondeur maximale d’imbrication.

Ce code vérifie uniquement l’imbrication. Il ignore les autres caractères mais ne comprend ni chaînes entre guillemets ni commentaires : ce n’est pas un analyseur de langage. Dans le premier extrait, top et removed valent tous deux "second" et la pile restante vaut ["first"]. Sur une liste Python vide, stack[-1] et stack.pop() lèvent IndexError.

Avec une politique adaptée de croissance et de réduction, le tableau dynamique offre un dépilement amorti en $O(1)$, et non toujours en $O(1)$ dans le pire cas ; consulter le sommet reste en $O(1)$. Les bornes des extrémités chaînées comptent les modifications de liens, sans garantir un temps d’allocation réel constant.

Source

• Open Data Structures : interface de pile

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.