Maison > Article > interface Web > 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
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
, 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 pilefunction 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 StackLa pile a été créée, testons-laTout d'abord, initialisons la classe Stack. Ensuite, vérifiez si la pile est vide
var stack = new Stack(); console.log(stack.isEmpty()); //控制台输出trueEnsuite, 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()); //控制台输出8Ajouter un autre élément :
stack.push(11); console.log(stack.size()); //控制台输出3Nous 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èmeUtilisez 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)); //输出1111101000Ensuite, 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中文网!
相关推荐:
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!