Spécialité N.S.I.
Classe de terminale générale
Structuration : Les piles et les files
1) Les piles (Stack en anglais)
Les piles sont basées sur le principe LIFO (Last In First Out : le dernier rentré sera le premier à
sortir).
On retrouve souvent ce principe LIFO en informatique, Exemples :
Historique de recherche Bouton annuler Pointeur de pile
Voici les opérations que l'on peut réaliser sur une pile :
on peut savoir si une pile est vide (pile_vide?)
on peut empiler un nouvel élément sur la pile (push)
on peut récupérer l'élément au sommet de la pile tout en le supprimant. On dit que l'on dépile (pop)
on peut accéder à l'élément situé au sommet de la pile sans le supprimer de la pile (peek)
on peut connaitre le nombre d'éléments présents dans la pile (taille)
Exemples :
Soit une pile P composée des éléments suivants : 12, 14, 8, 7, 19 et 22 , Pour chaque exemple ci-dessous on
repart de la pile d'origine :
pop(P) renvoie 22 et la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7 et 19 (le
sommet de la pile est 19)
push(P,42) la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7, 19, 22 et 42
sommet(P) renvoie 22, la pile P n'est pas modifiée
si on applique pop(P) 6 fois de suite, pile_vide?(P) renvoie vrai
Après avoir appliqué pop(P) une fois, taille(P) renvoie 5
Question : Soit une pile P composée des éléments suivants : 15, 11, 32, 45 et 67 (le sommet de la pile est 67).
Quel est l'effet de l'instruction pop(P)
2) Les files (Queue en anglais)
Comme les piles, les files ont des points communs avec les listes.
Différences majeures : dans une file on ajoute des éléments à une
extrémité de la file et on supprime des éléments à l'autre extrémité. On
prend souvent l'analogie de la file d'attente devant un magasin pour
décrire une file de données.
Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici
aussi, on retrouve souvent ce principe FIFO en informatique. Exemples
Spooler d’imprimante Ordonnancement des taches
Voici les opérations que l'on peut réaliser sur une file :
on peut savoir si une file est vide (file_vide?)
on peut ajouter un nouvel élément à la file (ajout)
on peut récupérer l'élément situé en bout de file tout en le supprimant (retire)
on peut accéder à l'élément situé en bout de file sans le supprimer de la file (premier)
on peut connaitre le nombre d'éléments présents dans la file (taille)
Exemples :
Soit une file F composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est
22 ; le dernier élément rentré dans la file est 12). Pour chaque exemple ci-dessous on repart de la file d'origine :
ajout(F,42) la file F est maintenant composée des éléments suivants : 42, 12, 14, 8, 7, 19 et 22 (le
premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 42)
retire(F) la file F est maintenant composée des éléments suivants : 12, 14, 8, 7, et 19 (le premier élément
rentré dans la file est 19 ; le dernier élément rentré dans la file est 12)
premier(F) renvoie 22, la file F n'est pas modifiée
si on applique retire(F) 6 fois de suite, pile_vide?(F) renvoie vrai
Après avoir appliqué retire(F) une fois, taille(F) renvoie 5
Soit une file F composée des éléments suivants : 1, 12, 24, 17, 21 et 72 (le premier élément rentré dans la file est
72 ; le dernier élément rentré dans la file est 1).
Question : Quel est l'effet de l'instruction ajout(F,25)
