C3 : Piles et files
💚 Vocabulaire
Généralités
Les piles et les files sont des structures de données dites linéaires (ou séquentielles), les données qu'elles contiennent sont ordonnées.
Comme toute structure de données, les piles et les files doivent être implémentées. Cela peut se faire soit avec des fonctions, soit avec des classes.
Piles
Caractéristique
Les piles se caractérisent par le fait que les données qu'elles contiennent se manipulent en respectant le principe « dernier arrivé, premier sorti » (en anglais LIFO pour last in, first out). Autrement dit, les éléments sont ajoutés et enlevés du même côté.
Interface
L'interface minimale des piles permet les actions suivantes :
- - Créer une structure vide ;
- - Tester si la structure est vide ;
- - Ajouter un élément à la structure : empiler ;
- - Enlever (en renvoyant) un élément à la structure : dépiler.
Files
Caractéristique
La manipulation des données d'une file se fait suivant le principe « premier arrivé, premier sorti » (en anglais FIFO pour first in, first out). Autrement dit, les éléments sont ajoutés d'un côté et enlevés de l'autre.
Interface
L'interface minimale des files doit permettre les actions suivantes :
- - Créer une structure vide ;
- - Tester si la structure est vide ;
- - Ajouter un élément à la structure : enfiler ;
- - Enlever (en renvoyant) un élément à la structure : défiler.