Les piles et les files
Numérique et sciences informatiques
Les piles
Les piles sont fondées sur le principe du « dernier arrivé, premier sorti » ; on les dit de type LIFO (Last In,First Out). C’est le principe même de la pile d’assiette : c’est la dernière assiette posée sur la pile d’assiettes sales qui sera la première lavée.
Une réalisation concrète de la structure pile doit fournir dans l’idéal :
Action | Instruction |
---|---|
Créer une pile P vide | creer_pile_vide() |
tester si une pile est vide | est_vide(Pile) renvoie vrai si la pile pile est vide |
Insérer un nouvel élément e au sommet de la pile Pile(push) | empiler(Pile,e) |
Enlever et retourner l'élément au sommet de la pile Pile (pop) | depiler(Pile) |
Compter le nombre d'éléments présents dans une pile Pile | taille(Pile) |
Créer une nouvelle liste L1 à partir d'un élement x d'une liste existante L | L1 = cons(x,L) |
Entraînement 2 :
Que contiennent les variables P et N après cette série d'instruction :
P= creer_pile_vide()
empiler(P,3)
empiler(P,2)
N = depiler(P)
empiler(P,5)
empiler(P,7)
empiler(P,9)
Implémentation en python
class Pile:
"""Classe définissant une structure de pile."""
def __init__(self):
self.contenu = []
def est_vide(self):
"""Renvoie le booléen True si la pile est vide, False sinon."""
return self.contenu == []
def empiler(self, v):
"""Place l'élément v au sommet de la pile"""
self.contenu.append(v)
def depiler(self):
"""
Retire et renvoie l’élément placé au sommet de la pile,
si la pile n’est pas vide.
"""
if not self.est_vide():
return self.contenu.pop()
pile1 = Pile()
pile1.empiler(2)
pile1.est_vide()
pile1.empiler(1)
pile1.empiler(2)
pile1.empiler(3)
print(pile1.contenu)
print(pile1.est_vide())
print(pile1.depiler())
Un exemple de classe python pour les piles avec POO (lvl 2)
Les Files
Les files sont fondées sur le principe du « premier arrivé, premier sorti » ; on les dit de type FIFO (First In,First Out). C’est le principe de la file d’attente devant un guichet.
Une réalisation concrète de ces structures doit fournir dans l’idéal :
- une fonction de création d’une file vide ;
- deux fonctions d’ajout et de suppression;
- une fonction vérifiant si une file est vide.
on peut réaliser les opérations suivantes sur un objet de type File:
Action | Instruction |
---|---|
Créer une file File vide | creer_file_vide() |
tester si une file est vide | est_vide(File) renvoie vrai si la pile pile est vide |
Enfiler un nouvel élément e : le mettre en dernier(enqueue) | enfiler(File,e) |
Défiler un élément, le premier (le supprimer) (dequeue) | defiler(File) |
Afficher le nombre d'éléments présents dans une file File | taille(File) |
Entraînement 3 :
Que contiennent les variables F et N après cette série d'instruction :
F = creer_file_vide()
enfiler(F,3)
enfiler(F,2)
N = defiler(F)
enfiler(F,5)
enfiler(F,7)
enfiler(F,9)
Implémentation en python
###########################################
#Extrait de la documentation python
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry") # Terry arrives
queue.append("Graham") # Graham arrives
queue.popleft() # The first to arrive now leaves
print(queue)
queue.popleft() # The second to arrive now leaves
print(queue) # Remaining queue in order of arrival
print("-----------------------------------------")
##################################################################
def creer_file():
"""création de la file"""
return[]
def est_vide(file):
"""teste si file est vide et renvoie le booléen obtenu"""
return (file == [])
def enfiler(e,file):
"""file.append(e)"""
file[len(file):] = [e]
def defiler(file):
"""return file.pop(0)"""
del file[0]
def taille(file):
"""Renvoie le nombre d'élément de la file"""
return len(file)
#########################################################
f= creer_file()
enfiler(1,f)
print(f)
enfiler(2,f)
enfiler(3,f)
print(f)
est_vide(f)
defiler(f)
print(f)
defiler(f)
defiler(f)
print(f)
print(est_vide(f))
Un exemple de classe python pour les files avec POO (lvl 2)
Entraînement 6 : proposer un fonction qui vide une file
Savoir faire
- Savoir spécifier une structure de données par son interface.
- Savoir distinguer interface et implémentation.
- Savoir écrire plusieurs implémentations d’une même structure de données.
- Savoir distinguer des structures par le jeu des méthodes qui les caractérisent.
- Savoir choisir une structure de données adaptée à la situation à modéliser.
Fiche de cours