Introduction

Les piles et les files permettent de stocker des objets, et proposent différentes opérations pour ajouter ou retirer des objets un par un. Toutefois, leur spécificité réside dans le fait que les objets ajoutés et retirés le sont dans un ordre particulier.

Dans une pile (stack), l'opération de retrait va retirer l'objet ajouté le plus récemment. On peut comparer cela à une pile d'assiettes, où chaque assiette représente un objet dans notre pile en informatique.

• À chaque ajout d'assiette, on va placer l'assiette sur le dessus de la pile.
• À chaque retrait d'assiette, on va récupérer l'assiette sur le dessus de la pile.

Cette méthode d'ajout et de retrait est appelée Dernier Entré, Premier Sorti (DEPS), plus couramment employé dans sa version anglaise : Last In, First Out (LIFO).

Dans une file (queue), l'opération de retrait va retirer l'objet ajouté le moins récemment. On peut comparer cela à une file d'attente devant un commerce, où chaque client représente un objet dans notre file en informatique.

• À chaque arrivée de client, le client se place au bout de la file.
• À chaque appel du client suivant, le client en début de file est appelé.

Cette méthode d'ajout et de retrait est appelée Premier Entré, Premier Sorti (PEPS), plus couramment employé dans sa version anglaise : First In, First Out (FIFO).

Quels sont donc les attendus de nos deux structures de données ?

• Créer une structure vide.
• Vérifier si une structure est vide.
• Ajouter un élément dans une structure.
• Retirer un élément d'une structure.

Enfin, même si ces structures peuvent contenir des données de type différent, nous allons considérer qu'elles doivent être homogènes, c'est-à-dire que le type de données de chaque élément dans la structure doit être de même type.