Les piles et les files

Numérique et sciences informatiques

donnees

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.

pile
Pile : LIFO

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.

file
File : FIFO

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