NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

Identifiant Mot de passe

Programmation orientée objet
Récursivité
Base de données et langage SQL
Les listes chainées
Piles et Files
Les dictionnaires
Protocoles de routage
Les arbres
Sécurisation des données
Diviser pour régner
Les processus
Les systèmes sur puce
Recherche textuelle
Les Graphes
L'intelligence artificielle
Epreuves pratiques et écrites du Bac
Le grand oral

Algorithmes de référence de première
Mise au point des programmes
Algorithme de recherche dichotomique
Algorithmes de tri par insertion
Fractales récursives
Algorithmes de tri par sélection
Base de données et langage SQL
Modularité

Devoir maison n°1
Les 48 sujets de l'épreuve pratique 2024
Les 45 sujets de l'épreuve pratique 2023

D
É
C
O
N
N
E
C
T
É

Structures de données, partie 2 - PILES et FILES

1. Introduction

Les piles et les files permettent toutes deux de stocker un ensemble d'éléments, et fournissent des opérations permettant d'ajouter ou de supprimer des éléments un par un. Dans chacune de ces deux structures, les éléments sont retirés dans un ordre bien précis.

Remarque.

Dans ce qui suit, nous allons faire des piles et des files d'éléments d'un type arbitraire que nous noterons T.

Les structures de pile et de file sont munies au minimum des quatre opérations suivantes :

créer une structure vide,
tester si la structure est vide,
ajouter un élément,
retirer et obtenir un élément.

Ces quatre opérations forment l'interface minimale de ces deux structures.

(Rappel : l'interface est l'ensemble des opérations qui permettent d'interagir avec la structure.)

2. Pile

2.1 Type abstrait

Dans une pile (stack en anglais), on empile les données comme une pile de livres

l'élément retiré est l'élément le plus récent de la pile.

On appelle cette mécanique LIFO : Last In First Out (dernier entré premier sorti en français)

Définition

Une pile est une collection ordonnée d'éléments, accompagnée de différentes opérations parmi lesquelles :

Pile() -> Pile(T) : crée et retourne une pile vide
est_vide(self : Pile(T)) -> bool : retourne True si la pile est vide et False sinon
empiler(self : Pile(T), elt : T) -> None : ajoute elt au sommet de la pile
depiler(self : Pile(T)) -> T : retire et retourne l'élément au sommet de la pile

2.2 Mise en œuvre

2.2.1 Avec une liste chaînée

Une façon de mettre en œuvre une pile est d'utiliser une liste chaînée. Pour cela, nous allons utiliser une classe Element, définie de la façon suivante :

def est_vide(self):
        """self(Pile) -> bool
        Précondition : aucune
        Retourne True si le paramètre est vide et False sinon"""
        return self.sommet is None
        
    def empiler(self, elt):
        """self(Pile), T -> None
        Précondition : aucune
        Empile elt au sommet de self"""
        nouvel_element = Element(elt)
        nouvel_element.suivant = self.sommet
        self.sommet = nouvel_element
        
    def depiler(self):
        """self(Pile) -> T
        Précondition : self est non vide
        Depile et retourne un élément du sommet de self"""
        if self.est_vide():
            raise IndexError("Impossible de retirer un élément d'une pile vide")
        element = self.sommet.valeur
        self.sommet = self.sommet.suivant   
        return element

Exercice 1:

1) On considère les instructions ci-dessous. Donner le contenu de la pile obtenue à chaque étape.

p = Pile () # | ? | p.empiler (42) # | ? | p.empiler (10) # | ? | p.empiler (5) # | ? | p.depiler () # | ? | p.depiler () # | ? | p.empiler (1) # | ? |

2.2.2 Avec le type list de Python

Une autre façon de mettre en œuvre une pile est d'utiliser le type list de Python. En effet, le type list inclut :

une méthode append qui prend en paramètre un élément et l'ajoute à la fin d'un objet de type list
une méthode pop qui prend en paramètre un entier i, retire l'élément d'indice i d'un objet de type list et le retourne. Si on ne donne pas de paramètre à la méthode pop, elle retire et retourne par défaut le dernier élément de l'objet.

Voir exercice 3 pour les détails.

2.2.3 Avec un tableau

Si on veut mettre en œuvre une pile bornée c'est-à-dire contenant un nombre d'éléments inférieur ou égal à un entier n, on peut utiliser un tableau de taille n. Il suffit alors de garder en mémoire l'indice correspondant au sommet de la pile.

Voir exercice 4 pour les détails.

3 File

3.1 Type abstrait

Dans une File (queue an anglais), l'élément retiré est l'élément le plus ancien de la liste. On appelle cette mécanique FIFO : First In First Out (premier entré premier sorti en français).

On illustre souvent cette mécanique par une file d'attente, par exemple dans un magasin à file unique : la personne entrée en premier dans la file (celle qui attend depuis le plus longtemps) sera la première à passer à la caisse.

Définition

Une file est une collection ordonnée d'éléments, accompagnée de différentes opérations parmi lesquelles :

File() -> File(T) : crée et retourne une file vide
est_vide(self : File(T)) -> bool : retourne True si la file est vide et False sinon
enfiler(self : File(T), elt : T) -> None : ajoute elt en queue de la file
defiler(self : File(T)) -> T : retire et retourne l'élément en tête de la file

3.2 Mise en œuvre

3.2.1 Avec une liste chaînée

En reprenant la classe Element ci-dessus, la classe File se déffinit de la façon suivante :

class Element: def __init__(self, elt): """self, T -> None Précondition : aucune Initialise un objet de classe Element""" self.valeur = elt # valeur de l'élément self.suivant = None # pointeur vers l'élément suivant class File: def __init__(self): """self(File) -> None Précondition : aucune Initialise un objet de classe File à la file vide""" self.tete = None self.queue = None def est_vide(self): """self(File) -> bool Précondition : aucune Retourne True si le paramètre est vide et False sinon""" return self.tete is None def enfiler(self, elt): """self(File), T -> None Précondition : aucune Ajoute elt en queue de self""" nouvel_element = Element(elt) if self.est_vide(): self.tete = nouvel_element else: self.queue.suivant = nouvel_element self.queue = nouvel_element def defiler(self): """self(Pile) -> T Précondition : self est non vide Retire et retourne un élément en tête de self""" if self.est_vide(): raise IndexError("Impossible de retirer un élément d'une file vide") else: element = self.tete.valeur self.tete = self.tete.suivant return element

3.2.2 Avec le type list de Python

Une autre façon de mettre en œuvre une pile est d'utiliser le type list de Python, en utilisant les méthodes append et pop. Voir exercice 3 pour les détails.

3.2.3 Avec un tableau

Si on veut mettre en œuvre une file bornée c'est-à-dire contenant un nombre d'éléments inférieur ou égal à un entier n, on peut utiliser un tableau de taille n. Il suffit alors de garder en mémoire l'indice correspondant à la tête et à la queue de la file. Voir exercice 4 pour les détails.

Exercice 2

1) On considère les instructions ci-dessous. Donner la file obtenue à chaque étape.

f = File() # | ? | f.enfiler (42) # | ? | f.enfiler (10) # | ? | f.enfiler (10) # | ? | f.enfiler (5) # | ? | f.defiler () # | ? | f.defiler () # | ? | f.enfiler (1) # | ? |

2) Donner la structure la plus appropriée entre liste, pile et file pour effectuer les actions suivantes :

stocker dans l'historique d'un logiciel les actions effectuées et disposer d'une commande pour annuler l'action précédente :
Pile File Liste

stocker dans un navigateur web les pages visitées et disposer d'une commande pour aller à la page précédente ou revenir à la page suivante :
Pile File Liste

gérer les fichiers envoyés à une serveur d'impression :
Pile File Liste

gérer les appels récursifs d'une fonction :
Pile File Liste

4. Exercices

Exercice 3

Le but de cet exercice est de mettre en œuvre les piles et les files en utilisant le type list de Python et en faisant appel aux méthodes append et pop.

1) Écrire en Python une classe Pile avec toutes les méthodes décrites dans la partie 2. Les objets de la classe Pile auront un unique attribut contenu de type list. Le sommet de la pile sera le dernier élément de cet attribut.

2) Écrire en Python une classe File avec toutes les méthodes décrites dans la partie 3. Les objets de la classe File auront un unique attribut contenu de type list. La tête de la file sera le premier élément de cet attribut et la queue de la file sera le dernier élément de cet attribut.

Exercice 4

Le but de cet exercice est de mettre en œuvre les piles et les files bornées en utilisant un tableau de taille fixe. Dans tout cet exercice, les structures contiendront au plus 100 éléments.

S'il y a un dépassement de capacité de la pile, vous l'indiquerez par une instruction raise.

1) Écrire en Python une classe Pile avec toutes les méthodes décrites dans la partie 2.

Les objets de la classe Pile auront pour attributs :

contenu de type list de taille 100 dont tous les éléments valent initialement None,
indice_sommet représentant l'indice du sommet de la pile et valant initialement -1, ce qui correspond à une pile vide.

2) Écrire en Python une classe File avec toutes les méthodes décrites dans la partie 3. Les objets de la classe File auront pour attributs :

contenu de type list de taille 100 dont tous les éléments valent initialement None,
indice_tete représentant l'indice de la tête de la file et valant initialement -1, ce qui correspond à une file vide,
indice_queue représentant l'indice de la queue de la file et valant initialement -1.

Attention, lorsqu'on atteint la fin du tableau contenu, on repart au début.

Exercice 5.

1) Dans une chaîne bien parenthésée, à chaque parenthèse ouvrante correspond une unique parenthèse fermante. Écrire une fonction indice_ouvrante qui :

prend en paramètre une chaîne de caractères chaine et un indice f correspondant à une parenthèse fermante,
retourne l'indice de la parenthèse ouvrante associée.
la fonction utilisera une pile qui contiendra les indices des parenthèses ouvrantes, qu'on dépilera dès qu'on rencontre une parenthèse fermante
la fonction retournera le sommet de la pile

Exemple :

indice_ouvrante("cos(2*(x+1)/2)*(3+x)",13) doit retourner 3

2) Dans cette question, on considère une chaîne contenant des parenthèses et des crochets. La chaîne est bien parenthésée si à chaque symbole ouvrant correspond un symbole fermant, et si il n'y a pas d'entrecroisement. Par exemple ([3 + 2] * 5 + 8) * 2 est bien parenthésée et ([3 + 2) * 5 + 8] * 2 ne l'est pas.

Ajouter une fonction bien_parenthesee utilisant une pile et qui :

prend en paramètre une chaîne de caractères chaine,
retourne True si la chaîne est bien parenthésée et False sinon.

Exercice 6.

Dans l'écriture polonaise inverse d'une expression arithmétique, on place l'opérateur après ses opérandes. Par exemple l'expression polonaise inverse : "1⏎ 2⏎ 3 * + 4 *" correspond à l'expression en notation classique : (1 + 2 * 3) * 4 dont la valeur est 28.

La lecture d'une expression en notation polonaise inverse se fait facilement à l'aide d'une pile en effectuant les opérations suivantes pour chaque élément e de l'expression :

si e est un nombre, l'empiler comme entier,
si e est un opérateur, on dépile les deux opérandes, on effectue l'opération, on empile le résultat.

Exemple d'évolution de la pile pour le calcul "1 2 3 * +"

Écrire une fonction qui :

prend en paramètre une chaîne de caractères correspondant à une expression en notation polonaise inverse contenant uniquement des additions, des multiplications et des nombres entiers et dont les éléments sont séparés par des espaces (la méthode chaine.split(" ") permet de transformer une chaine de caractères séparée par un espace, en une liste de str),
retourne la valeur de l'expression.

Epreuve écrite de NSI (Centres Etrangers Afrique 1) - Bac 2023 - Exercice 3

# Bac NSI Afrique 2023

from random import *
import time,os

def ajout(f):
    couleurs=("bleu","rouge","jaune","vert")
    indice=randint(???,???)
    enfiler(???,???)
    return f

def vider(?):
    """vide la file sans la renvoyer"""
    ???

def affiche_seq(sequence):
    stock=creer_file_vide()
    ajout(sequence)
    while not est_vide(sequence):
        c=???
        ???
        time.sleep(0.5)
        ???
    while ???:
        ???

def tour_de_jeu(sequence):
    # n=len(sequence)   # affichera le score final
    ?ZONEA?
    stock=creer_file_vide()
    while not est_vide(sequence):
        c_joueur=saisie_joueur()
        c_seq=?ZONE B?
        if c_joueur ??? c_seq:
            ?ZONE C?
        else:
            ?ZONE D?
            # return n    #retourne le score

?ZONE E?
        ?ZONE F?

# Fonctions hors épreuve
def debut():
    for i in range(3,0,-1):
        print(i)
        time.sleep(1)
        os.system("clear")
    time.sleep(1)

def affichage(couleur):
    print(couleur)
    time.sleep(0.5)
    os.system("clear")
    
def creer_file_vide():
    """renvoie une file vide"""
    return(list())

def est_vide(f):
    """renvoie True si f est vide, False sinon"""
    return len(f)==0

def enfiler(f,elt):
    """ajoute element en queue de f"""
    f.insert(0,elt)

def defiler(f):
    """retire l'élément en tête de f et le renvoie"""
    return f.pop()

def taille(f):
    """renvoie le nombre d'éléments de f"""
    return len(f)

def saisie_joueur():
    c= input("couleur : ")
    os.system("clear")
    return c

# Début du jeu
debut()
sequence=creer_file_vide()
time.sleep(1)

tour_de_jeu(sequence)
while not est_vide(sequence):
    n=tour_de_jeu(sequence)
    time.sleep(1)
    
print("Score : "+str(n))

Copiez-coller votre code dans cette application pour le tester : https://trinket.io/

Fond : Texte : Tables : Thème du langage:

Contenu sous licence CC BY-NC-SA 3.0
Amandine SCHREK 31/10/2022
Mise à jour le 15/03/2023