Structures de données, interfaces et implémentation

Les structures de données sont des moyens de stocker et de manipuler les données de manière efficace. Il existe de nombreux types de structures de données, chacun ayant ses propres avantages et inconvénients. Par exemple, les tableaux sont très rapides pour accéder à un élément spécifique, mais ils peuvent être lents pour insérer ou supprimer des éléments. Les listes liées, d'autre part, sont plus lentes pour accéder à un élément spécifique, mais elles sont plus rapides pour insérer ou supprimer des éléments.

Les interfaces décrivent les fonctionnalités d'un objet ou d'une classe sans décrire comment elles sont implémentées. Cela permet aux développeurs de créer des objets qui respectent une certaine interface sans avoir à connaître les détails de l'implémentation. Par exemple, une interface pour un téléphone mobile pourrait décrire les fonctions telles que passer un appel, envoyer un message texte et accéder à internet, mais ne décrirait pas comment ces fonctions sont implémentées (par exemple, en utilisant une carte SIM ou une connexion Wi-Fi).

L'implémentation est le processus de création d'un objet ou d'une classe qui respecte une certaine interface. Cela peut impliquer la création de variables de données pour stocker les données de l'objet et la définition de fonctions pour manipuler ces données. Par exemple, pour implémenter une interface de téléphone mobile, un développeur pourrait créer une classe qui contient des variables pour stocker le numéro de téléphone, le nom du contact, et d'autres informations liées aux contacts, et définir des fonctions pour ajouter, supprimer, et afficher les contacts.

L'interface d'une structure de données abstraite est l'ensemble des opérateurs nécessaires à la manipulation de cette structure.

=La file=

Une file est:

Une structure de File fonctionne sur le principe premier entré − premier sorti (comme les files d’attentes à un guichet) FIFO : First In First Out.

On pourra représenter une file de la manière suivante :

 Un arbre est une structure de données hiérachique qui est constitué d'un noeud racine tout en haut et de plusieurs sous-arbres.Chaque noeud de l'arbre peut avoir un ou plusieur enfants mais un seul parent(sauf le noeud racine qui n'a pas de parents

Soit P une pile. On dispose d'un tableau nommé T avec n emplacements.
Il est possible d’implémenter la pile P d’au plus n éléments avec le tableau T.

Le tableau possède un attribut sommet(P) qui indexe l’élément le plus récemment inséré.  
La pile est constituée des éléments T[1..sommet(P)], tous ceux compris entre T[1],
l’élément situé à la base de la pile, et T[sommet(P)], l’élément situé au sommet.

La donnée de la pile se constitue donc de la donnée de T
et de la valeur de sommet(P).

On dispose d'un tableau nommé T avec n emplacements.
Il est possible d’implémenter une file F
d’au plus n éléments avec le tableau T.

Le tableau possède un attribut tete(F)
qui indexe l’élément de tête et un attribut queue(F) qui indexe l'emplacement où un nouvel
élément sera inséré. T[queue(F)] est vide au sens de la file.

Avec cette implémentation T[n+1] doit pointer vers T[1] au sens de la file.
Une façons de visualiser cette implémentation est un tableau circulaire où le début
du tableau et la fin du tableau seraient reliés.

Les éléments de la file se trouvent aux emplacements tete(F),
tete(F)+1, . . . , queue(F)−1, après quoi l’on « boucle » : l’emplacement 1 suit immédiatement
l’emplacement n dans un ordre circulaire.
Dans cette implémentation la queue est vide.