Table des matières

• Introduction
• Définition de la pile
• Type de données abstrait de la pile
• Implémentation par tableau séquentiel
• Implémentation par liste chaînée
• Conclusion

Introduction

La pile est une structure de données linéaire où les opérations d'insertion et de suppression sont limitées à une seule extrémité. La file, quant à elle, permet l'insertion à une extrémité et la suppression à l'autre.

Définition de la pile

Une structure de données où les éléments entrent en dernier et sortent en premier — voilà ce qu'est une pile.

Dans les applications logicielles, cette caractéristique dernier entré, premier sorti (LIFO) est très répandue. Lorsque vous naviguez sur Internet avec un navigateur, le bouton « Retour » permet de revenir aux pages visitées précédemment dans l'ordre inverse. Vous pouvez ainsi revenir en arrière après avoir suivi plusieurs liens, exactement comme une machine à remonter le temps.

De nombreux logiciels comme les traitements de texte ou les éditeurs d'images implémentent la fnoction d'annulation (undo) en utilisant ce principe de pile. Bien que les implémentations具体代码 diffèrent selon les logiciels, le concept reste le même.

Une pile (stack) est une structure de données linéaire où les opérations d'insertion et de suppression sont effectuées uniquement à une extrémité appelée le sommet.

L'extrémité où s'effectuent les insertions et suppressions est appelée le sommet (top), tandis que l'autre extrémité est la base (bottom). Une pile sans aucun élément est appelée pile vide. La pile遵循 le principe Last In First Out (LIFO).

Points importants à retenir :

Premièrement, la pile est une structure linéaire avec des relations de prédécesseur-succèsseur entre ses éléments. Deuxièmement, l'insertion et la suppression s'effectuent au niveau du sommet, et non à la base. Troisièmement, la base reste fixe — le premier élément inséré se retrouve à la base de la pile.

L'opération d'insertion s'appelle l'empilement (push), analogue aux munitions dans un chargeur.

L'opération de suppression s'applele le désempilement (pop), comme les balles sortant d'un chargeur.

Type de données abstrait de la pile

Bien que la pile hérite des propriétés d'une structure linéaire, certaines opérations sont renommées pour plus de clarté. L'insertion devient empiler et la suppression devient désempiler.

Comme la pile est elle-même une structure linéaire, elle peut être implémentée soit par un tableau, soit par une liste chaînée.

ADT Pile (Stack)
Data
    Les éléments sont de type identique. Les éléments adjacents ont une relation de prédécesseur-succèsseur.
Opérations
    InitialiserPile(*p) : Crée et initialise une pile vide.
    DetruirePile(*p) : Détruit la pile si elle existe.
    ViderPile(*p) : Retire tous les éléments de la pile.
    PileVide(p) : Retourne vrai si la pile est vide, faux sinon.
    SommetPile(p, *e) : Retourne l'élément au sommet sans le supprimer.
    Empiler(*p, e) : Insère un nouvel élément e au sommet de la pile.
    Desempiler(*p, *e) : Retire l'élément au sommet et le retourne dans e.
    TaillePile(p) : Retourne le nombre d'éléments dans la pile.
FinADT

Implémentation par tableau séquentiel

La pile étant un cas particulier de structure linéaire, son implémentation par tableau dérive directement de celle des tableaux linéaires, simplifiée pour ce cas d'usage.

Quelle extrémité du tableau utiliser comme sommet et base ? L'extrémité d'indice 0 est préférable pour la base, car cet élément change rarement. Un indicateur sommet permet de suivre la position du dernier élément inséré. Cet indicateur peut varier, mais il ne doit jamais dépasser la taille maximale du tableau. Si la capacité maximale est CAPACITE_MAX, alors le sommet doit être strictement inférieur à cette valeur. Lorsque la pile contient un élément, sommet vaut 0. Par convention, une pile vide correspond à sommet égal à -1.

Définition de la structure :

typedef int TypeElement; /* TypeElement dépend du contexte */

typedef struct {
    TypeElement donnees[CAPACITE_MAX];
    int sommet; /* Indice de l'élément au sommet */
} PileTableau;

Avec une capacité de 5 éléments, les états possibles sont : pile normale, pile vide, et pile pleine.

Implémentation par liste chaînée

Examinons maintenant l'implémentation par liste chaînée, appelée pile chaînée. Puisque les opérations s'effectuent uniquement au sommet, celui-ci peut être placé au début de la liste. Un seul pointeur suffira : celui vers le sommet.

La liste chaînée ne présente généralement pas de problème de capacité maximale, sauf en cas d'épuisement total de la mémoire, situation qui provoque alors un crash du système d'exploitation. Pour une pile vide, le pointeur vers le sommet vaut NULL.

Structure de la pile chaînée :

typedef struct NoeudPile {
    TypeElement donnee;
    struct NoeudPile *suivant;
} NoeudPile, *PointeurPile;

typedef struct {
    PointeurPile sommet;
    int nombreElements;
} PileChainee;

Les opérations sur la pile chaînée ressemblent fortement à celles d'une liste chaînée simple, à l'exception près que les insertions et suppressions s'effectuent exclusivement au niveau du premier nœud.

Conclusion

Certains pourraient se demander pourquoi introduire une structure de pile alors que les tableaux ou listes chaînées suffisent largement. La réponse est analogue à celle concernant les moyens de transport : bien que marcher soit possible partout, les véhicules permettent d'atteindre destination plus efficacement.

L'utilisation de la pile simplifie le problème en définissant clairement le niveau d'abstraction. Elle permet de se concentrer sur l'essence du problème plutôt que sur les détails d'implémentation comme la gestion des indices. Les langages modernes comme Java ou C# proposent des classes de pile prédéfinies, rendant son utilisation transparente.