Structure : la pile

Nous connaissons déjà les tableaux, qui permettent de stocker un nombre fixe de valeurs de même types. Dans ce chapitre, nous présentons la structure de pile, qui permet de stocker un nombre variable de valeurs de même type et d'y accéder selon un ordre précis. Cette structure sera également l'occasion de mettre en œuvre l'approche « type abstrait » présentée dans le chapitre précédent.

Principe

Une pile sert à stocker des valeurs de même type. Son nom vient de la manière particulière dont elle permet d'accéder aux valeurs qui y sont stockées. Prenons l'analogie avec une pile d'assiettes. On ne peut poser (ou empiler) une nouvelle assiette que sur le dessus (ou sommet) de la pile, et on ne peut retirer (ou dépiler) que l'assiette qui se trouve au sommet de la pile. Par ailleurs, si on suppose que chaque assiette a un motif dessiné en son centre (sa « valeur »), on ne peut voir que le motif de l'assiette du sommet.

Une pile peut bien sûr être vide (ne contenir aucune valeur), ce qui doit pouvoir être vérifié, car cela n'aurait pas de sens de consulter ou dépiler la valeur au sommet d'une pile vide. De la même manière, des contraintes techniques peuvent limiter le nombre d'éléments qu'une pile peut contenir. On souhaiterait donc pouvoir tester si une pile est pleine, c'est à dire s'il est impossible d'y empiler une nouvelle valeur. Enfin, il faut disposer d'une opération permettant d'initialiser une nouvelle pile ; la nouvelle pile sera vide.

Indication

En anglais, « pile » se traduit par « stack », mais on parle également parfois de LIFO pour « Last In, First Out » (dernier entré, premier sorti). Le sommet est appelé « top », et les opérations d'empilement et de dépilement sont généralement appelées « push » et « pop », respectivement.

Spécification

On spécifie ci-dessous une pile destinée à contenir des valeurs de type chaîne de caractères. Le type des valeurs n'a évidemment aucune incidence sur la spécification ou l'implémentation. Il serait tout à fait possible de définir une pile de n'importe quel autre type en remplaçant dans ce qui suit str par le nom de cet autre type.

######## Tpile : Spécification ########

def construit_pile():
    """
    :sortie p: Tpile
    :post-cond: p est une pile vide
    """

def pile_vide(p):
    """
    :entrée p: Tpile
    :sortie v: bool
    :post-cond: v est True si et seulement si p est vide
    """

def pile_pleine(p)
    """
    :entrée p: Tpile
    :sortie pp: bool
    :post-cond: pp est True si et seulement si p est pleine
    """

def empile(p, e)
    """
    :entrée e: str
    :entrée/sortie p: Tpile
    :pre-cond: p n'est pas pleine
    :post-cond: e est ajouté au sommet de p
    """

def sommet(p):
    """
    :entrée p: Tpile
    :sortie s: str
    :pre-cond: p n'est pas vide
    :post-cond: s est l'élément stocké au sommet de p
    """

def depile(p):
    """
    :entrée/sortie p: Tpile
    :pre-cond: p n'est pas vide
    :post-cond: l'élément stocké au sommet de p est retiré
    """

Implémentation

Le seul moyen dont nous disposons pour l'instant pour stocker plusieurs valeurs du même type est d'utiliser un tableau. Nous allons donc utiliser un champs de type tableau de chaînes pour implémenter notre type abstrait. La taille de ce tableau correspondra au nombre maximum d'éléments que notre pile pourra contenir ; cette valeur sera stockée comme une constante MAX (pour pouvoir être changée facilement). Enfin, une pile peut contenir à un moment donné moins d'éléments que sa contenance maximale : il faut donc un champs qui mémorise le nombre d'éléments stockés dans la pile, et donc le nombre de cases effectivement utilisés dans le tableau.

Reste à décider quelles cases du tableau utiliser. Supposons que la pile contienne n éléments : on choisit de les stocker dans les n premières cases du tableau, du plus ancien au plus récent. En effet, lorsqu'on ajoute un élément à la pile, il sera ajouté dans la n+1ème case, et il deviendra bien le plus récent. Inversement, lorsqu'on retire l'élément le plus récent, il reste n-1 éléments, et la n-1ème contient bien le prochain élément à sortir de la pile. Notons enfin que le nombre d'élément du tableau est l'indice du sommet plus un, car le tableau est indicé à partir de zéro.

######## Tpile : Implémentation n°1 ########

from algo import *
from numpy import *

MAX = 100

class Tpile(Struct):
    tab = ndarray  # tableau de MAX éléments
    isommet = int  # indice du sommet

def construit_pile():
    p = Tpile(tab=empty(MAX, "<U1000"), isommet=-1)
    return p

def pile_vide(p):
    v = (p.isommet == -1)
    return v

def pile_pleine(p):
    pp = (p.isommet == MAX-1)
    return pp

def empile(p, e):
    p.isommet = p.isommet + 1
    p.tav[p.isommet] = e

def sommet(p):
    s = p.tab[p.isommet]
    return s

def depile(p):
    p.isommet = p.isommet - 1

Toutes les opérations sur la pile s'exécutent en temps constant : elles ne dépendent pas du nombre d'éléments stocké dans la pile (ni de la capacité maximale de la pile). Cette implémentation est donc optimale en terme de complexité algorithmique.

On remarque que les procédures construit_pile et depile ne modifient pas le contenu du tableau. Le contenu des cases d'indicie supérieur à p.isommet ne sera en effet jamais utilisé, on peut donc les laisser en l'état sans aucun impact pour le fonctionnement de la pile.

NB: Une autre implémentation de la pile sera proposées dans le chapitre Liste chaînée.

Application : texte bien parenthésé

Les piles sont utilisées dans de nombreuses situations en informatique. Nous étudions ici un exemple d'analyseur syntaxique simple, vérifiant si un texte est correctement parenthésé.

Considérons une chaîne de caractères contenant un texte. Ce texte contient des parenthèses rondes (« ( » et « ) ») et carrées (« [ » et « ] »). À chaque parenthèse ouvrante doit correspondre une parenthèse fermante du même type, et réciproquement. Par ailleurs, si une parenthèse ouvrante est ouverte à l'intérieur d'un autre couple de parenthèses, sa parenthèse fermante doit elle aussi de trouver à l'intérieur du même couple.

Le tableau ci-dessous donne des exemples de textes bien et mal parenthésés.

Bien parenthésés	Mal parenthésés
abc	(
(abc)	abc)
ab[cd]ef	ab)c
a[b]c(d)e	a(b]c
a((b)c)d	a(b(c)d
a(b[c()e]f)g	a(b[c)d]e

La spécification de l'algorithme est donc la suivante :

def bien_parenthese(txt):
    """
    :entrée txt: str
    :sortie bp: bool
    :post-cond: bp est True si et seulement si txt est bien parenthésé
    """

D'après la définition d'un texte bien parenthésé, une condition nécessaire est qu'il contienne autant de « ( » que de « ) », et autant de « [ » que de « ] ». Cependant, cette condition n'est pas suffisante, comme l'illustre le dernier exemple de texte mal parenthésé dans le tableau ci-dessus. Ceci est dû au fait que la dernière condition n'est pas vérifiée par cet exemple. L'ordre dans lequel on rencontre les parenthèses fermantes doit correspondre à l'ordre dans lequel on a rencontré les parenthèses ouvrantes.

En fait, le type (rond ou carré) d'une parenthèse fermante doit toujours correspondre au type de la dernière parenthèse ouvrante rencontrée (et non encore fermée). On décide donc de stocker dans une pile les types des parenthèses ouvrante rencontrées. Lorsqu'on rencontre une parenthèse fermante, il faut s'assurer qu'il reste dans la pile une parenthèse ouvrante à fermer, et que son type correspond à celui de la parenthèse fermante. Si ces conditions sont vérifiées, la parenthèse ouvrante est retirée de la pile (puisqu'elle vient d'être fermée), sinon le texte est mal parenthésé et on peut interrompre le traitement. Arrivé à la fin du texte, il faut également vérifier qu'aucune parenthèse ne demeure ouverte dans la pile. On supposera que le nombre de parenthèses ouvertes simultanément n'excède jamais la capacité de la pile.

def bien_parenthese(txt):
    bp = True
    p = construit_pile()
    i = 0
    while bp and i < len(txt):
        if txt[i] == "("  or  txt[i] == "[":
            empile(p, txt[i])
        elif txt[i] == ")":
            if sommet(p) != "(":
                bp = False
            else:
                depile(p)
        elif txt[i] == "]":
            if sommet(p) != "[":
                bp = False
            else:
                depile(p)
        i = i+1
     if not pile_vide(p):
         bp = False
     return bp