Les piles et les files

Nous allons ici aborder un concept que vous avez déjà rapidement étudié dans ce cours, mais qu'il serait bon de vous remettre en tête.

Les piles et les files sont deux manières de manipuler vos tableaux. Plutôt que de les voir comme de simples listes de données, vous pouvez les imaginer comme étant, par exemple, une pile de livres où le dernier posé sera au final le premier récupéré, ou bien comme une file d'attente, où le dernier entré sera le dernier sorti. Ces deux façons de faire sont bien souvent très pratiques dans de nombreux cas, vous vous en rendrez bien vite compte.

Retour sur les méthodes étudiées

Quatre méthodes ont été étudiées au cours des premiers chapitres de ce cours. Il est de bon ton de revenir sur leur utilisation avant d'entamer le sujet des piles et des files :

push() : ajoute un ou plusieurs éléments à la fin du tableau (un argument par élément ajouté) et retourne la nouvelle taille de ce dernier.
pop() : retire et retourne le dernier élément d'un tableau.
unshift() : ajoute un ou plusieurs éléments au début du tableau (un argument par élément ajouté) et retourne la nouvelle taille de ce dernier.
shift() : retire et retourne le premier élément d'un tableau.

Les piles

Les piles partent du principe que le premier élément ajouté sera le dernier retiré, comme une pile de livres ! Elles sont utilisables de deux manières différentes : soit avec les deux méthodes push() et pop(), soit avec les deux restantes unshift() et shift(). Dans le premier cas, la pile sera empilée et dépilée à la fin du tableau, dans le deuxième cas, les opérations se feront au début du tableau.

var myArray = ['Livre 1'];

var result = myArray.push('Livre 2', 'Livre 3');

alert(myArray); // Affiche : « Livre 1,Livre 2,Livre 3 »

alert(result); // Affiche : « 3 »

result = myArray.pop();

alert(myArray); // Affiche : « Livre 1,Livre 2 »

alert(result); // Affiche : « Livre 3 »

Aucun problème pour les méthodes push() et pop() ? Essayons maintenant le coupleunshift()/shift() :

var myArray = ['Livre 3'];

var result = myArray.unshift('Livre 1', 'Livre 2');

alert(myArray); // Affiche : « Livre 1,Livre 2,Livre 3 »

alert(result); // Affiche : « 3 »

result = myArray.shift();

alert(myArray); // Affiche : « Livre 2,Livre 3 »

alert(result); // Affiche : « Livre 1 »

Voilà pour les piles !

Les files

Les files partent d'un autre principe tout aussi simple : le premier élément ajouté est le premier sorti, comme une file d'attente. Elles sont, elles aussi, utilisables de deux manières différentes : soit avec le couple push()/shift(), soit avec le couple unshift()/pop().

En Javascript, les files sont bien moins utilisées que les piles, car elles sont dépendantes des méthodes unshift() et shift(). Ces dernières souffrent d'un manque de performance, nous y reviendrons.

var myArray = ['Fanboy 1', 'Fanboy 2'];

var result = myArray.push('Fanboy 3', 'Fanboy 4');

alert(myArray); // Affiche : « Fanboy 1,Fanboy 2,Fanboy 3,Fanboy 4 »

alert(result); // Affiche : « 4 »

result = myArray.shift();

alert(myArray); // Affiche : « Fanboy 2,Fanboy 3,Fanboy 4 »

alert(result); // Affiche : « Fanboy 1 »

Le couple unshift()/pop() est tout aussi simple d'utilisation :

var myArray = ['Fanboy 3', 'Fanboy 4'];

var result = myArray.unshift('Fanboy 1', 'Fanboy 2');

alert(myArray); // Affiche : « Fanboy 1,Fanboy 2,Fanboy 3,Fanboy 4 »

alert(result); // Affiche : « 4 »

result = myArray.pop();

alert(myArray); // Affiche : « Fanboy 1,Fanboy 2,Fanboy 3 »

alert(result); // Affiche : « Fanboy 4 »

Voilà pour les files !

Quand les performances sont absentes : unshift() et shift()

Revenons maintenant sur ce petit problème de performances. Les deux méthodes unshift() et shift()utilisent chacune un algorithme qui fait qu'en retirant ou en ajoutant un élément en début de tableau, elles vont devoir réécrire tous les index des éléments qui suivent. En gros, prenons un tableau de ce style :

0 => 'test 1'

1 => 'test 2'

2 => 'test 3'

En ajoutant un élément en début de tableau, nous cassons l'indexation :

0 => 'test supplémentaire'

0 => 'test 1'

1 => 'test 2'

2 => 'test 3'

Ce qui fait que nous devons réécrire tous les index suivants :

0 => 'test supplémentaire'

1 => 'test 1'

2 => 'test 2'

3 => 'test 3'

Si le tableau possède de nombreux éléments, cela peut parfois prendre un peu de temps. C'est ce qui fait que les piles sont généralement préférées aux files en Javascript, car elles peuvent se passer de ces deux méthodes. Cela dit, il faut relativiser : la perte de performance n'est pas dramatique, vous pouvez très bien vous en servir pour des tableaux de petite taille (en dessous de 10 000 entrées, en gros), mais au-dessus il faudra peut-être songer à utiliser les piles ou bien à utiliser des scripts qui résolvent ce genre de problèmes.

En résumé

Pour concaténer deux tableaux, il faut utiliser la méthode concat(), car l'opérateur + ne fonctionne pas selon le comportement voulu.
La méthode forEach() permet de parcourir un tableau en s'affranchissant d'une boucle for. Mais cette méthode n'est pas supportée par les versions d'Internet Explorer antérieures à la version 9.
indexOf() et lastIndexOf() permettent de rechercher un élément qui peut être une chaîne de caractères, un nombre, ou même un tableau. Il faudra toutefois faire attention lors de la comparaison de deux tableaux.
L'utilisation d'une fonction pour trier un tableau est possible et se révèle particulièrement utile pour effectuer un tri personnalisé.
Les piles et les files sont un moyen efficace pour stocker et accéder à de grandes quantités de données.

Créé avec HelpNDoc Personal Edition: Outil de création d'aide complet