Explication détaillée de la structure des données JavaScript et des compétences de l'algorithme stack_javascript

Dans le article précédent le blog a présenté la liste suivante. La liste est la structure la plus simple, mais si vous voulez traiter des structures plus complexes, la liste est trop simple, nous avons donc besoin d'une sorte. of et Lists sont similaires mais plus complexes aux structures de données - les piles. 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, cette opération est donc rapide et facile à mettre en œuvre.

1 : Opérations sur la pile.

La pile est un type spécial de liste. Les éléments de la pile ne sont accessibles que par une extrémité de la liste, qui est le haut de la pile. Par exemple, lorsque vous faites la vaisselle dans un restaurant, vous ne pouvez d'abord laver que l'assiette supérieure. Une fois l'assiette lavée, elle ne peut être vissée qu'au sommet de la pile d'assiettes. La pile est une structure de données appelée « dernier entré, premier sorti » (LIFO).

Étant donné que la pile a la caractéristique dernier entré, premier sorti, tout élément qui ne se trouve pas en haut de la pile n'est pas accessible. Afin d'obtenir l'élément en bas de la pile, l'élément au-dessus doit l'être. retiré en premier. Les deux opérations principales que nous pouvons effectuer sur la pile sont de pousser un élément sur la pile et de retirer un élément de la pile. Nous pouvons utiliser la méthode push() pour pousser dans la pile et la méthode pop() pour sortir de la pile. Bien que la méthode pop() puisse accéder à l'élément en haut de la pile, après avoir appelé cette méthode, l'élément en haut de la pile est définitivement supprimé de la pile. Une autre méthode couramment utilisée est peek(), qui renvoie uniquement l'élément supérieur de la pile sans le supprimer.

Le schéma réel de poussée et de saut sur la pile est le suivant :

push(), pop() et peek() sont les trois méthodes principales de la pile, mais la pile a d'autres méthodes et propriétés. Comme suit :

clear() : Efface tous les éléments de la pile.

length() : enregistre le nombre d'éléments dans la pile.

2 : La mise en œuvre de la stack est la suivante :

On peut commencer par implémenter les méthodes de la classe stack comme suit :

Copier le code Le code est le suivant :

fonction Pile() {
This.dataStore = [];
Ceci.top = 0;
>

Comme ci-dessus : dataStore enregistre tous les éléments de la pile. La variable top enregistre la position du haut de la pile et est initialisée à 0. Cela signifie que la position de départ du tableau correspondant au haut de la pile est 0, si un élément est poussé sur la pile. La valeur de la variable changera en conséquence.

Nous avons également les méthodes suivantes : push(), pop(), peek(), clear(), length();

1. Méthode Push() ; lorsque vous poussez un nouvel élément dans la pile, il doit être enregistré à la position correspondant à la variable supérieure dans le tableau, puis la valeur supérieure est augmentée de 1 pour pointer vers le suivant. position dans le tableau. Le code suivant :

Copier le code Le code est le suivant :

fonction push(élément) {
This.dataStore[this.top] = élément;
>

2. La méthode pop() est à l'opposé de la méthode push() : elle renvoie l'élément supérieur de la pile et décrémente la valeur supérieure de 1. Le code suivant :

Copier le code Le code est le suivant :

fonction pop(){
         return this.dataStore[--this.top];
>

3. La méthode peek() renvoie l'élément en première position du tableau, qui est l'élément supérieur de la pile
;

Copier le code Le code est le suivant :

Fonction coup d'oeil(){
          return this.dataStore[this.top - 1];
>

4. Méthode length() Parfois, nous avons besoin de savoir combien d'éléments il y a dans la pile. Nous pouvons renvoyer le nombre d'éléments dans la pile en renvoyant la valeur de la variable top, comme indiqué dans le code suivant :
.

Copier le code Le code est le suivant :

Longueur de la fonction(){
           return this.top;
>

5. clear(); Parfois, nous voulons vider la pile, nous définissons la valeur supérieure de la variable sur 0 avec le code suivant :

Copier le code Le code est le suivant :

fonction clear() {

this.top = 0;

}

Tous les codes ci-dessous :

Copier le code Le code est le suivant :

fonction Pile() {
This.dataStore = [];
Ceci.top = 0;
>

Stack.prototype = {
 
//Pousse un nouvel élément dans la pile
Push : fonction (élément) {
This.dataStore[this.top] = élément;
},
// Accédez à l'élément supérieur de la pile, l'élément supérieur de la pile est définitivement supprimé
pop : fonction(){
          return this.dataStore[--this.top];
},
// Renvoie l'élément en première position du tableau, c'est-à-dire l'élément supérieur de la pile
coup d'oeil : fonction(){
          return this.dataStore[this.top - 1];
},
//Combien d'éléments sont stockés dans la pile
longueur : fonction(){
         return this.top;
},
//Effacer la pile
; clair : fonction(){
Ceci.top = 0;
>
};

L'exemple de démonstration est le suivant :

var stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek()); // c

var popped = 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()); // non défini

Ci-dessous nous pouvons implémenter une définition récursive de la fonction factorielle telle que 5 ! La factorielle de 5 ! = 5*4*3*2*1;

Le code suivant :

Copier le code Le code est le suivant :

fonction fait(n) {
var s = new Stack();
; pendant que(n > 1) {
s.push(n--);
>
var produit = 1;
Tandis que(s.length() > 0) {
Produit *= s.pop();
>
Retourner le produit ;
>
console.log(fact(5));

La signification du code ci-dessus est la suivante : passez d'abord le chiffre 5 dans la fonction, utilisez une boucle while et poussez la fonction push() en utilisant la pile dans la pile avant de la décrémenter de 1 à chaque fois jusqu'à ce que la variable n soit moins de 1. Définissez ensuite une variable product ; utilisez la méthode length() de la pile pour déterminer si elle est supérieure à 0 et exécutez product* = s.pop() à chaque fois ; la méthode pop() renvoie l'élément supérieur de la pile et la supprime ; l'élément de la pile. Ainsi, à chaque exécution, un élément est supprimé jusqu'à ce que s.length() <= 0. Donc product = 5*4*3*2*1 et autres opérations.