Type de données abstrait

En informatique , un type de données abstrait ( ADT ) est un modèle mathématique pour les types de données , défini par son comportement ( sémantique ) du point de vue d'un utilisateur des données, notamment en termes de valeurs possibles, d'opérations possibles sur les données de ce type et du comportement de ces opérations. Ce modèle mathématique contraste avec les structures de données , qui sont des représentations concrètes de données et sont le point de vue d'un implémenteur, et non d'un utilisateur. Par exemple, une pile comporte des opérations push/pop qui suivent une règle Last-In-First-Out et peuvent être concrètement implémentées à l'aide d'une liste ou d'un tableau. Un autre exemple est un ensemble qui stocke des valeurs, sans ordre particulier , et sans valeurs répétées. Les valeurs elles-mêmes ne sont pas extraites d'ensembles ; on teste plutôt une valeur pour savoir si elle appartient à un ensemble afin d'obtenir un booléen « in » ou « not in ».

Les ADT sont un concept théorique, utilisé dans la sémantique formelle et la vérification de programmes et, de manière moins stricte, dans la conception et l'analyse d' algorithmes , de structures de données et de systèmes logiciels . La plupart des langages informatiques courants ne prennent pas directement en charge la spécification formelle des ADT. Cependant, diverses fonctionnalités du langage correspondent à certains aspects de la mise en œuvre des ADT et sont facilement confondues avec les ADT proprement dites ; il s'agit notamment des types abstraits , des types de données opaques , des protocoles et de la conception par contrat . Par exemple, dans la programmation modulaire , le module déclare des procédures qui correspondent aux opérations ADT, souvent avec des commentaires qui décrivent les contraintes. Cette stratégie de masquage des informations permet de modifier l'implémentation du module sans perturber les programmes clients , mais le module ne définit qu'informellement un ADT. La notion de types de données abstraits est liée au concept d' abstraction de données , important dans la programmation orientée objet et les méthodologies de conception par contrat pour l'ingénierie logicielle .

Les ADT ont été proposés pour la première fois par Barbara Liskov et Stephen N. Zilles en 1974, dans le cadre du développement du langage CLU . La spécification algébrique était un sujet de recherche important en informatique vers 1980 et presque synonyme de types de données abstraits à cette époque. Elle a un fondement mathématique dans l'algèbre universelle .

Formellement, un ADT est analogue à une structure algébrique en mathématiques, composée d'un domaine, d'une collection d'opérations et d'un ensemble de contraintes que les opérations doivent satisfaire. Le domaine est souvent défini implicitement, par exemple l' objet libre sur l'ensemble des opérations ADT. L' interface de l'ADT ne fait généralement référence qu'au domaine et aux opérations, et peut-être à certaines des contraintes sur les opérations, telles que les pré-conditions et les post-conditions ; mais pas à d'autres contraintes, telles que les relations entre les opérations, qui sont considérées comme un comportement. Il existe deux principaux styles de spécifications formelles pour le comportement, la sémantique axiomatique et la sémantique opérationnelle .

Même si elles ne font pas partie de l'interface, les contraintes sont néanmoins importantes pour la définition de l'ADT ; par exemple, une pile et une file d'attente ont des interfaces d'ajout/suppression d'éléments similaires, mais ce sont les contraintes qui distinguent le comportement dernier entré, premier sorti du comportement premier entré, premier sorti. Les contraintes ne se composent pas uniquement d'équations telles que fetch(store(S,v))=vmais également de formules logiques .

Dans l'esprit de la programmation fonctionnelle , chaque état d'une structure de données abstraite est une entité ou une valeur distincte. Dans cette perspective, chaque opération est modélisée comme une fonction mathématique sans effets secondaires . Les opérations qui modifient l'ADT sont modélisées comme des fonctions qui prennent l'ancien état comme argument et renvoient le nouvel état comme partie du résultat. L'ordre dans lequel les opérations sont évaluées est sans importance, et la même opération appliquée aux mêmes arguments (y compris les mêmes états d'entrée) renverra toujours les mêmes résultats (et états de sortie). Les contraintes sont spécifiées sous forme d'axiomes ou de lois algébriques que les opérations doivent satisfaire.

Dans l'esprit de la programmation impérative , une structure de données abstraite est conçue comme une entité mutable , ce qui signifie qu'il existe une notion de temps et que l'ADT peut être dans différents états à différents moments. Les opérations modifient ensuite l'état de l'ADT au fil du temps ; par conséquent, l'ordre dans lequel les opérations sont évaluées est important, et la même opération sur les mêmes entités peut avoir des effets différents si elle est exécutée à des moments différents. Cela est analogue aux instructions d'un ordinateur ou aux commandes et procédures d'un langage impératif. Pour souligner ce point de vue, il est courant de dire que les opérations sont exécutées ou appliquées , plutôt qu'évaluées , à l'instar du style impératif souvent utilisé lors de la description des algorithmes abstraits. Les contraintes sont généralement spécifiées en prose.

Les présentations des ADT se limitent souvent aux opérations clés. Des présentations plus complètes précisent souvent les opérations auxiliaires sur les ADT, telles que :

• create(), qui produit une nouvelle instance de l'ADT ;
• compare( s , t ), qui teste si les états de deux instances sont équivalents dans un certain sens ;
• hash( s ), qui calcule une fonction de hachage standard à partir de l'état de l'instance ;
• print( s ) ou show( s ), qui produit une représentation lisible par l'homme de l'état de l'instance.

Ces noms sont illustratifs et peuvent varier selon les auteurs. Dans les définitions ADT de style impératif, on trouve souvent aussi :

• initialize( s ), qui prépare une instance s nouvellement créée pour d'autres opérations, ou la réinitialise à un « état initial » ;
• copy( s , t ), qui met l'instance s dans un état équivalent à celui de t ;
• clone( t ), qui exécute s ← create(), copy( s , t ), et renvoie s ;
• free( s ) ou destroy( s ), qui récupère la mémoire et d’autres ressources utilisées par s .

L' freeopération n'est normalement pas pertinente ni significative, car les ADT sont des entités théoriques qui n'utilisent pas de mémoire. Cependant, elle peut être nécessaire lorsqu'il faut analyser le stockage utilisé par un algorithme qui utilise l'ADT. Dans ce cas, il faut des axiomes supplémentaires qui spécifient la quantité de mémoire utilisée par chaque instance d'ADT, en fonction de son état, et la quantité de mémoire renvoyée au pool par free.

La définition d'une ADT restreint souvent la ou les valeurs stockées pour ses instances aux membres d'un ensemble spécifique X appelé plage de ces variables. Par exemple, une variable abstraite peut être contrainte de ne stocker que des entiers. Comme dans les langages de programmation, de telles restrictions peuvent simplifier la description et l'analyse des algorithmes et améliorer leur lisibilité.

Dans le style opérationnel, il est souvent difficile de savoir comment plusieurs instances sont gérées et si la modification d'une instance peut affecter d'autres. Un style courant de définition des ADT écrit les opérations comme si une seule instance existait pendant l'exécution de l'algorithme, et toutes les opérations sont appliquées à cette instance. Par exemple, une pile peut avoir des opérations push( x ) et pop(), qui opèrent sur la seule pile existante. Les définitions d'ADT dans ce style peuvent être facilement réécrites pour admettre plusieurs instances coexistantes de l'ADT, en ajoutant un paramètre d'instance explicite (comme S dans l'exemple de pile ci-dessous) à chaque opération qui utilise ou modifie l'instance implicite. Certains ADT ne peuvent pas être définis de manière significative sans autoriser plusieurs instances, par exemple lorsqu'une seule opération prend deux instances distinctes de l'ADT comme paramètres, comme une unionopération sur des ensembles ou une compareopération sur des listes.

Le style d'instance multiple est parfois combiné avec un axiome d'aliasingcreate , à savoir que le résultat de () est distinct de toute instance déjà utilisée par l'algorithme. Les implémentations d'ADT peuvent toujours réutiliser la mémoire et permettre aux implémentations de create() de générer une instance créée précédemment ; cependant, définir qu'une telle instance est même « réutilisée » est difficile dans le formalisme ADT.

Plus généralement, cet axiome peut être renforcé pour exclure également les alias partiels avec d'autres instances, de sorte que les ADT composites (tels que les arbres ou les enregistrements) et les ADT de type référence (tels que les pointeurs) peuvent être considérés comme complètement disjoints. Par exemple, lors de l'extension de la définition d'une variable abstraite pour inclure les enregistrements abstraits , les opérations sur un champ F d'une variable d'enregistrement R impliquent clairement F , qui est distinct de R , mais qui en fait également partie . Un axiome d'alias partiel stipulerait que la modification d'un champ d'une variable d'enregistrement n'affecte aucun autre enregistrement.

Certains auteurs incluent également la complexité de calcul (« coût ») de chaque opération, à la fois en termes de temps (pour les opérations de calcul) et d'espace (pour la représentation des valeurs), pour faciliter l' analyse des algorithmes . Par exemple, on peut spécifier que chaque opération prend le même temps et que chaque valeur prend le même espace quel que soit l'état de l'ADT, ou qu'il existe une « taille » de l'ADT et que les opérations sont linéaires, quadratiques, etc. dans la taille de l'ADT. Alexander Stepanov , concepteur de la bibliothèque de modèles standard C++ , a inclus des garanties de complexité dans la spécification STL, en faisant valoir :

La raison pour laquelle on a introduit la notion de types de données abstraits était de permettre l'interchangeabilité des modules logiciels. Il est impossible d'avoir des modules interchangeables à moins que ces modules partagent un comportement de complexité similaire. Si je remplace un module par un autre module ayant le même comportement fonctionnel mais avec des compromis de complexité différents, l'utilisateur de ce code sera désagréablement surpris. Je pourrais lui dire tout ce que je veux sur l'abstraction des données, et il ne voudrait toujours pas utiliser le code. Les assertions de complexité doivent faire partie de l'interface.

—  Alexandre Stepanov

D'autres auteurs ne sont pas d'accord, affirmant qu'une pile ADT est la même qu'elle soit implémentée avec une liste chaînée ou un tableau, malgré la différence de coûts d'exploitation, et qu'une spécification ADT doit être indépendante de l'implémentation.

Une variable abstraite peut être considérée comme la plus simple des ADT non triviales, avec la sémantique d'une variable impérative. Elle admet deux opérations, fetchet store. Les définitions opérationnelles sont souvent écrites en termes de variables abstraites. Dans la sémantique axiomatique, soit le type de la variable abstraite et le type de son contenu, est une fonction et est une fonction de type . La contrainte principale est que renvoie toujours la valeur x utilisée dans l' opération la plus récente sur la même variable V , c'est-à-dire . Nous pouvons également exiger que écrase complètement la valeur, . fetchstorefetchstorefetch(store(V,x)) = xstorestore(store(V,x1),x2) = store(V,x2)

Dans la sémantique opérationnelle, fetch( V ) est une procédure qui renvoie la valeur courante à l'emplacement V , et store( V , x ) est une procédure avec voidun type de retour qui stocke la valeur x à l'emplacement V . Les contraintes sont décrites de manière informelle comme si les lectures étaient cohérentes avec les écritures. Comme dans de nombreux langages de programmation, l'opération store( V , x ) est souvent écrite V ← x (ou une notation similaire), et fetch( V ) est implicite chaque fois qu'une variable V est utilisée dans un contexte où une valeur est requise. Ainsi, par exemple, V ← V + 1 est généralement considéré comme un raccourci pour store( V , fetch( V ) + 1).

Dans cette définition, on suppose implicitement que les noms sont toujours distincts : le stockage d'une valeur dans une variable U n'a aucun effet sur l'état d'une variable distincte V . Pour rendre cette hypothèse explicite, on pourrait ajouter la contrainte suivante :

• si U et V sont des variables distinctes, la séquence { store( U , x ); store( V , y ) } est équivalente à { store( V , y ); store( U , x ) }.

Cette définition ne dit rien sur le résultat de l'évaluation de fetch( V ) lorsque V n'est pas initialisé , c'est-à-dire avant d'effectuer une storeopération sur V . La récupération avant le stockage peut être interdite, définie pour avoir un certain résultat ou laissée non spécifiée. Il existe certains algorithmes dont l'efficacité dépend de l'hypothèse selon laquelle un tel a fetchest légal et renvoie une valeur arbitraire dans la plage de la variable.

Une pile abstraite est une structure de type dernier entré, premier sorti. Elle est généralement définie par trois opérations clés : push, qui insère un élément de données sur la pile ; pop, qui en supprime un élément de données ; et peekou top, qui accède à un élément de données au-dessus de la pile sans suppression. Une définition complète de pile abstraite comprend également une fonction à valeur booléenneempty ( S ) et une createopération () qui renvoie une instance de pile initiale.

Dans la sémantique axiomatique, soit le type des états de la pile et le type des valeurs contenues dans la pile, ceux-ci pourraient avoir les types , , , et . Dans la sémantique axiomatique, la création de la pile initiale est une opération « triviale » et renvoie toujours le même état distinctif. Par conséquent, elle est souvent désignée par un symbole spécial comme Λ ou « () ». Le prédicat d'opération peut alors être écrit simplement comme ou . empty

Les contraintes sont alors pop(push(S,v))=(S,v), top(push(S,v))=v, empty ( create) = T (une pile nouvellement créée est vide), empty( push( S , x )) = F (pousser quelque chose dans une pile la rend non vide). Ces axiomes ne définissent pas l'effet de top( s ) ou pop( s ), à moins que s ne soit un état de pile renvoyé par a push. Puisque pushlaisse la pile non vide, ces deux opérations peuvent être définies comme non valides lorsque s = Λ. De ces axiomes (et de l'absence d'effets secondaires), on peut déduire que push(Λ, x ) ≠ Λ. De plus, push( s , x ) = push( t , y ) si et seulement si x = y et s = t .

Comme dans d'autres branches des mathématiques, il est également courant de supposer que les états de pile sont uniquement ceux dont l'existence peut être prouvée à partir des axiomes en un nombre fini d'étapes. Dans ce cas, cela signifie que chaque pile est une séquence finie de valeurs, qui devient la pile vide (Λ) après un nombre fini de pops. En eux-mêmes, les axiomes ci-dessus n'excluent pas l'existence de piles infinies (qui peuvent être poprépétées indéfiniment, donnant à chaque fois un état différent) ou de piles circulaires (qui reviennent au même état après un nombre fini de pops). En particulier, ils n'excluent pas les états s tels que pop( s ) = s ou push( s , x ) = s pour un certain x . Cependant, comme on ne peut pas obtenir de tels états de pile à partir de l'état initial de la pile avec les opérations données, on suppose qu'ils "n'existent pas".

Dans la définition opérationnelle d'une pile abstraite, push( S , x ) ne renvoie rien et pop( S ) donne la valeur comme résultat mais pas le nouvel état de la pile. Il y a alors la contrainte que, pour toute valeur x et toute variable abstraite V , la séquence d'opérations { push( S , x ); V ← pop( S ) } est équivalente à V ← x . Puisque l'affectation V ← x , par définition, ne peut pas changer l'état de S , cette condition implique que V ← pop( S ) restaure S à l'état qu'il avait avant push( S , x ). De cette condition et des propriétés des variables abstraites, il résulte, par exemple, que la séquence :

{ push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S ) }

où x , y et z sont des valeurs quelconques et U , V , W sont des variables distinctes deux à deux, est équivalent à :

{ U ← y ; V ← z ; W ← x }

Contrairement à la sémantique axiomatique, la sémantique opérationnelle peut souffrir d'aliasing. Ici, il est implicitement supposé que les opérations sur une instance de pile ne modifient pas l'état d'une autre instance ADT, y compris d'autres piles ; c'est-à-dire :

• Pour toutes les valeurs x , y et toutes les piles distinctes S et T , la séquence { push( S , x ); push( T , y ) } est équivalente à { push( T , y ); push( S , x ) }.

Un exemple plus complexe est la hiérarchie Boom des types de données abstraits binary tree , list , bag et set . Tous ces types de données peuvent être déclarés par trois opérations : null , qui construit le conteneur vide, single , qui construit un conteneur à partir d'un seul élément et append , qui combine deux conteneurs du même type. La spécification complète des quatre types de données peut alors être donnée en ajoutant successivement les règles suivantes sur ces opérations :

L'accès aux données peut être spécifié par une correspondance de modèles sur les trois opérations, par exemple une fonction membre pour ces conteneurs par :

Il faut veiller à ce que la fonction soit invariante selon les règles applicables au type de données. Dans chacune des classes d'équivalence impliquées par le sous-ensemble d'équations choisi, elle doit produire le même résultat pour tous ses membres.

Certains ADT courants, qui se sont avérés utiles dans une grande variété d'applications, sont

Chacun de ces ADT peut être défini de plusieurs manières et variantes, pas nécessairement équivalentes. Par exemple, une pile abstraite peut ou non avoir une countopération qui indique combien d'éléments ont été poussés et pas encore extraits. Ce choix fait une différence non seulement pour ses clients mais aussi pour l'implémentation.

Type de données graphiques abstraites

Une extension de l'ADT pour l'infographie a été proposée en 1979 : un type de données graphiques abstrait (AGDT). Il a été introduit par Nadia Magnenat Thalmann et Daniel Thalmann . Les AGDT offrent les avantages des ADT avec des fonctionnalités permettant de construire des objets graphiques de manière structurée.

Les types de données abstraits sont des entités théoriques, utilisées (entre autres) pour simplifier la description des algorithmes abstraits, pour classer et évaluer les structures de données et pour décrire formellement les systèmes de types des langages de programmation. Cependant, un ADT peut être implémenté . Cela signifie que chaque instance ou état ADT est représenté par un type de données ou une structure de données concret , et pour chaque opération abstraite, il existe une procédure ou une fonction correspondante , et ces procédures implémentées satisfont aux spécifications et aux axiomes de l'ADT jusqu'à un certain niveau. En pratique, l'implémentation n'est pas parfaite et les utilisateurs doivent être conscients des problèmes dus aux limitations de la représentation et des procédures implémentées.

Par exemple, les entiers peuvent être spécifiés comme un ADT, défini par les valeurs distinguées 0 et 1, les opérations d'addition, de soustraction, de multiplication, de division (avec précaution pour la division par zéro), de comparaison, etc., se comportant selon les axiomes mathématiques familiers de l'algèbre abstraite tels que l'associativité, la commutativité, etc. Cependant, dans un ordinateur, les entiers sont le plus souvent représentés sous forme de nombres binaires à largeur fixe de 32 ou 64 bits . Les utilisateurs doivent être conscients des problèmes liés à cette représentation, tels que le dépassement arithmétique , où l'ADT spécifie un résultat valide mais la représentation n'est pas en mesure de prendre en charge cette valeur. Néanmoins, pour de nombreuses raisons, l'utilisateur peut ignorer ces infidélités et simplement utiliser l'implémentation comme s'il s'agissait du type de données abstrait.

En général, il existe de nombreuses façons d'implémenter le même ADT, en utilisant plusieurs structures de données concrètes différentes. Ainsi, par exemple, une pile abstraite peut être implémentée par une liste chaînée ou par un tableau . Différentes implémentations de l'ADT, ayant toutes les mêmes propriétés et capacités, peuvent être considérées comme sémantiquement équivalentes et peuvent être utilisées de manière quelque peu interchangeable dans le code qui utilise l'ADT. Cela fournit une forme d' abstraction ou d'encapsulation et offre une grande flexibilité lors de l'utilisation d'objets ADT dans différentes situations. Par exemple, différentes implémentations de l'ADT peuvent être plus efficaces dans différentes situations ; il est possible d'utiliser chacune dans la situation où elles sont préférables, augmentant ainsi l'efficacité globale. Le code qui utilise une implémentation ADT en fonction de son interface continuera à fonctionner même si l'implémentation de l'ADT est modifiée.

Afin d'empêcher les clients de dépendre de l'implémentation, un ADT est souvent empaqueté sous forme de type de données opaque ou de handle d'une certaine sorte, dans un ou plusieurs modules , dont l'interface ne contient que la signature (nombre et types des paramètres et des résultats) des opérations. L'implémentation du module, à savoir les corps des procédures et la structure de données concrète utilisée, peut alors être cachée à la plupart des clients du module. Cela permet de modifier l'implémentation sans affecter les clients. Si l'implémentation est exposée, elle est alors connue sous le nom de type de données transparent.

Les langages modernes orientés objet, tels que C++ et Java , prennent en charge une forme de types de données abstraits. Lorsqu'une classe est utilisée comme type, il s'agit d'un type abstrait qui fait référence à une représentation cachée. Dans ce modèle, un ADT est généralement implémenté en tant que classe , et chaque instance de l'ADT est généralement un objet de cette classe. L'interface du module déclare généralement les constructeurs comme des procédures ordinaires et la plupart des autres opérations ADT comme des méthodes de cette classe. De nombreux langages de programmation modernes, tels que C++ et Java, sont fournis avec des bibliothèques standard qui implémentent de nombreux ADT dans ce style. Cependant, une telle approche n'encapsule pas facilement plusieurs variantes de représentation trouvées dans un ADT. Elle peut également compromettre l'extensibilité des programmes orientés objet. Dans un programme purement orienté objet qui utilise des interfaces comme types, les types font référence à des comportements, et non à des représentations.

La spécification de certains langages de programmation est volontairement vague sur la représentation de certains types de données intégrés, définissant uniquement les opérations qui peuvent être effectuées sur eux. Par conséquent, ces types peuvent être considérés comme des « ADT intégrés ». Les tableaux de nombreux langages de script, tels que Awk , Lua et Perl , qui peuvent être considérés comme une implémentation de la liste abstraite, en sont des exemples.

Dans un langage de spécification formel , les ADT peuvent être définis de manière axiomatique, et le langage permet ensuite de manipuler les valeurs de ces ADT, fournissant ainsi une implémentation simple et immédiate. La famille de langages de programmation OBJ permet par exemple de définir des équations pour la spécification et de les réécrire pour les exécuter. De telles implémentations automatiques ne sont cependant généralement pas aussi efficaces que les implémentations dédiées.

À titre d’exemple, voici une implémentation de la pile abstraite ci-dessus dans le langage de programmation C.

Une interface de style impératif pourrait être :

typedef struct stack_Rep stack_Rep ; // type : représentation d'instance de pile (enregistrement opaque) typedef stack_Rep * stack_T ; // type : handle vers une instance de pile (pointeur opaque) typedef void * stack_Item ; // type : valeur stockée dans l'instance de pile (adresse arbitraire)
stack_T stack_create ( void ); // crée une nouvelle instance de pile vide void stack_push ( stack_T s , stack_Item x ); // ajoute un élément en haut de la pile stack_Item stack_pop ( stack_T s ); // supprime l'élément supérieur de la pile et le renvoie bool stack_empty ( stack_T s ); // vérifie si la pile est vide

Cette interface pourrait être utilisée de la manière suivante :

#include <stack.h>  // inclut l'interface de la pile
stack_T s = stack_create (); // crée une nouvelle instance de pile vide int x = 17 ; stack_push ( s , & x ); // ajoute l'adresse de x en haut de la pile void * y = stack_pop ( s ); // supprime l'adresse de x de la pile et la renvoie if ( stack_empty ( s )) { } // fait quelque chose si la pile est vide

Cette interface peut être implémentée de plusieurs manières. L'implémentation peut être arbitrairement inefficace, puisque la définition formelle de l'ADT, ci-dessus, ne précise pas combien d'espace la pile peut utiliser, ni combien de temps chaque opération doit prendre. Elle ne précise pas non plus si l'état de la pile s continue d'exister après un appel x ← pop( s ).

En pratique, la définition formelle doit spécifier que l'espace est proportionnel au nombre d'éléments poussés et non encore extraits ; et que chacune des opérations ci-dessus doit se terminer dans un laps de temps constant, indépendamment de ce nombre. Pour se conformer à ces spécifications supplémentaires, l'implémentation pourrait utiliser une liste chaînée ou un tableau (avec redimensionnement dynamique) avec deux entiers (un nombre d'éléments et la taille du tableau).

Les définitions ADT de style fonctionnel sont plus adaptées aux langages de programmation fonctionnels, et vice versa. Cependant, il est possible de fournir une interface de style fonctionnel même dans un langage impératif comme C. Par exemple :

typedef struct stack_Rep stack_Rep ; // type : représentation de l'état de la pile (enregistrement opaque) typedef stack_Rep * stack_T ; // type : handle vers un état de la pile (pointeur opaque) typedef void * stack_Item ; // type : valeur d'un état de la pile (adresse arbitraire)
stack_T stack_empty ( void ); // renvoie l'état de pile vide stack_T stack_push ( stack_T s , stack_Item x ); // ajoute un élément en haut de l'état de pile et renvoie l'état de pile résultant stack_T stack_pop ( stack_T s ); // supprime l'élément supérieur de l'état de pile et renvoie l'état de pile résultant stack_Item stack_top ( stack_T s ); // renvoie l'élément supérieur de l'état de pile