Pile (informatique)

Pile (informatique)
Page d'aide sur l'homonymie Pour les articles homonymes, voir pile.
Une pile est gérée en Last in, first out.

En informatique, une pile (en anglais stack) est une structure de données fondé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

Pile système

La plupart des microprocesseurs gèrent nativement une pile. Elle correspond alors à une zone de la mémoire, et le processeur retient l'adresse du dernier élément.

Architecture x86

Dans l'architecture x86 32bits, le registre ESP sert à indiquer l'adresse du sommet d'une pile dans la RAM. Les opcodes "push" et "pop" permettent respectivement d'empiler et de dépiler des données. Les opcodes "call" et "ret" utilisent la pile pour appeler une fonction et la quitter par la suite en retournant à l'instruction suivant immédiatement l'appel.

En cas d'interruption, les registres EFLAGS, CS et EIP sont automatiquement empilés. Dans le cas d'un changement de niveau de priorité lors de l'interruption, les registres SS et ESP le sont aussi.

Architecture basée sur la pile

Certains processeurs n'utilisent pas de registre générique, mais uniquement la pile. Les instructions concernent alors ses premiers éléments. Par exemple, les calculatrices Hewlett-Packard, les processeurs Focus, ou les machines Burroughs de la gamme B 5000. Les instructions sont alors souvent plus courtes, car elles n'ont pas à référencer des registres[1]. Le bytecode du langage Java utilise aussi cette astuce.

Langage de programmation

Dans la plupart des langages de programmation compilés, la pile est l'endroit où sont poussés tout ou partie des paramètres d'appel des procédures ou fonctions. 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.

Primitives

PrimitivesPile.png

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.

Algorithme

Classe Pile
Attributs :
    pile   : tableau[1, MAX] de Objet
    sommet : entier {indice du dernier element entre}
Methodes
    Mprocédure PUSH(element)            {entre un element (Objet)}
    Mfonction  POP() retourne Objet     {sort un Objet} 
    {non données ici}
    Mfonction  FULL() retourne booleen  {la pile est-elle pleine ? (retourne sommet >= MAX)}
    Mfonction  EMPTY() retourne booleen {la pile est-elle vide ? (retourne sommet <= 0)}
    Mfonction  SIZE() retourne entier   {retourne le nombre d'elements (retourne sommet)}
    Mprocedure INIT()                   {constructeur (met sommet à 0)}
Mprocédure PUSH (element)
{ajouter un élément sur la pile}
Paramètres :
   (D)   element : Objet
   (D/R) cible   : Pile
Début
   Si cible.sommet <= MAX
   Alors
      cible.sommet <- cible.sommet + 1
      cible.pile[cible.sommet] <- element
   Sinon
      afficher("Pile pleine")
   Fsi
Fin 
Mfonction POP () retourne objet
{enlever un élément de la pile et le renvoyer}
Paramètres :
   (D/R) cible : Pile
Variables :
   Element : objet
Début
   Si cible.sommet > 0
   Alors
      Element <- cible.pile[cible.sommet]
      cible.sommet <- cible.sommet - 1
   Sinon
      afficher("Pile vide")
   Fsi
   Retourner Element
Fin 


Cette implémentation est celle utilisée dans les processeurs — elle est simple et la pile occupe peu de place. Une implémentation sous forme de liste chaînée est également possible pour des programmes.


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.

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écursivité en créant les primitives de gestion d'une pile.

Voir aussi

Articles connexes

Références

  1. Philip Koopman, Stack Computers, 1989

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Pile (informatique) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • pile — ● n. f. ►TYPE Structure de données classique où les premières données qu on y met sont les dernières à en ressortir. Tout à fait analogue à une pile d assiettes normalement constituée (et utilisée par quelqu un n ayant pas envie de tout… …   Dictionnaire d'informatique francophone

  • Pile d'appel — Pile d exécution En informatique, la pile d exécution (souvent abbréviée en la pile ; en anglais, call stack) est une structure de données de type pile qui sert à enregistrer des informations au sujet des fonctions actives dans un programme… …   Wikipédia en Français

  • INFORMATIQUE - Principes — Le traitement de l’information, au sens large, forme une part importante de l’activité humaine et elle est aussi ancienne que l’homme lui même. L’analyse de cette activité, qui est l’objet de l’informatique, a conduit à distinguer la manipulation …   Encyclopédie Universelle

  • Pile de protocoles — 7.  Application 6.  Présentation 5.  Session 4.  …   Wikipédia en Français

  • Pile d'exécution — En informatique, la pile d exécution (souvent abbréviée en la pile ; en anglais, call stack) est une structure de données de type pile qui sert à enregistrer des informations au sujet des fonctions actives dans un programme informatique. Une …   Wikipédia en Français

  • Pile — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Pile », sur le Wiktionnaire (dictionnaire universel) Sommaire 1 …   Wikipédia en Français

  • Pile ou face — Pour les articles homonymes, voir Pile ou face (homonymie). Lancer d une pièce. Le pile ou face est un jeu de hasard se jouant avec une pièce de monnaie. Le principe du jeu e …   Wikipédia en Français

  • Informatique théorique — L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités universelles (axiomes) en… …   Wikipédia en Français

  • Débordement de la pile d’exécution — Dépassement de pile En informatique, un dépassement de pile ou débordement de pile (en anglais, stack overflow) est un bogue causé par un processus qui, lors de l écriture dans une pile, écrit à l extérieur de l espace alloué à la pile, écrasant… …   Wikipédia en Français

  • Débordement de pile — Dépassement de pile En informatique, un dépassement de pile ou débordement de pile (en anglais, stack overflow) est un bogue causé par un processus qui, lors de l écriture dans une pile, écrit à l extérieur de l espace alloué à la pile, écrasant… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”