Comment implémenter une pile en JavaScript

Cet article présente principalement comment utiliser JavaScript pour implémenter une pile, qui a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

Qu'est-ce qu'une pile

<.>

• Une pile est une collection ordonnée qui suit le principe du dernier entré, premier sorti (LIFO).

• Les éléments nouvellement ajoutés ou à supprimer sont stockés à la fin de la pile, appelée haut de la pile, et l'autre extrémité est appelée bas de la pile.

• Dans la pile, les nouveaux éléments sont proches du haut de la pile et les anciens éléments sont proches du bas de la pile

Exemples concrets

De nombreux exemples de stacks peuvent être trouvés dans la vie. Par exemple, parmi les assiettes empilées dans la cuisine, celles du dessus sont toujours utilisées en premier ; lorsque le contenu de la zone de saisie est supprimé, la dernière entrée est toujours supprimée en premier, les balles du chargeur sont tirées en premier telles quelles ; chargé plus tard....

Implémenter manuellement une pile

Tout d'abord, créez une classe pour représenter la pile

function Stack () { }

Nous devons choisir une structure de données à enregistrer les éléments de la pile, vous pouvez choisir le tableau

function Stack(){
    var items = [];     //用来保存栈里的元素
}

Ensuite, ajoutez quelques méthodes à la pile

push(element(s));   //添加新元素到栈顶
pop();              //移除栈顶的元素，同时返回被移除的元素
peek();             //返回栈顶的元素，不对栈做任何修改
isEmpty();          //如果栈里没有任何元素就返回true，否则false
clear();            //移除栈里的所有元素
size();             //返回栈里的元素个数,类似于数组的length属性

La première méthode que nous devons implémenter est

. Utilisée pour ajouter de nouveaux éléments à la pile, une chose est très importante : cette méthode n'ajoute que le haut de la pile, qui est la fin de la pile. Par conséquent, vous pouvez écrire comme ceci : push

this.push = function (element) {
    items.push(element);
}

En utilisant la méthode push du tableau, vous pouvez ajouter un nouvel élément à la fin du haut de la pile.

Ensuite, implémentez la méthode

pour supprimer des éléments de la pile. La pile suit le principe LIFO (dernier entré, premier sorti). Ce qui est supprimé est le dernier élément ajouté. Par conséquent, vous pouvez utiliser la méthode pop du tableau. pop

this.pop = function () {
    return items.pop();
}

De cette façon, cette pile suit naturellement le principe LIFO

Ajoutons maintenant des méthodes auxiliaires supplémentaires à cette pile.

Si vous souhaitez connaître le dernier élément ajouté à la pile, vous pouvez utiliser la méthode

. Cette méthode renverra l'élément en haut de la pile peek

this.peek = function () {
    return items[items.length-1];
}

Parce que la classe utilise un tableau pour enregistrer les éléments, donc ici pour accéder au dernier élément du tableau, utilisez

length-1

La prochaine méthode à implémenter est

, si la pile est vide, elle renvoie vrai, sinon elle renvoie faux : isEmpty

this.isEmpty = function () {
    return items.length == 0;
}

En utilisant la méthode isEmpty, vous pouvez simplement déterminer si la pile est vide.

Semblable à la propriété length du tableau, nous pouvons également implémenter la longueur de la pile.

this.size = function () {
    return items.length;
}

Étant donné que la pile utilise un tableau en interne pour stocker des éléments, la longueur du tableau est la longueur de la pile.

implémente la méthode

et la méthode clear est utilisée pour effacer tous les éléments de la pile. La méthode d'implémentation la plus simple est : clear

this.clear = function () {
    items = [];
}

En fait, il est également possible d'appeler la méthode pop plusieurs fois, mais ce n'est pas aussi simple et rapide que cette méthode.

Enfin, afin de vérifier le contenu de la pile, vous devez implémenter une méthode d'assistance :

. Il affichera tous les éléments de la pile sur la console : print

this.print = function () {
    console.log(items.toString());
}

À ce stade, nous avons complètement créé une

pile !

Code complet de la pile

function Stack(){

    var items = [];     //用来保存栈里的元素

    this.push = function (element) {
        items.push(element);
    }

    this.pop = function () {
        return items.pop();
    }

    this.peek = function () {
        return items[items.length-1];
    }

    this.isEmpty = function () {
        return items.length == 0;
    }

    this.size = function () {
        return items.length;
    }

    this.clear = function () {
        items = [];
    }

    this.print = function () {
        console.log(items.toString());
    }
}

Utilisation de la classe Stack

La pile a été créée, testons-la

Tout d'abord, initialisons la classe Stack. Ensuite, vérifiez si la pile est vide

var stack = new Stack();
console.log(stack.isEmpty());         //控制台输出true

Ensuite, ajoutez un élément à la pile :

stack.push(5);
stack.push(8);

Si vous appelez la méthode peek, elle affichera évidemment 8, car elle C'est l'élément en haut de la pile :

console.log(stack.peek());            //控制台输出8

Ajouter un autre élément :

stack.push(11);
console.log(stack.size());            //控制台输出3

Nous en avons ajouté 11 autres à la pile. Si la méthode size est appelée, le résultat est 3 car il y a trois éléments sur la pile (5, 8 et 11). Si vous appelez la méthode isEmpty à ce moment, vous verrez un faux résultat (car la pile n'est pas vide à ce moment). Enfin, ajoutez-y un autre élément :

stack.push(15);

Ensuite, appelez deux fois la méthode pop pour supprimer deux éléments de la pile :

stack.pop();
stack.pop();
console.log(stack.size());            //控制台输出2
stack.print();                        //控制台输出[5,8]

À ce stade, la fonction de l'ensemble Test de pile terminé.

Utilisez la pile pour résoudre le problème

Utilisez la pile pour terminer la conversion hexadécimale.

Dans la vraie vie, on utilise principalement la base 10, mais en informatique, le binaire est très important, car tout dans l'ordinateur est représenté par les nombres binaires 0 et 1. Les cours d'informatique dans les universités enseigneront d'abord la conversion de base. Prenons l'exemple du binaire :

function pideBy2 (decNumber) {

    var remStack = new Stack(),
    rem,
    binaryString = '';

    while (decNumber>0) {  //{1}
        rem = Math.floor(decNumber % 2);  //{2}
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / 2);  //{4}
    }

    while (!remStack.isEmpty()) {  //{5}
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

Dans ce code, lorsque le résultat remplit la condition d'être divisible par 2, (ligne {1}), nous obtiendrons le courant Le résultat et le reste de 2 sont placés sur la pile (lignes {2}, {3}). Ensuite, laissez le résultat être divisé également par 2 (ligne {4})

Remarque : JavaScript a un type numérique, mais il ne fait pas la distinction entre les entiers et les nombres à virgule flottante. Par conséquent, utilisez la fonction Math.floor pour que l'opération de division renvoie uniquement la partie entière.

Enfin, utilisez la méthode pop pour supprimer tous les éléments de la pile et concaténer les éléments sautés en une chaîne (ligne {5}).

Testez-le :

console.log(pideBy2(520));      //输出1000001000
console.log(pideBy2(10));       //输出1010
console.log(pideBy2(1000));     //输出1111101000

Ensuite, vous pouvez facilement modifier l'algorithme ci-dessus afin qu'il puisse convertir le nombre décimal en n'importe quelle base. En plus de convertir des nombres décimaux et la divisibilité par 2 en nombres binaires, vous pouvez également passer d'autres bases arbitraires comme paramètres, comme l'algorithme suivant :

function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = '';
    digits = '0123456789ABCDEF';     //{6}

    while (decNumber>0) {  
        rem = Math.floor(decNumber % base);
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。因此，需要对栈中的数字做个转化才可以（行{6}、{7}）。

来测试一下输出结果：

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

小结

我们用js代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多，比如平衡圆括号和汉诺塔。

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！

相关推荐：

如何利用js fetch实现ping效果

Node.js使用superagent模拟GET/POST的请求

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!