Dans le blog précédent, j'ai présenté la liste suivante. La liste est la structure la plus simple, mais si vous souhaitez gérer des structures plus complexes, la liste semble trop simple, nous avons donc besoin d'une structure de données similaire à la liste mais plus complexe - la pile. La pile est une structure de données efficace, car les données ne peuvent être ajoutées ou supprimées qu'en haut de la pile, donc cette opération est très rapide et facile à implémenter.
1: Fonctionnement sur la pile.
Une pile est une liste spéciale. Les éléments de la pile ne sont accessibles que via une extrémité de la liste, et cette fin est le haut de la pile. Par exemple, lorsque vous lavez la vaisselle dans un restaurant, vous ne pouvez que laver la plaque supérieure en premier. Après avoir lavé la vaisselle, vous ne pouvez que faire escarger le haut de la pile de plats. La pile est appelée structure de données "tardif-premier-out" (LIFO).
Étant donné que la pile a les caractéristiques de la remise en arrière, en premier, aucun élément qui n'est pas en haut de la pile ne peut être accessible. Afin d'obtenir des éléments avec une pile basse, l'élément ci-dessus doit être supprimé en premier. Les deux opérations principales que nous pouvons faire avec la pile sont de pousser un élément sur la pile et de faire entrer un élément sur la pile. Lors de la saisie de la pile, nous pouvons utiliser la méthode de la méthode push (), et lorsque nous la mettons, nous pouvons utiliser la méthode pop (). Bien que la méthode POP () puisse accéder aux éléments en haut de la pile, après avoir appelé la méthode, les éléments en haut de la pile sont supprimés en permanence de la pile. Une autre méthode que nous utilisons est Peek (), qui ne renvoie que l'élément supérieur de la pile sans le supprimer.
Les diagrammes de colonne réels de l'entrée de pile et de la sortie de la pile sont les suivants:
push (), pop () et peek () sont les trois principales méthodes de la pile, mais la pile a d'autres méthodes et propriétés. comme suit:
clear (): effacer tous les éléments de la pile.
Length (): Enregistrez le nombre d'éléments dans la pile.
Deux: l'implémentation de la pile est la suivante:
Nous pouvons d'abord commencer par implémenter la méthode de la classe de pile; comme suit:
La copie de code est la suivante:
function stack () {
this.datastore = [];
this.top = 0;
}
Comme ci-dessus: Datastore enregistre tous les éléments de la pile. Le supérieur variable enregistre la position en haut de la pile et est initialisé à 0. Cela signifie que la position de départ du tableau correspondant en haut de la pile est 0, si un élément est poussé dans la pile. La valeur de cette variable changera en conséquence.
Nous avons également les méthodes suivantes: push (), pop (), peek (), clear (), le long ();
1. Méthode push (); Lorsque vous poussez un nouvel élément dans la pile, il doit être enregistré dans le tableau correspondant au sommet variable, puis la valeur supérieure est augmentée de 1, de sorte qu'elle pointe vers la position suivante dans le tableau. Le code suivant:
La copie de code est la suivante:
fonction push (élément) {
this.datastore [this.top ++] = élément;
}
2. La méthode pop () est opposée à la méthode push () - il renvoie l'élément supérieur et déduit la valeur supérieure par 1. Le code suivant:
La copie de code est la suivante:
fonction pop () {
renvoie this.datastore [- this.top];
}
3. La méthode peek () renvoie l'élément à la position supérieure du tableau, c'est-à-dire l'élément supérieur de la pile;
La copie de code est la suivante:
fonction peek () {
Renvoie ce.datastore [this.top - 1];
}
4. Méthode Longueur () Parfois, nous devons savoir combien il y a d'éléments dans la pile. Nous pouvons renvoyer le nombre d'éléments dans la pile en renvoyant la valeur supérieure de la variable, comme indiqué dans le code suivant:
La copie de code est la suivante:
Longueur de fonction () {
Renvoyez ce.top;
}
5. Clear (); Parfois, nous voulons effacer la pile et nous définissons la valeur supérieure de la variable sur 0; Le code suivant:
La copie de code est la suivante:
fonction clear () {
this.top = 0;
}
Tous les codes ci-dessous:
La copie de code est la suivante:
function stack () {
this.datastore = [];
this.top = 0;
}
Stack.prototype = {
// Appuyez sur un nouvel élément dans la pile
push: fonction (élément) {
this.datastore [this.top ++] = élément;
},
// accéder à l'élément supérieur de la pile, l'élément supérieur de la pile est supprimé en permanence
pop: function () {
renvoie this.datastore [- this.top];
},
// renvoie l'élément en position supérieure dans le tableau, c'est-à-dire l'élément supérieur de la pile
peek: function () {
Renvoie ce.datastore [this.top - 1];
},
// Combien d'éléments sont stockés dans la pile
longueur: function () {
Renvoyez ce.top;
},
// efface la pile
Clear: function () {
this.top = 0;
}
};
Des exemples de démos sont les suivants:
var stack = new Stack ();
stack.push ("a");
stack.push ("b");
stack.push ("c");
console.log (stack.length ()); // 3
console.log (stack.Peek ()); // c
var poppped = stack.pop ();
Console.log (Popped); // c
console.log (stack.Peek ()); // b
stack.push ("d");
console.log (stack.Peek ()); // d
stack.clear ();
console.log (stack.length ()); // 0
console.log (stack.Peek ()); // indéfini
Ci-dessous, nous pouvons implémenter une définition récursive d'une fonction factorielle; Par exemple, 5! Factorielle 5! = 5 * 4 * 3 * 2 * 1;
Le code suivant:
La copie de code est la suivante:
Fonction Fact (n) {
var s = new Stack ();
tandis que (n> 1) {
S.push (n--);
}
produit var = 1;
while (s.length ()> 0) {
produit * = s.pop ();
}
produit de retour;
}
console.log (fait (5));
Le code ci-dessus signifie: transmettez d'abord le numéro 5 dans la fonction, utilisez une boucle while, et avant de décrémenter 1 à chaque fois, push () de la fonction que vous utilisez à la pile jusqu'à ce que la variable n soit inférieure à 1. Définissez ensuite un produit variable; Déterminez s'il est supérieur à 0 par la méthode de longueur () de la pile, et chaque fois que la méthode du produit * = s.pop () est exécutée, la méthode POP () renvoie l'élément supérieur de la pile et supprime l'élément de la pile. Ainsi, chaque fois que vous exécutez, supprimez un élément jusqu'à S.Length () <= 0. Donc Product = 5 * 4 * 3 * 2 * 1. etc.