Les piles et les files en Javascript

Septembre 2016

Les programmeurs connaissent bien ces deux structures que sont les piles et les files, et qui vous permettent d'ordonner des éléments durant l'attente d'un traitement. Nous allons voir ici qu'il existe un moyen simple de les reproduire en Javascript avec des méthodes pré-existantes.


L'objet Array


Au centre de notre attention : les tableaux, soit l'objet Array de Javascript. La plupart d'entre vous le connaissent surement, aussi le bout de code ci-dessous ne surprendra personne, et tout le monde comprendra que je ne m'attarde pas dessus ici.

var monTableau = new Array(1, 2, 3, 4, 5) ;


Figurez-vous que les piles et les files Javascript ne sont rien d'autre que des tableaux dont on utilise quatre méthodes : pop(), push(), shift() et unshift().

Les piles : la structure FILO


"La structure quoi ?!" vous entends-je dire. FILO est un acronyme anglais signifiant "First In Last Out", autrement dit : "Premier entré, dernier sorti".

Pour vous représenter la chose, imaginez... et bien une pile, tout simplement. Si vous prenez des bouquins et que vous les posez à plat le sol, en les superposant les uns sur les autres, un à un ; alors nécessairement le dernier posé sur le dessus sera le premier que vous saisirez par la suite (sauf si vous êtes un peu tordu, évidemment).

Bref, nous allons ici utiliser les deux méthodes suivantes :
  • push() : qui permet d'ajouter un élément à la fin du tableau, augmentant ainsi sa taille de 1.
  • pop() : qui retire le dernier élément du tableau, réduisant ainsi sa taille de 1.

Evidemment, vous pouvez également utiliser les méthodes shift() et unshift() pour faire une pile avec le début du tableau, mais il est plus propre "programmaticalement" parlant d'utiliser la fin.

Exemple d'utilisation d'une pile :
monTableau.push(6);  // On ajoute un 6e élément    
monTableau.pop();   // On le retire    
monTableau.pop();   // On retire le 5    
monTableau.push(monTableau.pop()); // Sans effet !    
/* Le tableau résultant est [1|2|3|4] */

Les files : la structure FIFO


Une nouvelle structure ! FIFO est l'acronyme anglais signifiant "First In First Out", autrement dit : "Premier entré, premier sorti".

Imaginez-vous cette fois une file d'attente dans un supermarché. Vous arrivez à la caisse en premier, et des gens arrivent derrière vous. Nécessairement, vous allez passer en premier : c'est une file !

Nous allons ici utiliser les deux méthodes suivantes :
  • push() : qui permet toujours d'ajouter un élément à la fin du tableau.
  • shift() : qui retire le premier élément du tableau, réduisant ainsi sa taille de 1 tout en décalant les autres éléments vers la gauche.

Encore une fois, vous pouvez faire une file inversée en ajoutant des éléments au début, et en les retirant par la fin ; mais mieux vaut rester le plus proche possible de la réalité !

Exemple d'utilisation d'une file :
monTableau.push(6);  // On ajoute un 6e élément    
monTableau.shift();   // On retire le 1    
monTableau.shift();   // On retire le 2    
monTableau.push(monTableau.shift()); // On met le premier élément à la fin !    
/* Le tableau résultant est [4|5|6|3] */

Quand les utiliser ?


L'utilisation des piles et des files s'imposera à vous. Si je fais cette astuce, c'est justement parce que j'en ai eu besoin pas plus tard qu'hier. Je devais en effet gérer les événements onKeyUp d'une input de type texte, le but étant de remplacer ce que tapait l'utilisateur par autre chose... tout en le mémorisant !

Seulement voilà, si l'utilisateur tapait trop vite, les événements onKeyUp se mélangeaient et je récupérais en sortie quelque chose de totalement faussé. J'ai donc créé une file me permettant de stocker rapidement au fur et à mesure, la totalité des lettres tapées, quitte à les traiter plus tard. Le problème était résolu.

Je ne vais donc pas vous donner des cas dans lesquels utiliser ces structures. Mon but était plutôt de vous les faire connaitre, afin que vous y pensiez la prochaine fois.

A voir également :

Ce document intitulé «  Les piles et les files en Javascript  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.