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

Copier le code Le code est le suivant :

fonction Pile(){
This.dataStore = []
Ceci.top = 0;
This.push = pousser
Ceci.pop = pop
This.peek = coup d'oeil
This.length = longueur;
>

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

Copier le code Le code est le suivant :

la fonction estPalindrome(mot) {
var s = new Stack()
pour (var i = 0; i < word.length; i ) {
s.push(mot[i])
>
var rword = "";
while (s.length() > 0) {
         rword = s.pop();
>
Si (mot == rmot) {
        return true ;
} autre {
         return false ;
>
>

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é

Copier le code Le code est le suivant :

fonction factorielle(n) {
Si (n === 0) {
Retour 1 ;
} autre {
          return n * factorial(n - 1);
>
>

Utiliser les opérations de pile

Copier le code Le code est le suivant :

fonction fait(n) {
var s = new Stack()
tandis que (n > 1) {
              //[5,4,3,2]
s.push(n--);
>
var produit = 1;
while (s.length() > 0) {
Produit *= s.pop();
>
Retourner le produit ;
>

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