Français
Menu

Qu'est-ce que Pile (stack) ?

Structure de données LIFO (dernier entré, premier sorti) dans laquelle l'élément ajouté en dernier est retiré en premier. L'ajout d'un élément s'appelle push et son retrait pop. Les piles servent à gérer les adresses de retour et les variables locales lors des appels de fonction (pile d'appels), à évaluer les expressions en notation polonaise inverse et au parcours en profondeur.

Nom japonais: スタック

« Pile (stack) » apparaît dans 33 questions d'entraînement réparties sur 8 thèmes, dont Éditeurs de liens, chargeurs et exécutables, ISA et assembleur, Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Pile (stack)

Dans une fonction qui n'appelle aucune autre fonction (fonction feuille), il n'est souvent pas nécessaire de sauvegarder ra sur la pile. Quelle en est la raison ?

  1. AParce qu'une fonction feuille n'utilise pas l'instruction ret
  2. BParce que le CPU empile automatiquement l'adresse de retour d'une fonction feuille
  3. CParce qu'elle n'appelle aucune autre fonction, ra n'est pas écrasé et l'adresse de retour reste intacte
Afficher la réponse et l'explication

Réponse : C. Parce qu'elle n'appelle aucune autre fonction, ra n'est pas écrasé et l'adresse de retour reste intacte

ra étant écrasé à chaque jal qui appelle une fonction, une fonction qui en appelle d'autres doit d'abord sauvegarder sa propre adresse de retour sur la pile. Une fonction feuille n'utilisant pas jal, ra n'est pas altéré et elle peut exécuter ret sans sauvegarde. Si elle n'utilise pas non plus de registres sauvegardés par l'appelé, elle n'a même pas besoin de créer de cadre de pile. L'instruction call de x86 empilant toujours l'adresse de retour, c'est une différence avec RISC-V.

En RISC-V, que se passe-t-il si l'on oublie de sauvegarder ra sur la pile en écrivant une fonction récursive qui s'appelle elle-même ?

  1. Ara est écrasé par l'appel interne, et la fonction externe ne peut plus revenir à son véritable appelant
  2. BLe CPU sauvegarde automatiquement ra, donc aucun problème ne survient
  3. CLe résultat du calcul est doublé quelle que soit la profondeur de récursion
Afficher la réponse et l'explication

Réponse : A. ra est écrasé par l'appel interne, et la fonction externe ne peut plus revenir à son véritable appelant

Le jal de l'appel récursif écrase ra avec « l'instruction qui suit l'appel interne à la fonction ». Sans sauvegarde, lorsque la fonction externe exécute ret, elle revient à l'intérieur d'elle-même au lieu de son appelant d'origine, ce qui provoque des répétitions ou des dysfonctionnements. C'est pourquoi une fonction qui en appelle d'autres doit sauvegarder ra sur la pile dans son prologue et le restaurer dans son épilogue.

« Pile (stack) » dans les explications

Questions mentionnant « Pile (stack) » (33)

  1. Dans une fonction qui n'appelle aucune autre fonction (fonction feuille), il n'est souvent pas nécessaire de sauvegarder ra sur la pile. Quelle en est la raison ?
  2. En RISC-V, que se passe-t-il si l'on oublie de sauvegarder ra sur la pile en écrivant une fonction récursive qui s'appelle elle-même ?
  3. Quel est l'avantage de l'agencement qui fait croître le tas et la pile d'un processus en sens opposés, avec un vaste espace libre entre eux ?
  4. Lorsqu'une récursion trop profonde dépasse la limite de la pile, que se passe-t-il généralement sous Linux notamment ?
  5. Sur un petit microcontrôleur sans MMU, quelle précaution concernant la surconsommation de pile est correcte ?
  6. Sur une pile vide, on effectue dans cet ordre les opérations push 1, push 2, pop, push 3, push 4, pop, pop. Dans quel ordre les valeurs sont-elles retirées par pop ?
  7. On évalue l'expression « 3 4 + 2 * 5 − » écrite en notation polonaise inverse (notation postfixée) en empilant chaque nombre sur une pile et, pour chaque opérateur, en retirant deux valeurs, en calculant le résultat et en l'empilant à nouveau. Quel est le résultat ? L'opérande gauche d'un opérateur est la valeur empilée la première.
  8. Une pile est représentée par le tableau d'entiers st de 5 éléments et la variable entière top. Tous les éléments de st valent 0 au départ, et top vaut 0. push(v) ajoute 1 à top puis exécute st[top] ← v ; pop() renvoie la valeur de st[top] puis soustrait 1 de top (les éléments de st ne sont pas modifiés). Quelles sont les valeurs de top et st après l'exécution du programme suivant ?
  9. Que contient le compteur ordinal (PC) du processeur ?
  10. Quelle zone est généralement utilisée pour sauvegarder temporairement l'adresse de retour, entre autres, lors de l'appel d'un sous-programme (fonction) ?
  11. Quel est le fonctionnement correct de l'instruction RISC-V « lw t0, 8(sp) » ?
  12. Quel est le principal objectif de la définition d'une convention d'appel (calling convention) ?
  13. Dans la convention d'appel standard de RISC-V, quels registres servent à transmettre les arguments entiers et la valeur de retour ?
  14. Dans la convention d'appel RISC-V, que signifie le fait que s0 à s11 soient des registres « sauvegardés par l'appelé » (callee-saved) ?
  15. Quel est l'objectif de l'exécution de « addi sp, sp, -16 » au début d'une fonction RISC-V ?

Comparatifs incluant ce terme

Termes associés

Variable Adresse de retour Tas (heap) Récursion (récursivité) Tableau Argument Convention d'appel Cadre de pile (stack frame) File d'attente Valeur de retour

Retour au glossaire