Piles

Files

Piles et Files

Ivan Noyer

Lycée Thiers

1/27 Ivan Noyer Piles et Files

 Piles
Files

1 Piles
Généralités

2 Files

2/27 Ivan Noyer Piles et Files

 Piles
Files

Crédits

Wikipédia : en français et (plus complet mais en anglais) ici

3/27 Ivan Noyer Piles et Files

 Piles
Files

Crédits

Wikipédia : en français et (plus complet mais en anglais) ici

La documentation sur le module Stack de OCaml

3/27 Ivan Noyer Piles et Files

 Piles
Files

Crédits

Wikipédia : en français et (plus complet mais en anglais) ici

La documentation sur le module Stack de OCaml
La documentation sur le module Queue de OCaml

3/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

1 Piles
Généralités

2 Files

4/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

1 Piles
Généralités

2 Files

5/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Pile
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.

Figure – Empiler et dépiler

6/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Pile
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.

Figure – Empiler et dépiler

6/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Exemple

Figure – Empilement de A puis B, dépilement de B puis A (LIFO)

7/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Historique

Turing 1946. Description théorique d’appel et de retour de

sous-routines.

8/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Historique

Turing 1946. Description théorique d’appel et de retour de

sous-routines.
Klaus Samelson et Friedrich L. Bauer de l’université
Technique de Münich généralisent l’idée en 1955 en
présentant une modélisation du fonctionnement des
ordinateurs à base de piles.

8/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Historique

Turing 1946. Description théorique d’appel et de retour de

sous-routines.
Klaus Samelson et Friedrich L. Bauer de l’université
Technique de Münich généralisent l’idée en 1955 en
présentant une modélisation du fonctionnement des
ordinateurs à base de piles.
Même concept, indépendamment développé par l’australien
Charles Leonard Hamblin en 1957.

8/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Les primitives indispensables

 Empiler  : ajoute un élément sur la pile. Terme anglais

correspondant :  Push .

9/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Les primitives indispensables

 Empiler  : ajoute un élément sur la pile. Terme anglais

correspondant :  Push .
 Dépiler  : enlève l’élément au sommet de la pile et le
renvoie. Terme anglais correspondant :  Pop .

9/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Les primitives indispensables

 Empiler  : ajoute un élément sur la pile. Terme anglais

correspondant :  Push .
 Dépiler  : enlève l’élément au sommet de la pile et le
renvoie. Terme anglais correspondant :  Pop .
 La pile est-elle vide ?  : renvoie vrai si la pile est vide, faux
sinon.  isempty 

9/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Autres primitives
Elles peuvent être obtenues à partir des 3 premières :
 Nombre d’éléments de la pile  : renvoie le nombre
d’éléments dans la pile. Complexité : Selon les
implémentations, peut être fait soit en temps constant soit en
temps linéaire.

10/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Autres primitives
Elles peuvent être obtenues à partir des 3 premières :
 Nombre d’éléments de la pile  : renvoie le nombre
d’éléments dans la pile. Complexité : Selon les
implémentations, peut être fait soit en temps constant soit en
temps linéaire.
 Quel est l’élément de tête ?  : renvoie l’élément de tête
sans le désempiler. Terme anglais correspondant :  Peek .

10/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Autres primitives
Elles peuvent être obtenues à partir des 3 premières :
 Nombre d’éléments de la pile  : renvoie le nombre
d’éléments dans la pile. Complexité : Selon les
implémentations, peut être fait soit en temps constant soit en
temps linéaire.
 Quel est l’élément de tête ?  : renvoie l’élément de tête
sans le désempiler. Terme anglais correspondant :  Peek .
 Vider la pile  : dépiler tous les éléments. Complexité :
Selon l’implémentation, cela peut être fait en temps constant
ou linéaire. Terme anglais correspondant :  Clear .

10/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Autres primitives
Elles peuvent être obtenues à partir des 3 premières :
 Nombre d’éléments de la pile  : renvoie le nombre
d’éléments dans la pile. Complexité : Selon les
implémentations, peut être fait soit en temps constant soit en
temps linéaire.
 Quel est l’élément de tête ?  : renvoie l’élément de tête
sans le désempiler. Terme anglais correspondant :  Peek .
 Vider la pile  : dépiler tous les éléments. Complexité :
Selon l’implémentation, cela peut être fait en temps constant
ou linéaire. Terme anglais correspondant :  Clear .
 Dupliquer l’élément de tête  et  Échanger les deux
premiers éléments  : existe sur les calculatrices fonctionnant
en notation polonaise inverse (style HP). Termes anglais
correspondants :  Dup  et  Swap  respectivement.
10/27 Ivan Noyer Piles et Files
 Piles
Généralités
Files

Un peu de maths

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 (la pile vide).

11/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

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.

12/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

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.
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ésempile l’adresse de la page
précédente en cliquant le bouton  Afficher la page
précédente .

12/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

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.
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ésempile 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.

12/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

La fonction  Annuler la frappe  (en anglais Undo) d’un

traitement de texte mémorise les modifications apportées au
texte dans une pile.

13/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

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 d’abord utilise une
pile pour mémoriser les nœuds visités.

13/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

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 d’abord utilise une
pile pour mémoriser les nœuds visités.
Inversion d’un tableau ou d’une chaı̂ne de caractères.

13/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Applications

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 d’abord utilise une
pile pour mémoriser les nœuds visités.
Inversion d’un tableau ou d’une chaı̂ne de caractères.
Les algorithmes récursifs admis par certains langages (LISP,
C, Python,etc. . . ) utilisent implicitement une pile d’appel.

13/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Listes OCaml et piles

En OCaml, les listes ont un comportement de piles

(fonctionnelles). Il n’y a donc pas besoin d’importer de
module particulier pour bénéficier d’une structure de pile.

14/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Listes OCaml et piles

En OCaml, les listes ont un comportement de piles

(fonctionnelles). Il n’y a donc pas besoin d’importer de
module particulier pour bénéficier d’une structure de pile.
Les listes OCaml ne sont pas des structures impératives : il n’y
a pas d’effets de bord.
Pour une structure de pile impérative préférer le module
Stack.

14/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

En OCaml
1 open Stack ;; (* charger le module Stack ( pile ) *)
2 let s = create () ;; (* cr é ation d ’ une pile vide *)
3 push 3 s ; push 6 s ; push 7 s ;;
4 (* -> ajouter 3 nombres dans la pile *)
5 let s ’ = copy ( s ) ;; (* faire une copie de la pile *)
6 for i = 0 to 2 do
7 (* notre premi è re boucle for CAML *)
8 (* pos s : retire le sommet *)
9 Printf . printf " % d ; " ( pop s ) ;
10 done ;;
11 try
12 (* On sait que le code suivant risque
13 de g é n é rer une exception ...
14 ... Mais on ’ essaye ’ quand m ^ e me ( try ) ! *)
15 print_int ( pop s ) ;
16 (* on risque depiler une pile vide !! *)
17 with Empty ->
18 print_string " pile vide : t ouf ???\ n " ;;

15/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Rendu (jusqu’aux empilements)

1 # open Stack ;;
2 # let s = create () ;;
3 val s : ’ _a Stack . t = < abstr >
4 # push 3 s ; push 6 s ; push 7 s ;;
5 - : unit = ()
6 # let s ’ = copy ( s ) ;;
7 val s ’ : int Stack . t = < abstr >
8 # for i = 0 to 2 do
9 Printf . printf " % d ; " ( pop s ) ;
10 done ;;
11 7; 6; 3; - : unit = ()
12 # push 3 s ; push 6 s ; push 7 s ;;
13 - : unit = ()

16/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Rendu (fin)

1 # let s ’ = copy ( s ) ;;
2 val s ’ : int Stack . t = < abstr >
3 # for i = 0 to 2 do
4 (* notre premi è re boucle for CAML *)
5 Printf . printf " % d ; " ( pop s ) ;
6 done ;;
7 7; 6; 3; - : unit = ()
8 # try
9 (* On sait que le code suivant risque de g é n é rer une
exception *)
10 (* mais on ’ essaye ’ quand m ^ e me ( try ) *)
11 print_int ( pop s ) ; (* on risque ded é piler une pile
vide *)
12 with Empty -> print_string " vous avez voulu d é piler
une pile vide \ n " ;;
13 vous avez voulu d é piler une pile vide
14 - : unit = ()

17/27 Ivan Noyer Piles et Files

 Piles
Généralités
Files

Des piles en C
À partir de tableaux redimensionnables

Dans le fichier vector.c (cf. cours listes), ajoutons :

1 // r e n v o i e l e sommet SANS dé p i l e r

2 i n t v e c to r t o p ( vector ∗v ) {
3 // r e n v o i e l ’ é l é ment en h a u t de p i l e SANS dé p i l e r
4 int n = vector size (v) − 1;
5 a s s e r t ( 0 <= n ) ;
6 return vector get (v , n) ;
7 }
8
9 // Dé p i l e l e sommet e t l e r e n v o i e
10 // dé c r é mente v−>s i z e + r e d i m e n s i o n n e m e n t p o s s i b l e
11 i n t vector pop ( vector ∗v ) {
12 int n = vector size (v) − 1;
13 a s s e r t ( 0 <= n ) ;
14 int r = vector get (v , n) ;
15 v e c t o r r e s i z e ( v , n ) ; //
16 return r ;
17
18/27
} Ivan Noyer Piles et Files
 Piles
Généralités
Files

Des piles en C
À partir de listes chaı̂nées

Dans le fichier tplc.c (cf TP sur les listes chaı̂nées) ajoutons :

1 L i s t e ∗ c r e a t e ( ) { // c r é e une l i s t e v i d e
2 L i s t e ∗ l i s t e = malloc ( s i z e o f ( L i s t e ) ) ;
3 l i s t e −> f i r s t = NULL ;
4 return l i s t e ;
5 }
6
7 v o i d push ( L i s t e ∗ l i s t e , i n t x ) { // e m p i l e r
8 ajouterDebut ( l i s t e , x ) ;
9 }
10
11 i n t pop ( L i s t e ∗ l i s t e ) { // dé p i l e r
12 return supprimer ( l i s t e ,0) ;
13 }
14

19/27 Ivan Noyer Piles et Files

 Piles
Files

1 Piles
Généralités

2 Files

20/27 Ivan Noyer Piles et Files

 Piles
Files

Définition
En informatique, une file (queue en anglais) est une structure
de données basée sur le principe du Premier entré, premier
sorti, en anglais FIFO (First In, First Out), ce qui veut dire
que les premiers éléments ajoutés à la file seront les premiers à
être récupérés.

Figure – Une pile (FIFO)

21/27 Ivan Noyer Piles et Files

 Piles
Files

Définition
En informatique, une file (queue en anglais) est une structure
de données basée sur le principe du Premier entré, premier
sorti, en anglais FIFO (First In, First Out), ce qui veut dire
que les premiers éléments ajoutés à la file seront les premiers à
être récupérés.
Le fonctionnement ressemble à une file d’attente à la poste :
les premières personnes à arriver sont les premières personnes
à sortir de la file.

Figure – Une pile (FIFO)

21/27 Ivan Noyer Piles et Files

 Piles
Files

Applications

Usage : Mémoriser temporairement des transactions qui

doivent attendre pour être traitées dans l’ordre d’arrivée.

22/27 Ivan Noyer Piles et Files

 Piles
Files

Applications

Usage : Mémoriser temporairement des transactions qui

doivent attendre pour être traitées dans l’ordre d’arrivée.
Les serveurs d’impression, qui doivent traiter les requêtes dans
l’ordre dans lequel elles arrivent, et les insèrent dans une file
d’attente (ou une queue).

22/27 Ivan Noyer Piles et Files

 Piles
Files

Applications

Usage : Mémoriser temporairement des transactions qui

doivent attendre pour être traitées dans l’ordre d’arrivée.
Les serveurs d’impression, qui doivent traiter les requêtes dans
l’ordre dans lequel elles arrivent, et les insèrent dans une file
d’attente (ou une queue).
Certains moteurs multitâches, dans un système d’exploitation,
qui doivent accorder du temps-machine à chaque tâche, sans
en privilégier aucune.

22/27 Ivan Noyer Piles et Files

 Piles
Files

Applications

Usage : Mémoriser temporairement des transactions qui

doivent attendre pour être traitées dans l’ordre d’arrivée.
Les serveurs d’impression, qui doivent traiter les requêtes dans
l’ordre dans lequel elles arrivent, et les insèrent dans une file
d’attente (ou une queue).
Certains moteurs multitâches, dans un système d’exploitation,
qui doivent accorder du temps-machine à chaque tâche, sans
en privilégier aucune.
Un algorithme de parcours en largeur d’abord dans un graphe
utilise une file pour mémoriser les nœuds visités.

22/27 Ivan Noyer Piles et Files

 Piles
Files

Applications

Usage : Mémoriser temporairement des transactions qui

doivent attendre pour être traitées dans l’ordre d’arrivée.
Les serveurs d’impression, qui doivent traiter les requêtes dans
l’ordre dans lequel elles arrivent, et les insèrent dans une file
d’attente (ou une queue).
Certains moteurs multitâches, dans un système d’exploitation,
qui doivent accorder du temps-machine à chaque tâche, sans
en privilégier aucune.
Un algorithme de parcours en largeur d’abord dans un graphe
utilise une file pour mémoriser les nœuds visités.
Pour créer toutes sortes de mémoires tampons (en anglais
buffers).

22/27 Ivan Noyer Piles et Files

 Piles
Files

Primitives

Voici les primitives communément utilisées pour manipuler des

files. Il n’existe pas de normalisation pour les primitives de
manipulation de file. Leurs noms sont donc indiqués de manière
informelle.
 Mettre dans la file  : ajoute un élément dans la file. Terme
anglais correspondant :  Enqueue .

23/27 Ivan Noyer Piles et Files

 Piles
Files

Primitives

Voici les primitives communément utilisées pour manipuler des

files. Il n’existe pas de normalisation pour les primitives de
manipulation de file. Leurs noms sont donc indiqués de manière
informelle.
 Mettre dans la file  : ajoute un élément dans la file. Terme
anglais correspondant :  Enqueue .
 Défiler  : renvoie le prochain élément de la file, et le retire
de la file. Terme anglais correspondant :  Dequeue .

23/27 Ivan Noyer Piles et Files

 Piles
Files

Primitives

Voici les primitives communément utilisées pour manipuler des

files. Il n’existe pas de normalisation pour les primitives de
manipulation de file. Leurs noms sont donc indiqués de manière
informelle.
 Mettre dans la file  : ajoute un élément dans la file. Terme
anglais correspondant :  Enqueue .
 Défiler  : renvoie le prochain élément de la file, et le retire
de la file. Terme anglais correspondant :  Dequeue .
 La file est-elle vide ?  : renvoie  vrai  si la file est vide,
 faux  sinon.

23/27 Ivan Noyer Piles et Files

 Piles
Files

Primitives

Voici les primitives communément utilisées pour manipuler des

files. Il n’existe pas de normalisation pour les primitives de
manipulation de file. Leurs noms sont donc indiqués de manière
informelle.
 Mettre dans la file  : ajoute un élément dans la file. Terme
anglais correspondant :  Enqueue .
 Défiler  : renvoie le prochain élément de la file, et le retire
de la file. Terme anglais correspondant :  Dequeue .
 La file est-elle vide ?  : renvoie  vrai  si la file est vide,
 faux  sinon.
 Nombre d’éléments dans la file  : renvoie le nombre
d’éléments dans la file.

23/27 Ivan Noyer Piles et Files

 Piles
Files

Implémentation en OCaml

On peut utiliser une liste comme une file FIFO.

24/27 Ivan Noyer Piles et Files

 Piles
Files

Implémentation en OCaml

On peut utiliser une liste comme une file FIFO.

Pas efficace : alors que les ajouts et suppressions en fin de
liste sont rapides, les opérations d’insertions ou de retraits en
début de liste sont lentes (car tous les autres éléments doivent
être décalés d’une position).

24/27 Ivan Noyer Piles et Files

 Piles
Files

Implémentation en OCaml

On peut utiliser une liste comme une file FIFO.

Pas efficace : alors que les ajouts et suppressions en fin de
liste sont rapides, les opérations d’insertions ou de retraits en
début de liste sont lentes (car tous les autres éléments doivent
être décalés d’une position).
Pour implémenter une file, utiliser le module OCaml Queue
qui a été conçue pour fournir des opérations d’ajouts et de
retraits rapides dans la file.

24/27 Ivan Noyer Piles et Files

 Piles
Files

En OCaml

1 open Queue ;; (* importer le module *)

2 let q = create () ;; (* file vide *)
3 let q ’ = copy ( q ) ;; (* copy de q *)
4 push 3 q ; push 6 q ; push 7 q ;; (* ajout de 3 6 7 *)
5 for i = 0 to 2 do (* vider q *)
6 print_int ( take q )
7 done ;; (* defiler 3 fois *)
8 try
9 print_int ( take q ) ; (* d é filer une file vide *)
10 with Empty -> print_string " file vide \ n " ;;

Une exception Empty est soulevée quand on essaye de défiler

(take) une file vide.

25/27 Ivan Noyer Piles et Files

 Piles
Files

Rendu

1 # open Queue ;;
2 # let q = create () ;;
3 val q : ’ _a Queue . t = < abstr >
4 # let q ’ = copy ( q ) ;;
5 val q ’ : ’ _a Queue . t = < abstr >
6 # push 3 q ; push 6 q ; push 7 q ;;
7 - : unit = ()
8 # for i = 0 to 2 do (* vider q *)
9 print_int ( take q ) ; (* d é filer *)
10 done ;;
11 367 - : unit = ()
12 # try
13 print_int ( take q ) ; (* d é filer une file vide *)
14 with Empty -> print_string " file vide \ n " ;;
15 file vide
16 - : unit = ()

26/27 Ivan Noyer Piles et Files

 Piles
Files

Implémentations
En C, on peut créer les structures suivantes :

1 // c e qu ’ on met d a n s l a f i l e
2 t y p e d e f s t r u c t e l e m e n t { // on y met c e qu ’ on v e u t :
3 i n t v ; // v a l e u r ( m a i s a u t r e s champs p o s s i b l e s )
4 }elt ;
5
6 t y p e d e f s t r u c t m{ // l i s t e d b l t cha ı̂ né e ( why n o t ? )
7 elt val ;
8 s t r u c t m∗ n e x t ; // s u i v a n t
9 s t r u c t m∗ p r e v ; // p r é c é d e n t
10 } maillon ;
11
12 t y p e d e f s t r u c t p { // s t r u c t u r e de c o n t r ô l e
13 m a i l l o n ∗ f i r s t ; // p o i n t e v e r s l e 1 e r m a i l l o n
14 m a i l l o n ∗ l a s t ; // p o i n t e v e r s l e d e r n i e r
15 // a u t r e s i n f o s , p a r e x e m p l e :
16 i n t s i z e ; // i n c r a v e c push , d e c r a v e c t a k e
17 } grip ;
18
27/27 Ivan Noyer Piles et Files