Dans ce chapitre, nous introduisons quelques structures utilisées de
façon très intensive en programmation. Leur but est de gérer un
ensemble fini d'éléments dont le nombre n'est pas fixé a
priori. Les éléments de cet ensemble peuvent être de
différentes sortes: nombres entiers ou réels, chaînes de
caractères, ou des objets informatiques plus complexes comme les
identificateurs de processus ou les expressions de formules en cours
de calcul 
On ne s'intéressera pas aux éléments de
l'ensemble en question mais aux opérations que l'on effectue sur cet
ensemble, indépendamment de la nature de ses éléments. Ainsi
les ensembles que l'on utilise en programmation, contrairement à
ceux considérés en mathématiques qui sont fixés une fois pour
toutes, sont des objets dynamiques. Le nombre de leurs éléments
varie au cours de l'exécution du programme, puisqu'on peut y ajouter
et supprimer des éléments en cours de traitement. Plus
précisément les opérations que l'on s'autorise sur les ensembles
sont les suivantes :
est vide.
à l'ensemble .
appartient à l'ensemble .
de l'ensemble .
Cette gestion des ensembles doit, pour être efficace, répondre au
mieux à deux critères parfois contradictoires: un minimum de place
mémoire utilisée et un minimum d'instructions élémentaires
pour réaliser une opération. La place mémoire utilisée devrait
pour bien faire être très voisine du nombre d'éléments de
l'ensemble , multipliée par leur taille; c'est ce qui se passera
pour les trois structures que l'on va étudier plus loin. En ce qui
concerne la minimisation du nombre d'instructions élémentaires, on
peut tester très simplement si un ensemble est vide et on peut
réaliser l'opération d'ajout en quelques instructions toutefois,
il est impossible de réaliser une suppression ou une recherche d'un
élément quelconque dans un ensemble en utilisant un nombre
d'opérations indépendant du cardinal de cet ensemble (à moins
d'utiliser une structure demandant une très grande place en
mémoire). Pour améliorer l'efficacité, on considère des
structures de données dans lesquelles on restreint la portée des
opérations de recherche et de suppression d'un élément en se
limitant à la réalisation de ces opérations sur le dernier ou le
premier élément de l'ensemble, ceci donne les structures de pile ou
de file, nous verrons que malgré ces restrictions les structures en
question ont de nombreuses applications.