Pile (informatique)
Un article de Wikipédia, l'encyclopédie libre.
En informatique, une pile (en anglais stack) est une structure de données basée sur le principe « dernier arrivé, premier sorti » (ou LIFO pour Last In, First Out), ce qui veut dire que les derniers éléments ajoutés à la pile seront les premiers à être récupérés. Le fonctionnement est celui d'une pile d'assiettes : on ajoute des assiettes sur la pile, et on les récupère dans l'ordre inverse, en commençant par la dernière ajoutée.
Sommaire |
[modifier] Pile d'appel
La pile d'appel (souvent appelée « la pile » tout court, parfois « pile système ») est, sur la plupart des architectures de microprocesseurs, une pile particulière dans laquelle sont poussés tout ou partie des paramètres d'appel des procédures ou fonctions, ainsi que l'adresse de retour. Par ailleurs, on y crée un espace pour des variables locales. La pile est ainsi formée de cadres de piles (stack frames) comprenant pour chaque procédure en cours d'appel imbriqué ses paramètres, ses variables locales et son point de retour. La pile système sert à sauver le contexte (valeur des registres, point de retour...) lors des exceptions et des interruptions. Devant pouvoir être lue comme écrite, la pile se trouve donc en RAM.
[modifier] Primitives
Voici les primitives communément utilisées pour manipuler des piles. Il n'existe pas de normalisation pour les primitives de manipulation de pile. Leurs noms sont donc indiqués de manière informelle.
- « Empiler » : ajoute un élément sur la pile. Terme anglais correspondant : « Push ».
- « Dépiler » : enlève un élément de la pile et le renvoie. Terme anglais correspondant : « Pop ».
- « La pile est-elle vide ? » : renvoie vrai si la pile est vide, faux sinon.
- « Nombre d'éléments de la pile » : renvoie le nombre d'éléments dans la pile.
[modifier] Algorithme
Procédure PUSH (objet : o) //ajouter un élément sur la pile
Début
Si sommet < max Alors
Tpile[sommet++] <- o
Sinon
Afficher "Pile pleine"
Fin Si
Fin
Fonction POP () : objet //enlever un élément de la pile et le renvoyer
objet : o
Début
Si non vide() Alors
0 <- Tpile[sommet]
Sommet <- Sommet - 1
Sinon
Afficher "Pile vide"
Finsi
Retourner o
Fin
[modifier] Architecture basée sur la pile
Certains processeurs n'utilisent pas de registre générique, mais uniquement la pile. Par exemple, les calculatrices Hewlett-Packard, les processeurs Focus, ou les machines Burroughs de la gamme B 5000
[modifier] Aspect mathématique
En matière de structures abstraites, on peut considérer qu'une pile est un monoïde libre, c’est-à-dire un ensemble muni d'une loi de composition interne (la concaténation) associative et possédant un élément neutre.
[modifier] Applications
- Dans un navigateur web, une pile sert à mémoriser les pages Web visitées. L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile l'adresse de la page précédente en cliquant le bouton « Afficher la page précédente ».
- L'évaluation des expressions mathématiques en notation post-fixée (ou polonaise inverse) utilise une pile.
- La fonction « Annuler la frappe » (en anglais Undo) d'un traitement de texte mémorise les modifications apportées au texte dans une pile.
- Un algorithme de recherche en profondeur utilise une pile pour mémoriser les nœuds visités.
- Par exemple, on peut très simplement inverser les éléments contenus dans un tableau ou dans une chaîne de caractères (pour tester un palindrome) en utilisant une pile. Il suffit d'empiler les éléments sur une pile puis de reconstituer le tableau (ou la chaîne) inverse en dépilant les éléments.
- Les algorithmes récursifs admis par certains langages (LISP, Algol, Pascal, C, etc.) utilisent implicitement une pile d'appel. Dans un langage non récursif (FORTRAN par exemple), on peut donc toujours simuler la récursion en créant les primitives de gestion d'une pile.
