Structures de données
Structures de données est une simulation interactive gratuite de StudyFi Lab. Elle fonctionne directement dans le navigateur, sans inscription ni installation.
Piles, files, listes, arbres et graphes
Expériences
Pile
Une pile fonctionne comme une pile d’assiettes : on ajoute (push) et on retire (pop) seulement au sommet, donc le dernier entré est le premier sorti (LIFO). Le pointeur top marque le sommet ; push et pop coûtent O(1). L’annulation d’un éditeur, le bouton Précédent du navigateur et les appels de fonctions (pile d’appels) l’utilisent.
Essaie ceci: Empile 1, 2, 3 puis fais trois pop : les nombres sortent dans l’ordre inverse. Essaie ensuite un neuvième push.
File
Une file fonctionne comme la queue à une caisse : les nouveaux éléments arrivent à l’arrière (enqueue, pointeur rear) et partent par l’avant (dequeue, pointeur front), donc premier entré, premier sorti (FIFO). Dans un tableau, on la range en tampon circulaire : les deux pointeurs reviennent de la dernière case à la case 0, donc enqueue et dequeue coûtent O(1). Les files gèrent l’imprimante, les requêtes d’un serveur et la mise en mémoire tampon des vidéos.
Essaie ceci: Active la vue circulaire, enfile six nombres, défile-en quatre et enfile-en quatre autres : rear passe de la case 7 à la case 0.
Liste chaînée
Chaque nœud contient une valeur et un lien next vers le nœud suivant ; le dernier pointe vers null et la liste commence au pointeur head. Insérer en tête coûte O(1), mais atteindre la position i ou une valeur cherchée oblige à parcourir nœud par nœud : O(n). Contrairement à un tableau, rien n’est décalé, on refait seulement les liens ; c’est ainsi que fonctionnent les playlists, les historiques et les listes de mémoire libre.
Essaie ceci: Cherche la dernière valeur et compte les pas du pointeur, puis insère en tête : c’est toujours un seul pas.
Arbre binaire de recherche
À chaque nœud, les valeurs plus petites vont à gauche et les plus grandes à droite. Rechercher et insérer suivent donc un seul chemin depuis la racine et coûtent O(h), où h est la hauteur de l’arbre ; pour un arbre équilibré h ≈ log₂ n. La suppression a trois cas : une feuille disparaît, un nœud à un enfant est remplacé par cet enfant, et un nœud à deux enfants prend la valeur de son successeur infixe. Le parcours infixe donne les valeurs triées ; des arbres semblables font tourner les index des bases de données.
Essaie ceci: Supprime la racine : elle a deux enfants, tu verras donc la recherche du successeur. Essaie ensuite « Insérer des valeurs triées » : l’arbre dégénère en liste et la hauteur monte à n.
Graphe : BFS et DFS
Le parcours en largeur (BFS) prend les nœuds dans une file : il visite d’abord tous les voisins du départ, puis leurs voisins, couche par couche, ce qui donne le plus court chemin en nombre d’arêtes. Le parcours en profondeur (DFS) prend les nœuds dans une pile et va le plus loin possible avant de revenir. Les deux visitent chaque nœud et chaque arête une fois : O(V + E). BFS sert au calcul d’itinéraire et aux « amis d’amis », DFS résout des labyrinthes et détecte des cycles.
Essaie ceci: Avance pas à pas depuis le nœud 0 et compare la file à la pile. Choisis ensuite le nœud 7 comme départ : l’ordre de visite change complètement.
Questions fréquentes
Qu’est-ce que Structures de données ?
Structures de données est une simulation interactive gratuite de StudyFi Lab. Elle fonctionne directement dans le navigateur, sans inscription ni installation. Piles, files, listes, arbres et graphes
Structures de données est-il gratuit ?
Oui. Structures de données est entièrement gratuit. Il fonctionne dans le navigateur sur ordinateur, tablette et téléphone, sans compte.
Que puis-je explorer dans Structures de données ?
Pile, File, Liste chaînée, Arbre binaire de recherche, Graphe : BFS et DFS.
Que montre l’expérience « Pile » ?
Une pile fonctionne comme une pile d’assiettes : on ajoute (push) et on retire (pop) seulement au sommet, donc le dernier entré est le premier sorti (LIFO). Le pointeur top marque le sommet ; push et pop coûtent O(1). L’annulation d’un éditeur, le bouton Précédent du navigateur et les appels de fonctions (pile d’appels) l’utilisent.
Que montre l’expérience « File » ?
Une file fonctionne comme la queue à une caisse : les nouveaux éléments arrivent à l’arrière (enqueue, pointeur rear) et partent par l’avant (dequeue, pointeur front), donc premier entré, premier sorti (FIFO). Dans un tableau, on la range en tampon circulaire : les deux pointeurs reviennent de la dernière case à la case 0, donc enqueue et dequeue coûtent O(1). Les files gèrent l’imprimante, les requêtes d’un serveur et la mise en mémoire tampon des vidéos.
Tu révises pour un contrôle ?
Importe tes notes et StudyFi les transforme en fiches, tests et podcasts.