Exemple d'utilisation de la pile de structures de données JavaScript

Le contenu de cet article concerne les exemples d'utilisation de la pile de structures de données JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. toi.

Pile

Regardons d'abord une question

Leetcode 32 parenthèses valides les plus longues (parenthèses valides les plus longues)

étant donné un pour une chaîne contenant uniquement '(' et ')', recherchez la longueur de la sous-chaîne la plus longue contenant des parenthèses valides.

Exemple 1 :

Entrée : "(()"
Sortie : 2
Explication : La sous-chaîne entre crochets valide la plus longue est "()"

Exemple 2 :

Entrée : ")()())"
Sortie : 4
Explication : La sous-chaîne entre crochets valide la plus longue est "()()"

Ce problème peut être résolu en utilisant une programmation dynamique, ou il peut être résolu en utilisant une pile concise et claire.

Qu'est-ce qu'une pile ?

La pile est une collection ordonnée premier entré, dernier sorti (LIFO), avec des éléments nouvellement ajoutés en haut de la pile et d'anciens éléments en bas.

Le chiffre suivant est un exemple, 1, 2, 3, 4, 5, 6, 7 sont poussés dans la pile l'un après l'autre :

Créer une pile

Créez une classe pour représenter la pile :

class Stack {
    // 初始化类，创建数组 items 存放入栈元素
    constructor() {
        this.items = [];
    }
    // push 方法进行元素入栈（可同时入栈一或多个元素），无返回值
    push() {
        this.items.push(...arguments);
    }
    // pop 方法出栈一个元素，返回出栈元素
    pop() {
        return this.items.pop();
    }
    // peek 方法返回栈顶元素，不对栈本身做任何操作
    peek() {
        return this.items[this.items.length-1];
    }
    // size 方法返回栈内元素个数
    size() {
        return this.items.length;
    }
    // isEmpty 方法查看栈是否为空，返回布尔值
    isEmpty() {
        return this.items.length == 0;
    }
    // clear 方法清空栈，无返回值
    clear() {
        this.items = [];
    }
    // print 方法打印栈内元素
    print() {
        console.log(this.items.toString());
    }
}

// 测试 
let stack = new Stack();
stack.push(1,2,3,4);
stack.print(); // 1,2,3,4
stack.isEmpty(); // false
stack.size(); // 4
stack.pop(); // 4
stack.peek(); // 3
stack.clear();

Remarque

Étant donné que les membres privés ne peuvent pas être définis temporairement dans les classes JavaScript, les éléments du tableau qui stockent les éléments de la pile est accessible en dehors de la classe. Cette opération est très dangereuse.

stack.items; // [1, 2, 3, 4]

Vous pouvez utiliser des fermetures et IIFE pour éviter cela. C'est une méthode très impuissante :

let Stack = (function () {
    // 使用 WeakMap 存储数组（数组存放进栈元素）
    let items = new WeakMap();
    class Stack {
        constructor() {
            items.set(this, []);
        }
        push() {
            items.get(this).push(...arguments);
        }
        // 其他方法
    }
    return Stack;
})();

let s = new Stack();
// 无法访问到 items
s.items; // undefined

WeakMap. : WeakMap est une collection de paires clé-valeur similaire à Map, mais la clé de WeakMap est une référence faible. Tant qu'il n'y a pas de référence, le mécanisme de récupération de place récupérera la mémoire occupée, qui est. équivalent à une suppression automatique. Pas besoin de supprimer manuellement.

Utiliser la pile pour résoudre des problèmes

Idée :

1. La variable start stocke l'indice de départ des parenthèses valides et maxLen stocke le maximum length;

2. La pile stocke uniquement l'indice du crochet gauche lorsqu'un crochet gauche est rencontré, son indice est stocké dans la pile

3. Lorsqu'un crochet droit est rencontré, si la pile est vide à ce moment, sautez cette boucle et mettez à jour start si la pile n'est pas vide, faites apparaître l'élément supérieur de la pile

4. Une fois l'élément supérieur de la pile sauté, si la pile est vide, calculez la distance entre l'indice actuel et

   , et mettez à jour startmaxLen

 ; Une fois l'élément supérieur de la pile affiché, si la pile n'est pas vide, calculez la distance entre l'indice actuel et l'indice stocké en haut de la pile et mettez à jour
5.  ; >

   boucles jusqu'à la fin. maxLen

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!