Définition générale

Suite ordonnée d’éléments. Chaque élément a un prédécesseur logique et un successeur logique.

Opérations de base

• Parcours des éléments
• Recherche d’un élément

Principe LIFO

LIFO signifie Last In, First Out. Le dernier élément ajouté est le premier retiré.

Fonctionnement

1. 1

   Empiler un élément au sommet.

2. 2

   Consulter le sommet.

Mémo

Imagine une pile d’assiettes : on ajoute et on retire toujours par le haut.

Principe FIFO

FIFO signifie First In, First Out. Le premier élément entré est le premier sorti.

Fonctionnement

1. 1

   Ajouter un élément en fin de file.

2. 2

   Consulter la tête de file.

Usages

• Files d’attente
• Ordonnancement de tâches

Tableaux et listes chaînées

Parcours et insertion

1. 1

   Parcourir jusqu’à la position visée.

2. 2

   Modifier l’indice ou les pointeurs.

Suppression d’éléments

• Dans un tableau, décaler les éléments.
• Dans une liste chaînée, modifier les liens.

Cas d’usage

Parcours, insertion, suppression

• Le parcours visite les éléments un par un.
• L’insertion et la suppression dépendent de la position.

• Une structure linéaire organise des éléments en séquence.
• Pile = LIFO, file = FIFO.
• Tableau et liste chaînée répondent à des besoins différents.
• Les opérations de base sont parcours, insertion, suppression.