File

Une file est un conteneur relativement simple. Comme pour la pile, le domaine n'admet pas forcément d'opération de comparaison, ni même d'égalité. L'image mentale d'une file est une file d'attente bien disciplinée où chaque nouvelle personne se met à la fin et la première de la file est servie en premier. En anglais, on parle de FIFO (First In First Out), alors que pour la pile on parle de LIFO (Last In First Out).

Contrairement à la pile, il est difficile de créer une file fonctionnelle, à savoir une file dont les opérations pour rajouter et supprimer un élément renvoient une nouvelle file sans modifier celle passée en argument. Pour cette raison, dans cette section nous parlons uniquement d'opérations impératives.