JavaScript 데이터 구조 스택의 사용 예

이 글은 특정 참고값이 있는 JavaScript 데이터 구조 스택의 사용 예를 제공합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다. 당신에게 도움이 될 것입니다.

Stack

질문을 먼저 살펴보겠습니다

Leetcode 32 가장 긴 유효 괄호# 🎜🎜##🎜 🎜#'(' 및 ')'만 포함된 문자열에서 유효한 괄호를 포함하는 가장 긴 부분 문자열의 길이를 찾습니다.

예 1:

Input: "(()"

Output: 2

Explanation: 가장 긴 유효한 대괄호 하위 문자열은 "()"입니다. # 🎜🎜#

예 2:

Input: ")()())"

Output: 4

설명: 가장 긴 유효 괄호 The 하위 문자열은 "()()"입니다.

이 질문은 동적 프로그래밍이나 간결하고 명확한 스택을 사용하여 해결할 수 있습니다.

스택이란 무엇인가요?

스택은 LIFO(선입후출) 순서 컬렉션으로, 스택 상단에 새로 추가된 요소가 있고 스택 하단에 이전 요소가 있습니다.

예를 들어 다음 그림에서는 1, 2, 3, 4, 5, 6, 7이 차례로 스택에 푸시됩니다.

#🎜🎜 #

스택 만들기

스택을 나타내는 클래스 만들기:

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

Note

비공개 멤버는 사용할 수 없기 때문에 스택 요소를 저장하는 배열 항목에 외부적으로 액세스하는 것은 매우

Dangerous

작업입니다.

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

closure 및 IIFE를 사용하면 매우 무력한 방법입니다.

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은 Map과 유사한 키-값 쌍의 모음이지만 WeakMap의 키는 다음과 같습니다. 약한 참조 예, 참조가 없는 한 가비지 수집 메커니즘은 점유된 메모리를 회수합니다. 이는 수동 삭제가 아닌 자동 삭제와 동일합니다. IIFE进行避免，这是一个很无奈的办法：

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

WeakMap: WeakMap是类似Map的键值对集合，但WeakMap的键是弱引用的，只要不存在引用，垃圾回收机制就会回收掉占用的内存，相当于自动删除，而不用手动删除。

用栈解题

思路：

1. 变量start存放有效括号起始下标，maxLen存放最大长度；

2. 栈只存放左括号的下标，遇到左括号，将其下标存入栈中；

3. 遇到右括号，若此时栈为空，跳过本次循环并更新start；若栈不为空，则栈顶元素出栈；

4. 栈顶元素出栈后，若栈为空，则计算当前下标和start的距离，并更新maxLen；

5. 栈顶元素出栈后，若栈不为空，则计算当前下标和栈顶存放的下标的距离，并更新maxLen스택을 사용하여 문제 해결

아이디어:

6. 변수 start는 유효한 대괄호의 시작 첨자를 저장하고, maxLen은 최대 길이를 저장합니다.

#🎜🎜##🎜🎜#스택은 괄호의 첨자만 저장합니다. 왼쪽 대괄호, 왼쪽 대괄호가 발견되면 해당 첨자가 스택에 저장됩니다. #🎜🎜##🎜🎜##🎜🎜##🎜🎜#오른쪽 대괄호가 발견되면 이때 스택이 비어 있습니다. , 이 루프를 건너뛰고 start를 업데이트합니다. 스택이 비어 있지 않으면 스택의 최상위 요소가 팝됩니다. #🎜🎜##🎜🎜##🎜🎜##🎜🎜#다음 스택 요소가 팝되고, 스택이 비어 있으면 현재 첨자와 start 사이의 거리를 계산하고 maxLen을 업데이트합니다. #🎜🎜##🎜🎜# #🎜🎜##🎜🎜#스택의 최상위 요소가 팝된 후, 스택이 비어 있지 않으면 현재 첨자와 스택 상단에 저장된 첨자 사이의 거리를 계산하고 maxLen; #🎜🎜##🎜🎜##🎜🎜##🎜🎜#마칠 때까지 반복하고 탐색합니다. #🎜🎜##🎜🎜##🎜🎜#rrreee

위 내용은 JavaScript 데이터 구조 스택의 사용 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!