Piles et files

Cours NSI Terminale

Les listes chaînées, les piles et les files

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
• 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
• p_empile(pile, v)
  • prend en paramètre une pile pile et une valeur v
  • empile la valeur v
  • ne renvoie rien

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

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]