Partager cet article

RSS
BOURSE

RUBRIQUES

 
 TUTORIEL ALGO/METHODES 
Structures de données : trois exemples essentiels à (re)découvrir
Pain quotidien des développeurs, les structures de données ne sont pourtant pas forcément bien connues. Explication des principes des listes, piles et files. (09/04/2004)
  Forum

Réagissez dans les forums de JDN Développeurs

Les structures de données sont une part essentielle de la programmation, au point que nombre de développeurs s'en servent sans vraiment savoir qu'elles sont définies comme telles.

Une structure de données correspond à un ensemble de deux ou plusieurs données, formant ainsi un groupe que le peut traiter à loisir. On peut ainsi facilement regrouper les données semblables ou liées, et mieux gérer les informations nécessaires au bon fonctionnement d'une application. Simplement, sans structure de données, le développeur devrait jongler avec un nombre important de variables indépendantes l'une de l'autre.

Une telle structure permet donc de se servir d'un ensemble de données (hétérogène ou non) en utilisant généralement qu'une seule variable (celle définissant la structure).

L'explication ci-dessous est sans doute évidente pour nombre de lecteurs, même si certains ne connaissent pas forcément quels sont les types de structures à leur disposition.

Principalement, le développeur peut avoir recours à six types de structures : la liste (chaînée ou double-chaînée), la pile, la file (ou queue), le tableau (ou vecteur), l'arbre et le graphe. Il y en a d'autres. Nous allons aborder ici les trois premiers.

Liste

C'est sans doute la première structure de données que l'on apprend en commençant à programmer. La liste est la manière la plus "naturelle" d'organiser ses données de manières séquentielles (dans un ordre donné). Elle permet d'ajouter et supprimer facilement un élément, et n'a pas une taille fixe comme le tableau (le nombre de données contenues dans une liste peut dépasser la taille spécifiée à la création de la liste), mais l'accès reste séquentiel.
Implémenté enECMAScript, cette structure devient un tableau Array() des plus classiques.

Pile et File
Ces deux structures sont très liées car ce sont là deux possibilités étendues des listes, mais avec chacune une subtilité. Si les listes peuvent librement être modifiées, les piles et files le sont dans un seul sens et une seule donnée à la fois, par le biais respectivement des méthodes LIFO et FIFO. (Ces deux termes sont les acronymes de Last In First Out et First In First Out.)

Une pile se traite en mode LIFO car la première donnée tirée/sortie de cette structure sera également la dernière entrée.
Pareillement, une file se traite en mode FIFO car la première donnée sortie de cette structure sera également la première entrée.

Il faut pour comprendre ce mode de fonctionnement savoir que pile et file n'exposent que leurs "extrémités" au programme, et se les représenter à l'aide d'une métaphore idoine.

PILE : le dernier élément entré dans la structure est aussi le premier à en sortir.
On peut comparer ce fonctionnement à celui d'une pile d'assiette à laver : si on ajoute une assiette à la pile, c'est elle qui sera la première lavée. Et donc, le premier élément ajouté à la structure (l'assiette du bas) sera aussi le dernier qui en sortira.
Cette structure tourne elle-aussi autour de deux fonctions : push() pour ajouter un élément ou plusieurs sur la pile (elle renvoi la nouvelle taille de celle-ci), et pop() pour en retirer un (celui deu "haut" de la pile).

apotres = ["Pierre", "Jacques", "Jean", "André", "Philippe", "Barthélémy"];
document.write(apotre.length); // écrit "6"

taille = apotres.push("Thomas", "Matthieu", "Thomas", "Jacques", "Simon", "Judas");
document.write(taille); // écrit "12"

traitre = apotres.pop();
document.write(traitre);       // écrit "Judas"
document.write(apotre.length); // écrit "11"

FILE : le premier élément entré dans la structure est aussi le premier élément sorti. On peut donc comparer cela à une file d'attente au cinéma : le premier arrivé devant le cinéma sera le premier dans la salle, et le dernier devra espérer qu'il reste de la place.
Cette structure tourne autour de deux fonctions : l'une (unshift())pour glisser un nouvel élément (ou plusieurs) dans une file (et décaler les autres éléments d'un "cran"), et l'autre (shift()) pour sortir un élément de la file. Les deux travaillent sur un tableau. Le langage ECMAScript dispose des fonctions nécessaires :

apotres = ["Judas", "Jacques", "Jean", "André", "Philippe", "Barthélémy"];
document.write(apotre.length); // écrit "6"

apotres.unshift("Thomas", "Matthieu", "Thomas", "Jacques", "Simon", "Pierre");
document.write(apotre.length); // écrit "12"

traitre = apotres.shift();
document.write(traitre);       // écrit "Judas"
document.write(apotre.length); // écrit "11"

  Forum

Réagissez dans les forums de JDN Développeurs

On peut penser que les pile et file n'apportent que des limitations au principe de la liste, où l'on accède plus librement aux données, mais l'intérêt se trouve principalement quand il s'agit de traiter une suite de traitements en attente : une donnée ne peut être traitée tant que celle qui vient de sortir de la structure n'a pas été elle-même traitée. On y fait souvent appel dans le cas d'une fonction récursive.
 
Xavier Borderie, JDN Développeurs
 
Accueil | Haut de page
 
 



A VOIR EGALEMENT