Anwendungsbeispiel eines JavaScript-Datenstrukturstapels

Der Inhalt dieses Artikels befasst sich mit Anwendungsbeispielen für den JavaScript-Datenstrukturstapel. Ich hoffe, dass er hilfreich ist Du.

Stack

Schauen wir uns zuerst eine Frage an

Leetcode 32 Longest Valid Parentheses (Longest Valid Parentheses)

Gegeben ein For eine Zeichenfolge, die nur „(“ und „)“ enthält, ermitteln Sie die Länge der längsten Teilzeichenfolge, die gültige Klammern enthält.

Beispiel 1:

Eingabe: „(()“
Ausgabe: 2
Erklärung: Die längste gültige Klammer-Teilzeichenfolge ist „()“

Beispiel 2:

Eingabe: ")()())"
Ausgabe: 4
Erklärung: Die längste gültige Klammer-Teilzeichenfolge ist "()()"

Dieses Problem kann durch dynamische Programmierung oder durch einen prägnanten und übersichtlichen Stapel gelöst werden.

Was ist ein Stapel?

Der Stapel ist eine LIFO-geordnete Sammlung (First-In, Last-Out), mit neu hinzugefügten Elementen oben im Stapel und alten Elementen unten.

Wie in der Abbildung unten gezeigt, werden 1, 2, 3, 4, 5, 6 und 7 nacheinander in den Stapel geschoben:

Stapel erstellen

Erstellen Sie eine Klasse, um den Stapel darzustellen:

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();

Hinweis

Da private Mitglieder nicht vorübergehend in JavaScript-Klassen definiert werden können, können die Array-Elemente, die Stapelelemente speichern, dies tun Der Zugriff außerhalb der Klasse ist sehr gefährlich.

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

Sie können Schließungen und IIFE verwenden, um dies zu vermeiden:

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 ist eine Sammlung von Schlüssel-Wert-Paaren ähnlich wie Map, aber die Schlüssel von WeakMap sind schwache Referenzen. Solange keine Referenz vorhanden ist, fordert der Garbage-Collection-Mechanismus den belegten Speicher zurück, was einem automatischen Löschen ohne entspricht manuelles Löschen.

Stack zum Lösen von Problemen verwenden

Idee:

1. Variable start speichert den Anfangsindex gültiger Klammern und maxLen speichert das Maximum Länge;

2. Der Stapel speichert nur den Index der linken Klammer. Wenn eine linke Klammer angetroffen wird, wird ihr Index im Stapel gespeichert 🎜>Wenn eine rechte Klammer angetroffen wird und der Stapel zu diesem Zeitpunkt leer ist, überspringen Sie diese Schleife und aktualisieren Sie

   ; wenn der Stapel nicht leer ist, entfernen Sie das oberste Element des Stapels

3. startNachdem das oberste Element des Stapels entfernt wurde und der Stapel leer ist, berechnen Sie den Abstand zwischen dem aktuellen Index und

   und aktualisieren Sie

4. start Wenn das oberste Element des Stapels entfernt wurde und der Stapel nicht leer ist, berechnen Sie den Abstand zwischen dem aktuellen Index und dem oben im Stapel gespeicherten Index und aktualisieren Sie maxLen

5. Schleifen bis zum Ende.

   maxLen

   function test(str) {
       let stack = new Stack();
       let start = 0;
       let maxLen = 0;
   
       for(let i=0; i<str.length; i++) {
           // 如果是左括号，下标入栈
           if (str[i] == &#39;(&#39;) {
               stack.push(i);
           } else {
               // 如果是右括号
               /* 栈内为空，说明本次有效括号匹配已结束，跳过本次循环并更新 start */
               if (stack.isEmpty()) {
                   start = i+1;
                   continue;
               } else {
                   // 栈内不为空，则出栈一个左括号进行匹配
                   stack.pop();
                   // 栈顶元素出栈后，栈为空
                   if (stack.isEmpty()) {
                       // 根据当前下标和 start 去更新 maxLen
                       maxLen = Math.max(maxLen, i-start+1);
                   } else {
                       // 栈不为空，根据当前下标和栈顶存放的下标去更新 maxLen
                       maxLen = Math.max(maxLen, i-stack.peek());
                   }
                   
               }
           }       
       }
       
       return maxLen;
   }
   
   test(&#39;(()&#39;); // 2
   test(&#39;)()())&#39;); // 4

Das obige ist der detaillierte Inhalt vonAnwendungsbeispiel eines JavaScript-Datenstrukturstapels. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!