Piles et files
Cours NSI Terminale
Les piles
On va commencer ce TP par la manipulation des piles, plus faciles à appréhender, et on terminera par la manuipulation des listes chaînées. Rappelons tout d'abord la notion de piles répondant à la règle LIFO : dernier entré, premier sorti.
Description de la structure
Pour stocker les données dans notre pile, nous utiliserons un tableau python (objet list). Le dernier élément du tableau sera le sommet de la pile. Seul cet élément sera visible.
Exemple : Si la pile est représentée en mémoire par le tableau [2, 3, 5, 8]
, le sommet de la pile sera 8
. Si je dépile le 8, la pile deviendra [2, 3, 5]
et le sommet de la pile sera 5. Une fois tous les éléments dépilés, la pile sera vide et représentée par []
.
A vous de jouer
Vous allez devoir implémenter les fonctions
-
p_valeur(pile)
- prend en paramètre une pile
pile
- renvoie le sommet de la pile ou
None
si la pile est vide
- prend en paramètre une pile
-
p_depile(pile)
- prend en paramètre une pile
pile
- dépile le dernier élément saisi
- renvoie la valeur dépilée ou
None
si la pile est vide
- prend en paramètre une pile
-
p_empile(pile, v)
- prend en paramètre une pile
pile
et une valeurv
- empile la valeur
v
- ne renvoie rien
- prend en paramètre une pile
def p_valeur(pile):
"""- prend en paramètre une pile
- renvoie le sommet de la pile
Exemple :
>>> p_valeur([2, 3, 5])
>>> 5
>>> p_valeur([])
>>> None
"""
# YOUR CODE HERE
raise NotImplementedError()
assert p_valeur([]) is None
assert p_valeur([2, 3, 5]) == 5
def p_depile(pile):
"""- prend en paramètre une pile
- dépile le dernier élément saisi
- renvoie le sommet de la pile
Exemple :
>>> pile =[2, 3, 5]
>>> p_depile([2, 3, 5])
>>> pile
>>> [2, 3]
"""
# YOUR CODE HERE
raise NotImplementedError()
p=[2, 3, 5]
assert p_depile(p) == 5
assert p == [2, 3]
assert p_depile([]) is None
def p_empile(pile, v):
"""- prend en paramètre une pile et une valeur v
- empile la valeur v
Exemple :
>>> pile = [2, 3]
>>> p_empile(pile, 5)
>>> pile
>>> [2, 3, 5]
"""
# YOUR CODE HERE
raise NotImplementedError()
pile = [2, 3]
p_empile(pile, 5)
assert pile == [2, 3, 5]
Les files
Rappelons la notion de files répondant à la règle FIFO : premier entré, premier sorti.
Description de la structure
Pour stocker les données dans notre file, nous utiliserons un tableau python (objet list).
- le dernier élément du tableau sera l'avant de la file. Seul cet élément sera visible
- le premier élément du tableau sera l'arrière de la file
Exemple : Si la file est représentée en mémoire par le tableau [2, 3, 5, 8]
, l'avant de la file sera 8
et l'arrière de la file sera 2. Si on ajoute 1 à l'arrière de la file, celle-ci contiendra [1, 2, 3, 5, 8]
. Une fois tous les éléments dépilés, la file sera vide et représentée par []
.
A vous de jouer
Vous allez devoir implémenter les fonctions
-
f_valeur(file)
- prend en paramètre une file
- renvoie la valeur à l'avant de la file ou
None
si la file est vide
-
f_defile(file)
- prend en paramètre une file
- défile l'élément situé à l'avant de la file
- renvoie la valeur défilée ou
None
si la file est vide
-
f_emfile(file, v)
- prend en paramètre une file et une valeur
v
- emfile la valeur
v
à l'arrière de la file - ne renvoie rien
- prend en paramètre une file et une valeur
def f_valeur(file):
"""- prend en paramètre une file
- renvoie la valeur à l'avant de la file ou None si la file est vide
Exemple :
>>> f_valeur([2, 3, 5])
>>> 5
>>> f_valeur([])
>>> None
"""
# YOUR CODE HERE
raise NotImplementedError()
assert f_valeur([]) is None
assert f_valeur([2, 3, 5]) == 5
def f_defile(file):
"""- prend en paramètre une file
- défile l'élément situé à l'avant de la file
- renvoie la valeur défilée ou None si la file est vide
Exemple :
>>> file = [2, 3, 5, 8]
>>> f_defile(file)
>>> 8
>>> file
>>> [2, 3, 5]
"""
# YOUR CODE HERE
raise NotImplementedError()
file = [2, 3, 5, 8]
assert f_defile(file) == 8
assert file == [2, 3, 5]
def f_enfile(file, v):
"""- prend en paramètre une file et une valeur v
- enfile la valeur v à l'arrière de la file
Exemple :
>>> file = [2, 3, 5, 8]
>>> f_enfile(file, 1)
>>> file
>>> [1, 2, 3, 5, 8]
"""
# YOUR CODE HERE
raise NotImplementedError()
file = [2, 3, 5, 8]
f_enfile(file, 1)
assert file == [1, 2, 3, 5, 8]