Maison > Article > interface Web > 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.
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.
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é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();
É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.
Idée :
La variable start
stocke l'indice de départ des parenthèses valides et maxLen
stocke le maximum length;
La pile stocke uniquement l'indice du crochet gauche lorsqu'un crochet gauche est rencontré, son indice est stocké dans la pile
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
, et mettez à jour start
maxLen
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!