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(ma_pile) renvoie vrai si la pile pile est vide |
| Insérer un nouvel élément e au sommet de la pile Pile(push) | empiler(ma_pile,e) |
| Enlever et retourner l'élément au sommet de la pile Pile (pop) | depiler(ma_pile) |
| Compter le nombre d'éléments présents dans une pile Pile | taille(ma_pile) |
| Créer une nouvelle pile ma_pile_2 à partir d'un élement x d'une pile existante ma_pile | ma_pile_2 = cons(x,ma_pile) |
Entraînement 2 :
Donner le contenu de ma_pile et de temp après cette série d'instruction :
ma_pile = creer_pile_vide()
empiler(ma_pile,3)
empiler(ma_pile,2)
temp = depiler(ma_pile)
empiler(ma_pile,5)
empiler(ma_pile,7)
empiler(ma_pile,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, elt):
"""Place l'élément elt au sommet de la pile"""
self.contenu.append(elt)
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()
pile_1 = Pile()
pile_1.empiler(2)
pile_1.est_vide()
pile_1.empiler(1)
pile_1.empiler(2)
pile_1.empiler(3)
print(pile_1.contenu)
print(pile_1.est_vide())
print(pile_1.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 ma_file vide | creer_file_vide() |
| tester si une file est vide | est_vide(ma_file) renvoie vrai si la pile pile est vide |
| Enfiler un nouvel élément elt : le mettre en dernier(enqueue) | enfiler(ma_file,elt) |
| Défiler un élément, le premier (le supprimer) (dequeue) | defiler(ma_file) |
| Afficher le nombre d'éléments présents dans une file ma_file | taille(ma_file) |
Entraînement 3 :
Donner le contenu de ma_file et de temp après cette série d'instruction :
ma_file = creer_file_vide()
enfiler(ma_file,3)
enfiler(ma_file,2)
temp = defiler(ma_file)
enfiler(ma_file,5)
enfiler(ma_file,7)
enfiler(ma_file,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 une fonction qui vide une file
Entraînement 7 : Exercices extraits de sujet de bac
- Jeu de la poussette : D'après 2022, Métropole, J2, Ex. 2
- Vérification syntaxique de parenthèses ou de balises : D'après 2022, Métropole, J1, Ex. 1
- Pile, file, programmation Python D'après l'exercice 5 du sujet Amérique du Nord J1 - 2021
- Traitement d'une pile : D'après 2022, Polynésie, J1, Ex. 4
- Traitement d'une pile D'après 2021, Centres Étrangers, J1, Ex. 5
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