Article original : How to implement a stack in vanilla JavaScript and ES6
Par Prashant Yadav
Une pile est une collection ordonnée d'éléments qui suit le principe Last In First Out (LIFO). L'ajout et le retrait d'éléments se font à la même extrémité, c'est-à-dire au sommet. Les éléments les plus récents sont au sommet, et les éléments les plus anciens sont au bas.
Nous avons de nombreux exemples de piles autour de nous comme une pile de livres, une pile de plateaux ou de plats, etc.
Une pile est utilisée par les compilateurs dans les langages de programmation, par la mémoire de l'ordinateur pour stocker des variables et des appels de fonctions, et dans les éditeurs de texte pour effectuer des opérations d'annulation et de rétablissement.
Liste des opérations effectuées sur une pile
- push() : Ajoute un ou plusieurs éléments au sommet de la pile.
- pop() : Retire et retourne l'élément du sommet de la pile.
- peek() : Retourne l'élément du sommet de la pile.
- isEmpty() : Retourne
Truesi la pile est vide,Falsesinon. - clear() : Retire tous les éléments de la pile.
- size() : Retourne la taille de la pile.
Création d'une pile
Une approche classique
Nous allons implémenter une pile comme elle est implémentée dans d'autres langages en dehors de JavaScript.
Nous allons utiliser un tableau et une variable supplémentaire pour suivre les éléments.
function Stack(){ var items = []; var top = 0; // autres méthodes vont ici }
Ajouter un élément dans la pile
// Ajouter un élément dans la pile
this.push = function(element){ items[top++] = element } // top++, effectue d'abord l'opération puis incrémente la valeur
Retirer un élément de la pile
// Retirer un élément de la pile
this.pop = function(){ return items[--top]; } // --top, décrémente d'abord la valeur puis effectue l'opération
Voir l'élément du sommet de la pile
// Voir un élément dans la pile
this.peek = function(){ return items[top - 1]; }
Vérifier si la pile est vide
// La pile est-elle vide
this.isEmpty = function(){ return top === 0; }
Vider la pile
// Vider la pile
this.clear = function(){ top = 0; }
Taille de la pile
// Taille de la pile
this.size = function(){ return top; }
Implémentation complète de la pile
function Stack(){ var items = []; var top = 0; // autres méthodes vont ici
// Ajouter un élément dans la pile this.push = function(element){ items[top++] = element } // top++, effectue d'abord l'opération puis incrémente la valeur
// Retirer un élément de la pile this.pop = function(){ return items[--top]; } // --top, décrémente d'abord la valeur puis effectue l'opération
// Voir l'élément du sommet de la pile this.peek = function(){ return items[top - 1]; }
// La pile est-elle vide this.isEmpty = function(){ return top === 0; }
// Vider la pile this.clear = function(){ top = 0; }
// Taille de la pile this.size = function(){ return top; }
}
Exemple
Nous allons maintenant créer une nouvelle instance de ce que nous avons implémenté et vérifier si cela fonctionne correctement.
var stack = new Stack(); // création d'une nouvelle instance de Stack
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.peek());
console.log(stack.isEmpty());
console.log(stack.size());
console.log(stack.pop());
console.log(stack.size());
stack.clear();
console.log(stack.isEmpty());
Sortie : 3 false 3 3 2 true
Implémentation de la pile avec JavaScript
Nous allons implémenter une pile avec un tableau JavaScript qui a des méthodes intégrées comme push et pop.
function Stack(){ var items = []; // autres méthodes vont ici }
Ajouter un élément dans la pile
// Ajouter un élément dans la pile
this.push = function(element){ items.push(element); }
Retirer un élément de la pile
// Retirer un élément de la pile
this.pop = function(){ return items.pop(); }
Voir l'élément du sommet de la pile
// Voir l'élément du sommet de la pile
this.peek = function(){ return items[items.length - 1]; }
Vérifier si la pile est vide
// La pile est-elle vide
this.isEmpty = function(){ return items.length === 0; }
Vider la pile
// Vider la pile
this.clear = function(){ items.length = 0; }
Taille de la pile
// Taille de la pile
this.size = function(){ return items.length; }
Implémentation complète de la pile
function Stack(){ var items = []; // autres méthodes vont ici
// Ajouter un élément dans la pile this.push = function(element){ items.push(element); }
// Retirer un élément de la pile this.pop = function(){ return items.pop(); }
// Voir l'élément du sommet de la pile this.peek = function(){ return items[items.length - 1]; }
// La pile est-elle vide this.isEmpty = function(){ return items.length === 0; }
// Vider la pile this.clear = function(){ items.length = 0; }
// Taille de la pile this.size = function(){ return items.length; }
}
Rendre les propriétés et méthodes privées avec une fermeture et IIFE (Immediately Invoked Function Expression).
var Stack = (function () { return function Stack(){ var items = []; // autres méthodes vont ici
// Ajouter un élément dans la pile this.push = function(element){ items.push(element); }
// Retirer un élément de la pile this.pop = function(){ return items.pop(); }
// Voir l'élément du sommet de la pile this.peek = function(){ return items[items.length - 1]; }
// La pile est-elle vide this.isEmpty = function(){ return items.length === 0; }
// Vider la pile this.clear = function(){ items.length = 0; } // Taille de la pile this.size = function(){ return items.length; } }})();
Pile utilisant ES6.
class Stack{ constructor(){ this.items = []; } // autres méthodes vont ici // Ajouter un élément dans la pile push = function(element){ this.items.push(element); }
// Retirer un élément de la pile pop = function(){ return this.items.pop(); } // Voir l'élément du sommet de la pile peek = function(){ return this.items[this.items.length - 1]; }
// La pile est-elle vide isEmpty = function(){ return this.items.length === 0; }
// Vider la pile clear = function(){ this.items.length = 0; } // Taille de la pile size = function(){ return this.items.length; }}
Pile utilisant ES6 WeakMap.
const items = new WeakMap();class Stack{ constructor(){ items.set(this, []); } // autres méthodes vont ici // Ajouter un élément dans la pile push = function(element){ let temp = items.get(this); temp.push(element); }
// Retirer un élément de la pile pop = function(){ let temp = items.get(this); return temp.pop(); } // Voir l'élément du sommet de la pile peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
// La pile est-elle vide isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
// Vider la pile clear = function(){ let temp = items.get(this); temp.length = 0; } // Taille de la pile size = function(){ let temp = items.get(this); return temp.length; }}
Rendre les propriétés et méthodes privées avec une fermeture et IIFE (Immediately Invoked Function Expression) pour la pile utilisant ES6 WeakMap.
let Stack = (() => { const items = new WeakMap(); return class Stack{ constructor(){ items.set(this, []); }
// autres méthodes vont ici // Ajouter un élément dans la pile push = function(element){ let temp = items.get(this); temp.push(element); }
// Retirer un élément de la pile pop = function(){ let temp = items.get(this); return temp.pop(); }
// Voir l'élément du sommet de la pile peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
// La pile est-elle vide isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
// Vider la pile clear = function(){ let temp = items.get(this); temp.length = 0; }
// Taille de la pile size = function(){ let temp = items.get(this); return temp.length; } }})();
Complexité temporelle
# Moyenne
Accès : Θ(N)
Recherche : Θ(N)
Insertion : Θ(1)
Suppression : Θ(1)
# Pire
Accès : O(N)
Recherche : O(N)
Insertion : O(1)
Suppression : O(1)
Complexité spatiale
# Pire: O(N)
Il existe de nombreux problèmes où la pile peut être la structure de données parfaite nécessaire pour la solution.
Si vous avez aimé cet article, n'hésitez pas à lui donner des ? et à le partager ! Si vous avez des questions à ce sujet, n'hésitez pas à me les poser.
Pour plus de contenu comme celui-ci et des solutions algorithmiques en JavaScript, suivez-moi sur Twitter. J'écris sur ES6, React, Nodejs, Structures de données, et Algorithmes sur learnersbucket.com_.