Structure de données piles, files et listes

Description

-1- -2-D´etour : les sacsINF 421 — 03 Luc MarangetLes piles et les files sont des cas particuliers des sacs.Les op´erations suivantes sont d´efinies sur les sacs◮ Le sac est-il vide ?◮ Ranger dans le sac,Un peu de listes◮ Sortir un ´el´ement du sac (un des ´el´ements rang´es au pr´ealable).Le sac typique (en style objet) :class Bag {Piles, Files...Bag () { ... }boolean isEmpty() { ... }void put(Object o) { ... }Object get() { ... }[e-mail]}http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/Remarquer : Le sac est une structure mutable.-3- -4-Les piles et les files La pilePiles et files sont des sacs munis de r`egles suppl´ementaires reliantles sorties et les entr´ees :◮ Les piles sont des sacs ( ´evang´eliques ) : dernier entr´e, premiersorti (ou LIFO : Last In, First Out).⊲ En ce cas, put se dit souvent push (empiler) et get se ditsouvent pop (d´epiler).◮ Les files sont des sacs ´egalitaires : premier entr´e, premier sorti(ou FIFO : First In, First Out).⊲ En ce cas, put peut se dire enfiler et get peut se dire d´efiler.-5- -6-La pile La file-7- -8-La file `A quoi ¸ca sert ?La file est la structure la plus intuitive.La file sert par exemple, dans un syst`eme d’exploitation, a` servirdes demandes d’impression dans l’ordre.◮ Il y a une file spool des fichiers a` imprimer.◮ Chaque utilisateur demande l’impression d’un fichier f par :...spool.put(f)...◮ Tandis qu’un acteur quelconque du syst`eme ...

Sujets

• informatique

Informations

• Publié par: Inse
• Nombre de lectures: 50
• Langue: Français

Extrait

-1-

-3-

INF 421 — 03

Luc Maranget

Un peu de listes

Piles, Files

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

Les piles et les files Pilesetfilessontdessacsmunisder`eglessupple´mentairesreliant lessortiesetlesentre´es: ◮ Les piles sont des sacs ✭ e´vang´eliques ✮ :dernierentr´e,premier sorti (ou LIFO : Last In, First Out). ⊲ En ce cas, put se dit souvent push (empiler) et get se dit souvent pop (de´piler). ◮ Lesfilessontdessacs´egalitaires:premierentr´e,premiersorti (ou FIFO : First In, First Out). ⊲ En ce cas, put peut se dire enfiler et get peutsedired´efiler.

-2-

-4-

D´etour:lessacs Les piles et les files sont des cas particuliers des sacs . Lesop´erationssuivantessontd´efiniessurlessacs ◮ Le sac est-il vide ? ◮ Ranger dans le sac, ◮ Sortirun´el´ementdusac(undes´el´ementsrange´saupre´alable). Le sac typique (en style objet) : class Bag { . . . Bag () { . . . } boolean isEmpty () { . . . } void put ( Object o ) { . . . } Object get () { . . . } } Remarquer : Le sac est une structure mutable.

La pile

-5-

-7-

La pile

La file

-6-

-8-

La file

` Aquoic¸asert? La file est la structure la plus intuitive. Lafilesertparexemple,dansunsyste`med’exploitation,a`servir des demandes d’impression dans l’ordre. ◮ Il y a une file spool desfichiers`aimprimer. ◮ Chaque utilisateur demande l’impression d’un fichier f par : . . . spool . put ( f ) . . .

◮ Tandisqu’unacteurquelconquedusyst`emed’exploitation exe´cute(conceptuellement)labouclesuivante: for ( ; ; ) { // Boucle infinie, comme ✭ while (true) { ✮ i f (! spool . isEmpty ()) { Fichier f = spool . get () ; . . . //R´llementenvoyerfa`l’imprimante. ee } }

-9-

-11-

` A quoi ca sert ? ¸ La pile est la structure la plus ✭ informatique ✮ . Son besoin se fait clairement sentir dans la situation suivante. . . ◮ Un cuisinier fait une sauce. . . ⊲ Chef, votre ´epouse au t´el´ephone ! Mettre la sauce en attente (empiler(sauce))etr´epondre... ⋆ Chef,ilyalefeu!Mettrelet´el´ephoneenattente (empiler(te´le´phone))etallere´teindrelefeu. ⋆ Lefeueste´teint... ⊲ D´epilerlataˆcheenattente(t´el´ephone)etlaterminer... ◮ De´pilerlataˆcheenattente(sauce)etlaterminer.

Exemples de calcul en notation postfixe Calculer 1 + (2 × 3) : 1 2 3 * + (ou 2 3 * 1 + d’ailleurs). 3 2 6 → 1 → 1 → 2 → → 3 → 2 → × → → + → 7 1 1 1 Calculer (1 + 2) × 3 : 1 2 + 3 * 2 3 → 1 → 1 → 2 → → + → 3 → 3 → → × → 9 1 3

1-0-

-12-

Autre utilisation des piles ´ Evaluationdesexpressionsarithme´tiques. Soit les piles d’entiers : class Stack { . . . Stack () { . . . } boolean isEmpty () { . . . } void push ( int i ) { . . . } int pop () { . . . } } Les calculettes en notation postfixe (ou ✭ polonaise ✮ ) fonctionnent a`l’aided’unepile,selonceprincipe: ◮ Un entier → l’empiler. ◮ U ´eration ⊕ , depiler x , d´epiler y , empiler ⊕ ( y x ). ne op

´ Une realisation de la calculette class Calc { public static void main ( String [] arg ) { Stack stack = new Stack () ; for ( int i = 0 ; i < arg . length ; i ++) { String cmd = arg [ i ] ; i f ( cmd . equals ( "+" )) { int x = stack . pop (), y = stack . pop () ; stack . push ( y + x ) ; } else i f . . . // Idem pour "*", "/", "-" } else { stack . push ( Integer . parseInt ( cmd )) ; // doc a } } System . out . println ( stack . pop ()) ; } } a http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Integer.html

-13-

Ex´ecutionde Calc % java Calc 1 2 + 3 ’*’ 1 -> [1] 2 -> [1, 2] + -> [3] 3 -> [3, 3] * -> [9] 9 Mais . . . % java Calc 1 + 1 -> [1] Exception in thread "main" java.util.EmptyStackException atjava.util.Stack.peek(Stack.java:79) atjava.util.Stack.pop(Stack.java:61) at Calc.main(Calc.java:9)

-15-

Correction du calcul Mode´lisonsleprogramme Calc .Son´etat: h I • S i . ◮ L’entr´ee I ,c’est-a`-direunesuitedesymboles. ◮ La pile S (d’entiers). Uneactionconsistea`lirelesymbole. h int I • S i → h I • S  int i h op I • S  v 1  v 2 i → h I • S  op ( v 1  v 2 ) i Th´eor`eme Si I est une notation postfixe P , alors la pile S contient v ( P )`alafin. h P • i → ∗ h • v ( P ) i

-14-

-16-

P ´ isions sur la notation postfixe rec Pard´efinition,unenotationpostfixeestunesuitedesymboles P . P = int | P 1 P 2 op Par exemple : 1 3 -* 0 | { 2 z + } |{z} |{z} | {z } | {z } Parde´finition,lavaleurd’unenotationpostfixeest: v ( int ) = int v ( P 1 P 2 op ) = op ( v ( P 1 )  v ( P 2 ))

Lemme Pour toute suite de symboles I , toute pile S , et toute notation postfixe : h P I • S i → ∗ h I • S v ( P ) i Demonstration Par induction (sur P ). Dans le cas ´ P = P 1 P 2 op . h P I • S i = h P 1 P 2 op I • S i → ∗ h P 2 op I • S  v ( P 1 ) i → ∗ h op I • S  v ( P 1 )  v ( P 2 ) i → h I • S  op ( v ( P 1 )  v ( P 2 )) i = h I • S  v ( P ) i

-1-7

-19-

Pileetappeldem´ethode Revenonssurlafusionr´ecursivequie´chouepar ✭ d´ebordementdela pile ✮ pour des listes assez longues. static List merge ( List xs , List ys ) { i f ( xs == null ) { return ys ; } else i f ( ys == null ) { return xs ; } //NB:de´sormaisxs!=null&&ys!=null else i f ( xs . val <= ys . val ) { return new List ( xs . val , merge ( xs . next , ys )) ; } else { // NB: ys.val < xs.val return new List ( ys . val , merge ( xs , ys . next )) ; } }

Dans le cas qui nous occupe Nousallonsmode´liserunprocesseurenJava,etexaminerceque faitlecodecompil´ede merge . ◮ Toutes les variables sont globales (registres). ◮ Lecontrˆoleestexplicite(code=se´quenced’instructions). ⊲ Ilyadese´tiquettes(pointsdansl’ex´ecution). ⊲ Il y a des instructions ✭ goto ✮ (transfert direct) et ✭ goto * ✮ (transfert indirect). ´ merge : // ✭ Etiquette ✮ dede´butdelame´thode. /* La pile S est P ret xs ys Il faut rendre P merge ( xs ys ) */ ys = S . pop () ; xs = S . pop () ; i f ( xs == null ) { lab = S . pop () ; S . push ( ys ) ; goto * lab ; } . . .

-18-

-20-

Appeldeme´thode En simplifiant un peu. ◮ Lesyst`med’exe´cutionJavadisposed’unepile. e ◮ Pourappelerunem´ethode: ⊲ Empiler une addresse de retour . ⊲ Empilerlesargumentsdelame´thode. ◮ Une m´ethode ⊲ Pre´lude:re´cupe´rerlesarguments. ⊲ Codedelam´ethodeproprementdit...quirendlapiledans l’´etatou`ill’atrouv´ee. ⊲ Postlude : (pour revenir) ⋆ D´epilerl’adressederetour. ⋆ Empilerle´ulttdelame´thode. res a ⋆ Transfe´rerlecontrˆoleduprogramme`al’adressederetour.

Appelre´cursif . /* La pile S est P ret Il faut rendre P merge ( xs ys ) */ i f ( xs . val <= ys . val ) { S . push ( xs . val ) ; // Sauver xs.val dans la pile S . push ( lab1 ) ; S . push ( xs . next ) ; S . push ( ys ) ; // S est P xs.val lab 1  xs.next ys goto merge ; //Appelr´ecursif lab1 : // S est P merge ( xs.next ys ) r = S . pop () ; //R´esultatdel’appel xsPointVal = S . pop () ; //xs.valsauve´avantl’appel lab = S . pop () ; // ´ Etiquettederetour S . push ( new List ( xsPointVal , r )) ; goto * lab ; // La pile est P merge ( xs ys ) ok. } . . .

2--1

-23-

Codage des piles (d’entiers) Le principe est le suivant : ◮ L’objet pile (classe Stack )maintientuneliste(prive´e) d’entiers. ◮ Ope´rations: ⊲ Ajouteraude´butdelaliste, ⊲ Enleverdude´butdelaliste. class Stack { private List me ; Stack () { me = null ; } boolean isEmpty () { return me == null ; } . . . }

Empiler : ajouter a d´but u e m

3 2 me = new List (4, me ) ;

m

4 3 2

1

1

2-2-

-24-

Diversion:modificateursdevisibilite´ Le champ me des objets Stack estde´clar´e private . class Stack { private List me ; . . . En effet, il ne faut pas que qui que ce soit d’autre (que l’objet Stack ) utilise me . Les modificateurs, du plus restrictif au plus permissif. ◮ private , visible de la classe uniquement. ◮ rien, visible du package (un paquet de classes). ◮ protected visibledesh´eritiers(unenouvellenotion). ◮ public visible de partout. Puisquenousn’utilisonsnipackage,nih´eritage,onselimite`a private eta`rien.(saufpour public static void main ).

De´piler:enleverdud´ebut m

3 2 me = me . next ;

m

3 2

1

1