Maison >interface Web >js tutoriel >Structures de données et algorithmes en JavaScript (1) : compétences stack_javascript
Préface
Structures de données et algorithmes JavaScript est un livre qui l'explique de manière relativement simple. L'avantage est qu'il utilise le langage JavaScript pour décrire les structures de données couramment utilisées. De nombreux exemples dans le livre proviennent de questions d'entretien courantes, qui peuvent être considérées. pour rester dans l'air du temps, je l'ai regardé en amateur et je l'ai d'ailleurs enregistré
.Téléchargement du code git : https://github.com/JsAaron/data_structure.git
Structure de la pile
Liste spéciale, les éléments de la pile ne sont accessibles que par une extrémité de la liste, le haut de la pile
Structure de données dernier entré, premier sorti (LIFO, dernier entré, premier sorti)
Javascript fournit des méthodes exploitables, push et pop, mais pop supprimera les données de la pile
Une classe d'implémentation qui implémente une pile
La structure de données sous-jacente utilise des tableaux
Étant donné que pop supprime les données de la pile, vous devez implémenter une méthode de recherche peek
Mettre en œuvre une méthode de nettoyage claire
Trouver le nombre total d'éléments dans la longueur de la pile
Vérifiez s'il y a encore un élément vide
fonction push(élément){
This.dataStore[this.top] = élément;
>
fonction coup d'oeil(élément){
Renvoyez this.dataStore[this.top-1];
>
fonction pop(){
Renvoyez this.dataStore[--this.top];
>
fonction clear(){
Ceci.top = 0
>
longueur de la fonction(){
Renvoyez ceci.top
>
Palindrome
Un palindrome fait référence à un mot, un tableau ou une phrase identique d'avant en arrière 12321.abcba
L'idée la plus simple d'un palindrome est que si l'élément est inversé et égal à l'élément d'origine, cela signifie que c'est un palindrome
Vous pouvez utiliser cette classe de pile pour opérer ici
isPalindrome("aarra") //false
estPalindrome("aaraa") //true
Regardez cette fonction isPalindrome. Elle appelle en fait la classe Stack, puis pousse l'élément mot transmis à chaque unité décomposée dans la pile selon le principe de la pile, le principe du dernier entré, premier sorti. la méthode pop pour démonter cet élément, et enfin comparer l'avant et l'après montage S'ils sont égaux, c'est un palindrome
.Récursion
Utiliser la récursivité pour implémenter un algorithme factoriel
5 = 5*4*3*2*1 = 120
Utiliser la récursivité
Utiliser les opérations de pile
fait(5) //120
Poussez n = 5 de manière décrémentale sur la pile pendant while, puis via une boucle ou selon le principe du dernier entré, premier sorti de la pile, retirez celui le plus en avant et empilez-le avec le produit via la méthode pop