Files et piles

Dans ce chapitre nous étudierons deux structures de données qui nous seront utiles tout au long de l'année : les files et les piles.

Le cours

Le cours sera fait en classe, avec des stylos et des feuilles de papier.

Activités

1. Observer, reconnaitre
2. Retourner une pile
3. Retourner une pile avec Python
4. La Princesse au petit pois
5. Les trois lits de la princesse
6. La Princesse et le Python
7. Les trois lits, la princesse et le Python
8. Une file avec deux piles : enfiler
9. Une file avec deux piles : enfiler et défiler
10. Une file avec deux piles : exercice aléatoire
11. Une file avec deux piles : retrouver la file
12. Retourner une pile, 100 % Python

Travaux pratiques

1. Parcours de files avec Python sur Capytale
2. Parcours de piles avec Python sur Capytale
3. Implémentation rudimentaire des files sur Codex
4. Implémentation des piles avec des list Python sur Capytale

Exercices de bac

1. Exercice 1 du sujet 0 publié en 2021
2. Exercice 1 du sujet 22-NSIJ2LR1
3. Exercice 1 du sujet 22-NSIJ1ME1

Idées de projets

Quelques idées de projets avec des files ou piles :

• Notation polonaise inverse.
• Algorithme Shunting-Yard.
• Jeu de cartes.
• Jeu Water sort puzzle ou Ball sort puzzle.
• Implémenter les fonctions de files avec deux piles.
• Simulation de création de brochettes, de colliers ou tout autre objet qu'on peut enfiler ou empiler.
• Simulation de robot gérant des containers dans un port.
• Simulation de trafic routier.
• Simulation d'une pile de Volta.
• Comment vérifier que les parenthèses d'une formule mathématique (ou d'un programme Python) sont correctes ? Extension possible aux balises HTML.
• Reprogrammer certaines des activités vues dans ce chapitre (sans animation).

Programme officiel

Structures de données, interface et implémentation. Spécifier une structure de données par son interface. Distinguer interface et implémentation. Écrire plusieurs implémentations d’une même structure de données (sera revu en cours d'année).

Listes, piles, files : structures linéaires. Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files.