Source : Scratch Wiki en français
Un pile est une structure de données concrète, associé au type abstrait « DEPS ».
SD concrète
- nom
- pile
- nom anglais
- stack
- type
- séquentielle
Structure de données concrète.
Informations supplémentaires
Utilisée pour l'organisation de la mémoire matérielle, la récursivité, la mise en place d'historique à court terme ou encore un système « Annuler / Rétablir »
Définition
Une pile est basée sur la structure de données abstraite « DEPS » (Dernier Entré, Premier Sorti), une structure séquentielle permettant de contenir des objets, pouvant être empilée (ajout d'un objet) et dépilée (retrait d'un objet).
L'exemple d'une pile d’assiette est généralement utilisé pour illustrer le fonctionnement des piles : la dernières assiette empilée est la première dépilée.
Implémentation
Voici un tutoriel expliquant comment implémenter un pile en Scratch.
Implémentation naïve
L'implémentation suivante est rudimentaire et adaptée aux usages simples de la structure de données concrète.
définir pile.vider mettre [pile v] à [nil] supprimer tous les éléments de la liste [pile v] définir pile.empiler (valeur) mettre [pile v] à [nil] ajouter (valeur) à [pile v]::list définir pile.regarder mettre [pile v] à (élément [1] de [pile v]) définir pile.dépiler mettre [pile v] à (élément [1] de [pile v]) supprimer l'élément (longueur de [pile v]) de [pile v] définir pile.est vide ? mettre [pile v] à <(longueur de [pile v]) = [0]>
Complexité
On note n la longueur de la file. Voici la complexité des primitives attendues :
- Complexité (enfiler) :
O(1)
. - Complexité (défiler) :
O(1)
.
L'implémentation naïve est satisfaisante.
Voir aussi
- Pile sur Wikipédia ;
- type abstrait DEPS sur Wikipédia ;
- Structure de données et type abstrait ;
- Langage Scratch
- Tutoriels
