Types de Données Abstraits — pile, file, liste chaînée
Introduit| English | Sens |
|---|---|
| queue/kjuː/ | fichier |
| push/pʊʃ/ | empilement |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | type de données abstrait |
| stack/stæk/ | pile |
| linked list/lɪŋkt lɪst/ | liste chaînée |
| LIFO/ˈlaɪfəʊ/ | LIFO (dernier entré, premier sorti) |
| pop/pɒp/ | dépilement |
| pointer/ˈpɔɪntə/ | pointeur |
| FIFO/ˈfaɪfəʊ/ | FIFO (premier entré, premier sorti) |
| enqueue/enˈkjuː/ | enfilage |
| dequeue/diːˈkjuː/ | défilage |
| node/nəʊd/ | nœud |
| traverse/trəˈvɜːs/ | parcours |
Le bouton Retour et la file d'impression
- Chaque page visitée est poussée sur une pile ; le bouton Retour retire le dessus. La page laissée le plus récemment est la première à la quelle on revient.
- Dans le couloir, une imprimante traite les tâches dans l'ordre d'arrivée. Le document envoyé en premier sort en premier, peu importe la taille de ceux derrière lui.
- Deux structures, règles opposées, et vous utilisez les deux avant la pause. Aucune ne dit comment elles sont stockées ; chacune dit seulement ce que font leurs opérations.
- C'est un type de données abstrait 抽象数据类型. Cette leçon porte sur les trois que le programme nomme, les opérations sur chacun, et comment justifier l'un pour une situation donnée.
Ce qu'est un TDA
- Un type de données abstrait (TDA) est un ensemble de données accompagné d'un ensemble d'opérations sur ces données. Cette phrase unique est la définition à un point.
- Il est défini par ce que font les opérations, pas par comment les données sont stockées. L'implémentation est cachée, donc elle peut changer sans affecter le code qui l'utilise.
- Une pile, une file, une liste chaînée, un arbre binaire et un tableau sont tous des TDAs.
Un Type de Données Abstrait (ADT) est défini par :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Un TAD spécifie les opérations (l'interface) ; l'implémentation est cachée et peut changer librement.
La pile
- Une pile 栈 est une liste où les éléments sont ajoutés et retirés à la même extrémité, le sommet, donc le dernier élément ajouté est le premier retiré : LIFO 后进先出.
- Opérations : push 入栈 ajoute au sommet, pop 出栈 retire du sommet, peek regarde le sommet, et teste pour vide et plein.
- Usages : historique d'annulation, bouton Retour, adresses de retour des appels de fonction, vérification des parenthèses, backtrack.

Tout se passe au sommet
Dans quel ordre fonctionne une pile ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Une pile est LIFO : l'élément le plus récemment empilé est le premier à être dépiler.
Exemple résolu : tracer la pile
- Une pile contient, du bas vers le haut,
'P' 'N' 'Z' 'X' 'Y' 'W'; le pointeur supérieur est à'W'. Les opérationsPOP,POP,PUSH 'A',PUSH 'B',POPsont effectuées. Que contient la pile, et où se trouve le pointeur ? - Les deux pops retirent
'W'puis'Y'. Les pushes placent'A'puis'B'à leur place. Le dernier pop retire'B'. - La pile contient
'P' 'N' 'Z' 'X' 'A', avec le pointeur à'A'. L'item resté le plus longtemps sur la pile est le fond,'P'; cinq autres pops sont possibles, et une sixième serait une erreur, c'est pourquoi pop teste pour vide d'abord.
Une pile contient P N Z X Y W (le sommet est W). Après POP, POP, PUSH 'A', PUSH 'B', POP, quel élément est au sommet ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
W et Y sont déspilés, A puis B sont empilés, B est déspilé. Le sommet est A, au-dessus de X.
La file
- Une file 队列 est une liste où les éléments sont ajoutés à l'arrière et retirés de l'avant, donc le premier élément ajouté est le premier retiré : FIFO 先进先出.
- Opérations : enqueue 入队 ajoute à l'arrière, dequeue 出队 retire de l'avant, et teste pour vide et plein.
- Usages : spooling d'impression, tampons clavier, ordonnancement, clients dans un magasin, recherche en largeur.

Entrer par derrière, sortir par devant
Piles, files & listes chaînées
LIFO vs FIFO
Une pile est last-in-first-out (dernier entré, premier sorti) ; push et pop se font au même bout (le sommet).
Une file est premier-entré-premier-sorti : les éléments sont retirés du ______ et ajoutés à l'arrière.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
FIFO : défiler depuis le devant, enfiler à l'arrière — comme une file d'attente.
Exemple résolu : décrire l'ajout et le retrait d'une file
- Ajouter : vérifier que la file n'est pas pleine ; stocker l'élément à la position donnée par le pointeur arrière ; déplacer le pointeur arrière (et ajouter un au compteur).
- Retirer : vérifier que la file n'est pas vide ; lire l'élément au pointeur avant ; déplacer le pointeur avant (et soustraire un au compteur).
- Énoncer la convention utilisée : si le pointeur arrière marque la prochaine case libre, stocker d'abord puis déplacer ; s'il marque le dernier élément, déplacer d'abord puis stocker. Les deux valent des points, tant que vous êtes cohérent.
Mettez les étapes d'ajout d'un élément dans une file dans l'ordre (le pointeur arrière marque la prochaine case libre).
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
La vérification vient en premier ; puis stocker, puis déplacer, selon cette convention. Dites quelle convention vous utilisez.
La liste chaînée
- Une liste chaînée 链表 est une liste où chaque nœud 节点 contient un élément de données et un pointeur 指针 vers le nœud suivant, avec un pointeur de départ vers le premier nœud. Le pointeur du dernier nœud est un sentinelle tel que
NULL. - Opérations : insertion, suppression, recherche, et traversée 遍历, suivant les pointeurs de la tête pour visiter tous les nœuds dans l'ordre.
- Avantage sur un tableau : insérer ou supprimer est peu coûteux, il suffit de rebrancher les pointeurs, et la liste grandit selon les besoins. Inconvénient : pas d'accès aléatoire ; atteindre le dixième nœud signifie suivre neuf pointeurs.

Une valeur et une flèche, répété
Une liste chaînée : des nœuds joints par des pointeurs
Chaque nœud stocke une valeur et un pointeur vers le nœud suivant. Insérer ou supprimer ne fait que relier les pointeurs — aucun élément ne se décale, contrairement à un tableau.
Chaque nœud d'une liste chaînée contient :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Un nœud stocke sa valeur ainsi qu'un pointeur (référence) vers le nœud suivant ; la tête marque le début, NULL la fin.
Une liste chaînée permet des insertions/suppressions peu coûteuses (simple rebranchement des pointeurs) mais un accès aléatoire lent (il faut suivre les pointeurs depuis la tête).
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
C'est le compromis tableau-vs-liste : les tableaux offrent un accès O(1) par indice ; les listes permettent des insertions/suppressions peu coûteuses.
Exemple résolu : ajouter un nœud dans l'ordre
- Décrire comment une nouvelle valeur est insérée dans une liste chaînée maintenue par ordre croissant. [4]
- Parcourir la liste depuis la tête, en suivant les pointeurs, jusqu'à ce que le nœud avant la position soit trouvé : le dernier nœud dont la valeur est inférieure à la nouvelle.
- Prendre un nœud libre et stocker la nouvelle valeur dedans. Définir le pointeur du nouveau nœud sur l'adresse à laquelle le nœud précédent pointe actuellement.
- Puis définir le pointeur du nœud précédent sur le nouveau nœud. Si la nouvelle valeur doit être placée au début, c'est le pointeur de tête qui change alors.
Mettez les étapes d'insertion d'une valeur dans une liste chaînée ordonnée dans l'ordre.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Trouver, remplir, pointer le nouveau nœud vers l'avant, puis rebrancher le nœud précédent. Inverser les deux dernières étapes fait perdre le reste de la liste.
Justifier le choix
- Les éléments doivent être traités dans l'ordre d'arrivée, impression, frappe au clavier, clients : une file, car elle est premier entré, premier sorti.
- Le dernier élément doit être traité en premier, annuler, revenir en arrière, appels imbriqués : une pile, car elle est dernier entré, premier sorti.
- Les éléments sont fréquemment insérés ou supprimés au milieu d'une collection ordonnée, et sa taille est inconnue : une liste chaînée, car seuls les pointeurs changent et rien n'est déplacé.
- Nommer la structure, nommer sa règle, relier la règle à la situation.
Associez chaque TAD à sa règle et à une utilisation typique.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Pile = dernier-entré-premier-sorti ; file = premier-entré-premier-sorti ; une liste chaînée enchaîne des nœuds avec des pointeurs.
Les impressions doivent s'exécuter dans l'ordre d'arrivée. Quel TAD et pourquoi ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
L'ordre d'arrivée suit la règle FIFO. Une pile imprimerait la tâche la plus récente en premier.
ADT versus implémentation
- L'ADT est le comportement : push et pop, enqueue et dequeue, insert et traverse.
- L'implémentation est le stockage : dans ce cours, un tableau plus quelques variables pointeur (prochaine leçon).
- Une question sur l'ADT demande des opérations et des règles ; une question sur l'implémentation demande des tableaux, des pointeurs et les vérifications.
Pièges qui font perdre des points
- Push et enqueue testent pour plein d'abord ; pop et dequeue testent pour vide d'abord. Écrire la vérification dans la description.
- Insérer dans une liste chaînée : définir le pointeur du nœud nouveau avant de changer celui du nœud précédent, sinon le reste de la liste sera perdu.
- Une pile change à une extrémité, une file aux deux. « Retirer du haut de la file » est une réponse de pile.
- Développer les abréviations une fois : LIFO, last in first out ; FIFO, first in first out.
Vous avez compris
- un ADT est un ensemble de données avec un ensemble d'opérations dessus ; comportement, pas stockage
- pile : ajouter et retirer au sommet, LIFO, push et pop · file : ajouter à l'arrière, retirer à l'avant, FIFO, enqueue et dequeue
- liste chaînée : nœuds de valeur + pointeur depuis un pointeur de tête ; insertion et suppression peu coûteuses, accès aléatoire lent ; parcourir en suivant les pointeurs
- justifier par règle : ordre d'arrivée → file ; plus récent en premier → pile ; insertion fréquente au milieu → liste chaînée