← Retour au chapitre

Fiche à trous · Terminale · NSI

Structures linéaires : listes, piles et files

Complétez de mémoire, puis vérifiez avec la page de corrigé.

Le bouton « Annuler » d'un traitement de texte retrouve la dernière action effectuée ; une imprimante traite les documents dans l'ordre d'arrivée. Ces deux comportements correspondent à deux structures de données : la pile et la file.

Interface et implémentation

Définition — interface :

Définition — implémentation :

La pile (LIFO)

Définition — pile :

Règle

La file (FIFO) et la liste chaînée

Définition — file :

Règle

Définition — liste chaînée :

Exemple

On empile 1, 2, 3 puis on dépile deux fois. Que reste-t-il ?

  1. 8.
  2. 9.
  3. 10.

Résultat :

Piège

Confondre pile et file.

Penser à une pile d'assiettes et à une file d'attente.

Choisir une structure linéaire

  1. 12.
  2. 13.
  3. 14.
  4. 15.
  • Ai-je défini le vocabulaire ?
  • Mon code est-il testé sur un exemple ?
  • Ai-je traité les cas limites ?
  • Ai-je justifié la complexité ou le résultat ?

Corrigé · à détacher

Structures linéaires : listes, piles et files

  1. 1. Ensemble des opérations disponibles sur une structure, sans dire comment elles sont programmées.
  2. 2. Manière concrète de programmer ces opérations (avec une liste Python, des maillons chaînés, une classe).
  3. 3. Structure « dernier entré, premier sorti » (LIFO) : on empile au sommet et on dépile le sommet.
  4. 4. Usages : annulation, retour arrière d'un navigateur, pile d'appels des fonctions, vérification des parenthèses. En Python : p.append(x) et p.pop().
  5. 5. Structure « premier entré, premier sorti » (FIFO) : on enfile à la queue et on défile en tête.
  6. 6. Usages : file d'impression, ordonnancement, parcours en largeur. collections.deque offre append et popleft en temps constant (list.pop(0) est coûteux).
  7. 7. Suite de maillons contenant une valeur et un lien vers le suivant ; insertion en tête en temps constant.
  8. 8. Après les empilements, la pile est [1, 2, 3], sommet 3.
  9. 9. On dépile 3, puis 2.
  10. 10. Il reste [1].
  11. 11. Une pile rend les éléments dans l'ordre inverse de leur arrivée.
  12. 12. Identifier l'ordre de traitement voulu.
  13. 13. Choisir la pile si le dernier arrivé sort d'abord.
  14. 14. Choisir la file si le premier arrivé sort d'abord.
  15. 15. Vérifier le coût des opérations de l'implémentation.