cours sur les structures de données

Description

INF 421 Luc MarangetUn peu de listesPiles, [e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/1D´etour : les sacsLes 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,◮ Sortir un ´el´ement du sac (un des ´el´ements rang´es au pr´ealable).Le sac typique (en style objet) :class Bag {...Bag () { ... }boolean isEmpty() { ... }void put(Object o) { ... }Object get() { ... }}Remarquer : Le sac est une structure mutable.2Les piles et les filesPiles 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.3La pile4La pile5La file6La file7`A quoi c¸a 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 d’exploitationex´ecute ...

Sujets

• informatique

Informations

• Publié par: Viod
• Nombre de lectures: 35
• Langue: Français

Extrait

INF 421

Un

peu

de

Luc Maranget

listes

Piles, Files

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

1

De´tour:lessacs

Les piles et les files sont des cas particuliers dessacs.

Lesop´erationssuivantessontde´finiessurlessacs

◮Le sac est-il vide ?

◮Ranger dans le sac,

◮.)ele´rpbalauritroSeme´le´ntnrse´emseuana´gsac(ntdus´elunde

Le sac typique (en style objet) : classBag{ . . . Bag() {. . .} booleanisEmpty() {. . .} voidput(Object o) {. . .} Object get() {. . .} }

Remarquer :Le sac est une structure mutable.

2

Les piles et les files

Pilesetfilessontdessacsmunisdere`glessupplementairesreliant ´ les sorties et les ent ´ rees :

◮Les piles sont des sacs✭leqina´geus´ev✮rei:ediernntree,r´empr sorti (ou LIFO : Last In, First Out).

⊲En ce cas,putse dit souventpush(empiler) etgetse dit souventpope´ipd(.ler)

◮ssonsfileLereostrie´p,erimermitrenesirre:page´atilsedtscas (ou FIFO : First In, First Out).

⊲En ce cas,putpeut se dire enfiler etgetpeseut.releridfie´d

3

La

pile

4

La

pile

5

La

file

6

La

file

7

` 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 filespooldesfichiers`emirpmia.r

◮Chaque utilisateur demande l’impression d’un fichierfpar : . . .spool.put(f). . .

◮tionsyduuenqcoelquuratiolpxe’deme`tscaet’unuidqsTna ex´ecute(conceptuellement)labouclesuivante: for( ; ; ) {// Boucle infinie, comme✭while (true) {✮ i f(!spool.isEmpty()) { Fichier f=spool.get() ; . . .mi’lmirpetna./R/e´lelementenvoyerf`a } }

8

` Aquoic¸asert?

La pile est la structure la plus✭rofnitameuqi✮.

Son besoin se fait clairement sentir dans la situation suivante. . .

◮Un cuisinier fait une sauce. . .

⊲´tuae´lenohpCf,hetrvoepe´neetanttttree!Meuceelasa ouse (empiler(sauce))etre´pondre... ⋆eenattenel´ephontterel´telef!ueMCayli,fehet (empiler(te´le´phone))etallere´teindrelefeu. ⋆nt..eteiest´efeuL.

⊲ph´ee)onlaetrmtereni...elt´e(ntteatenhecaˆtalrelipe´D

◮.erinpe´Drelilatˆacheenattent(eascu)etealetmr

9

Autre utilisation des piles

´ Evaluationdesexpressionsarithm´etiques.

Soit les piles d’entiers : classStack{ . . . Stack() {. . .} booleanisEmpty() {. . .} voidpush(inti) {. . .} intpop() {. . .} }

Les calculettes en notation postfixe (ou✭polonaise✮) fonctionnent `al’aided’unepile,selonceprincipe:

◮Un entier→l’empiler.

◮´erationUenpo⊕, depilerxreld,ipe´y, empiler⊕(y x).

10

Exemples de calcul en notation postfixe

Calculer 1 + (2×3) :1 2 3 * +(ou2 3 * 1 +’ailleurs).d

3 2 6 →1→ 1 →2→ →3→ 2  →→ × →+→ 1 1 1

Calculer (1 + 2)×3 :1 2 + 3 *

2 3 →1→ 1 →2→ →+→ 3 →3 × →→ → 1 3

11

7

9