Pile

Introduction

Structure de données	Implémentation
Tableau : cases mémoires au nombre fixé dans lesquelles on met des éléments indexés, de même type, accessible et modifiable par leurs indexes.	Type list de python ou type array de numpy
Tableau Dynamiques : tableau de taille variable	Type list de python ou type vector de numpy
= Interface (définie par les spécifications)	= Implémentation (définie par la documentation)

Les tableaux sont des structures de données séquentielles. On spécifie une structure de données par son interface. Chaque fonction d'une interface possède :

• un nom
• une liste de paramètres (avec les types)
• la spécification de la fonction (ce qu'elle fait)

Écrire une fonction avec ses paramètres et les types associés revient à écrire une signature de fonction. Par exemple, def magie(m : int, k : list[bool]) -> bool: est une signature

Notion de pile

Définition

Une pile est une structure de données que l'on manipule comme une pile d’assiettes. On ne peux pas exécuter d’opérations sur ses éléments, et on ne peut retirer que celui qui est en haut.

On abrège ce type de structure LIFO (Last In, First Out).

L'interface de la pile est la suivante :

• p = pile() pour créer une pile
• p.estVide() pour tester si la pile est vide
• p.empiler(e: Class) pour ajouter un élément dans la pile (en haut)
• p.depiler() -> Class pour prendre le premier élément de la pile

Bonus : Les types avec des majuscules sont, par conventions, des types créer par l'utilisateur/une extension. En python, ce n'est pas obligataire, mais beaucoup de langages le demandent (Astro, React, Java...)

Note

Les nom des fonctions/méthodes peuvent changer d'un sujet à l'autre

Fonctions de base

Warning

Dans des exercices sur les piles, seules ces méthodes ne peuvent êtres utilisés, et pas de tableaux.

Sommet

def sommet(p: Pile) -> int:
  a = p.depiler()
  p.empiler(a)
  return a

La fonction a un coût temporel de 2 () et un coût spatial de 1 ()

Copie

def copie(p: Pile) -> Pile:
  res = pile()
  temp = pile()
  # Transférer les éléments de p vers temp (inverser l'ordre)
  while not p.estVide():
    e = p.depiler()
    temp.empiler(e)
  # Restaurer p et construire la copie res
  while not temp.estVide():
    e = temp.depiler()
    p.empiler(e)
    res.empiler(e)
  return res

Pour une pile à n éléments, la fonction a un coût temporel de et un coût spatial de (car on crée, in fine, n nouvelles variables primaires que l'on déplace).

Hauteur d'une pile

Définition

On appelle hauteur d'une pile le nombre d'éléments qu'elle continent.

Définition

On appelle hauteur d'une pile le nombre d'éléments qu'elle contient.

Itératif

def haut_it(p: Pile) -> int:
  cnt = 0
  temp = pile()
  while not p.estVide():
    e = p.depiler()
    temp.empiler(e)
    cnt += 1
  while not temp.estVide():
    p.empiler(temp.depiler())
  return cnt

Récursif

def haut_rec(p: Pile) -> int:
  if p.estVide():
    return 0
  else:
    e = p.depiler()
    h = haut_rec(p)
    p.empiler(e)
    return 1 + h

La fonction a un coût linéaire dans les deux cas.