Structures de données : listes, piles, files

Structures de données : listes, piles, files

Une structure de données est une manière d'organiser des valeurs en mémoire, associée à un ensemble d'opérations et à leurs coûts. Choisir la bonne structure, c'est choisir quelles opérations seront rapides. En NSI, on distingue l'interface (les opérations promises) de l'implémentation (la façon dont elles sont réalisées) : c'est le principe d'abstraction.

I. Le tableau dynamique (liste Python)

La liste Python est un tableau redimensionnable : les éléments sont contigus en mémoire, donc l'accès par indice est immédiat.

Opération	Coût
t[i] (lecture/écriture)	O(1)
t.append(x)	O(1) amorti
t.pop()	O(1)
t.insert(0, x)	O(n)
x in t	O(n)

L'insertion en tête est coûteuse car elle décale tous les éléments suivants.

II. La liste chaînée

Chaque maillon contient une valeur et une référence vers le suivant. L'insertion en tête est en O(1), mais l'accès au i-ème élément exige de parcourir la chaîne : O(n).

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(tete):
    n, m = 0, tete
    while m is not None:
        n += 1
        m = m.suivant
    return n

Comparaison : tableau = accès rapide, insertion interne lente ; liste chaînée = insertion rapide en tête, accès lent. Il n'existe pas de structure universellement meilleure.

III. La pile (LIFO)

Dernier entré, premier sorti. Opérations : empiler(x), depiler(), est_vide(), sommet(), toutes en O(1).

class Pile:
    def __init__(self):
        self._t = []
    def est_vide(self):
        return len(self._t) == 0
    def empiler(self, x):
        self._t.append(x)
    def depiler(self):
        if self.est_vide():
            raise IndexError("pile vide")
        return self._t.pop()

Applications : annulation (Ctrl+Z), pile d'appels d'un programme récursif, évaluation d'expressions postfixées, retour arrière dans un navigateur.

Exemple classique — parenthésage bien formé :

def bien_parenthesee(ch):
    p = Pile()
    paires = {')': '(', ']': '[', '}': '{'}
    for c in ch:
        if c in "([{":
            p.empiler(c)
        elif c in paires:
            if p.est_vide() or p.depiler() != paires[c]:
                return False
    return p.est_vide()

IV. La file (FIFO)

Premier entré, premier sorti. Opérations : enfiler(x), defiler(), est_vide().

Une implémentation naïve avec list.pop(0) coûte O(n) par défilement. On utilise donc soit collections.deque (O(1) aux deux extrémités), soit deux piles : on empile dans la pile d'entrée, et quand la pile de sortie est vide, on y transvase tout — coût amorti O(1).

Applications : file d'impression, tampon de messages, ordonnancement de tâches, parcours en largeur d'un graphe (BFS), tandis que la pile sert au parcours en profondeur (DFS).

V. Choisir sa structure

1. Accès direct par indice fréquent → tableau.
2. Insertions/suppressions en tête nombreuses → liste chaînée.
3. Dernier arrivé traité en premier → pile.
4. Traitement dans l'ordre d'arrivée, équité → file.

Toujours vérifier le cas limite : que fait la structure vide ? Une bonne implémentation lève une exception explicite plutôt que de renvoyer une valeur silencieusement fausse.

À retenir

• Interface ≠ implémentation : la même pile peut reposer sur un tableau ou une liste chaînée.
• Tableau : accès O(1), insertion interne O(n). Liste chaînée : l'inverse.
• Pile = LIFO (parenthésage, récursivité, DFS) ; file = FIFO (tampon, BFS).
• Une file efficace se code avec deque ou deux piles, jamais avec pop(0).