Livre_silo 30 août 2013 16:32 Page 300
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
300
Informatique pour tous
Dans ce chapitre, on présente la structure de pile. Elle correspond exactement à l’image
traditionnelle d’une pile de cartes ou d’assiettes posée sur une table. En particulier, on ne
peut accéder qu’au dernier élément ajouté, qu’on appelle le sommet de la pile. Ainsi, si on
a ajouté successivement A, puis B, puis C dans une pile, on se retrouve dans la situation
suivante :
↓ ↑
C
B
A
C est empilé sur B, lui-même empilé sur A. On peut soit retirer C de la pile (on dit qu’on
« dépile » C), soit ajouter un quatrième élément D (on dit qu’on « empile » D). Si on veut
accéder à l’élément A, il faut commencer par dépiler C, puis B. L’image associée à une
pile est donc « dernier arrivé, premier sorti » (en anglais last in, first out, parfois abrégé en
LIFO).
POUR ALLER PLUS LOIN Structure de file
On peut bien évidemment aussi imaginer une structure où, comme dans une file d’attente,
les éléments sortent dans leur ordre d’arrivée, le premier élément sorti correspondant à
l’élément le plus anciennement arrivé (en anglais first in, first out, parfois abrégé en FIFO).
On parle alors de structure de file. De mise en œuvre légèrement plus délicate que celle
de la structure de pile présentée dans ce chapitre, la structure de file ne figure pas au
programme.
12.1 Opérations caractérisant une structure de pile
Avant de se pencher sur les différentes façons de réaliser une structure de pile, il faut définir
l’ensemble des opérations qu’une telle réalisation doit pouvoir fournir, quelle qu’elle soit.
Les trois opérations principales sont réalisées par les fonctions creer_pile, depiler et empiler.
• creer_pile(c) renvoie une nouvelle pile de capacité c, initialement vide.
• depiler(p) dépile et renvoie le sommet de la pile p.
• empiler(p, v) empile la valeur v sur la pile p.
Les opérations depiler et empiler modifient le contenu de la pile passée en argument. Voici
une illustration de l’utilisation de ces trois opérations :
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
300
Informatique pour tous
Dans ce chapitre, on présente la structure de pile. Elle correspond exactement à l’image
traditionnelle d’une pile de cartes ou d’assiettes posée sur une table. En particulier, on ne
peut accéder qu’au dernier élément ajouté, qu’on appelle le sommet de la pile. Ainsi, si on
a ajouté successivement A, puis B, puis C dans une pile, on se retrouve dans la situation
suivante :
↓ ↑
C
B
A
C est empilé sur B, lui-même empilé sur A. On peut soit retirer C de la pile (on dit qu’on
« dépile » C), soit ajouter un quatrième élément D (on dit qu’on « empile » D). Si on veut
accéder à l’élément A, il faut commencer par dépiler C, puis B. L’image associée à une
pile est donc « dernier arrivé, premier sorti » (en anglais last in, first out, parfois abrégé en
LIFO).
POUR ALLER PLUS LOIN Structure de file
On peut bien évidemment aussi imaginer une structure où, comme dans une file d’attente,
les éléments sortent dans leur ordre d’arrivée, le premier élément sorti correspondant à
l’élément le plus anciennement arrivé (en anglais first in, first out, parfois abrégé en FIFO).
On parle alors de structure de file. De mise en œuvre légèrement plus délicate que celle
de la structure de pile présentée dans ce chapitre, la structure de file ne figure pas au
programme.
12.1 Opérations caractérisant une structure de pile
Avant de se pencher sur les différentes façons de réaliser une structure de pile, il faut définir
l’ensemble des opérations qu’une telle réalisation doit pouvoir fournir, quelle qu’elle soit.
Les trois opérations principales sont réalisées par les fonctions creer_pile, depiler et empiler.
• creer_pile(c) renvoie une nouvelle pile de capacité c, initialement vide.
• depiler(p) dépile et renvoie le sommet de la pile p.
• empiler(p, v) empile la valeur v sur la pile p.
Les opérations depiler et empiler modifient le contenu de la pile passée en argument. Voici
une illustration de l’utilisation de ces trois opérations :