JavaScript數(shù)據(jù)結(jié)構(gòu)之棧的用法案例

這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)之棧的用法案例，具有一定借鑒價(jià)值，需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓小編帶著大家一起了解一下。

棧

先來(lái)看一道題

這道題可以用動(dòng)態(tài)規(guī)劃來(lái)做，也能用簡(jiǎn)潔明了的棧來(lái)解決。

什么是棧？

棧是一種先進(jìn)后出（LIFO）的有序集合，新添加的元素在棧頂，舊元素在棧底。

以下圖為例，1、2、3、4、5、6、7先后進(jìn)棧：

創(chuàng)建棧

創(chuàng)建一個(gè)類來(lái)表示棧：

class Stack {
    // 初始化類，創(chuàng)建數(shù)組 items 存放入棧元素
    constructor() {
        this.items = [];
    }
    // push 方法進(jìn)行元素入棧（可同時(shí)入棧一或多個(gè)元素），無(wú)返回值
    push() {
        this.items.push(...arguments);
    }
    // pop 方法出棧一個(gè)元素，返回出棧元素
    pop() {
        return this.items.pop();
    }
    // peek 方法返回棧頂元素，不對(duì)棧本身做任何操作
    peek() {
        return this.items[this.items.length-1];
    }
    // size 方法返回棧內(nèi)元素個(gè)數(shù)
    size() {
        return this.items.length;
    }
    // isEmpty 方法查看棧是否為空，返回布爾值
    isEmpty() {
        return this.items.length == 0;
    }
    // clear 方法清空棧，無(wú)返回值
    clear() {
        this.items = [];
    }
    // print 方法打印棧內(nèi)元素
    print() {
        console.log(this.items.toString());
    }
}

// 測(cè)試 
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();

注意

因?yàn)?JavaScript 的類內(nèi)暫時(shí)無(wú)法定義私有成員，所以可以在類外訪問(wèn)到存儲(chǔ)棧元素的數(shù)組 items，這個(gè)操作是很危險(xiǎn)的。

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

這時(shí)可以使用閉包和IIFE進(jìn)行避免，這是一個(gè)很無(wú)奈的辦法：

let Stack = (function () {
    // 使用 WeakMap 存儲(chǔ)數(shù)組（數(shù)組存放進(jìn)棧元素）
    let items = new WeakMap();
    class Stack {
        constructor() {
            items.set(this, []);
        }
        push() {
            items.get(this).push(...arguments);
        }
        // 其他方法
    }
    return Stack;
})();

let s = new Stack();
// 無(wú)法訪問(wèn)到 items
s.items; // undefined

WeakMap: WeakMap是類似Map的鍵值對(duì)集合，但WeakMap的鍵是弱引用的，只要不存在引用，垃圾回收機(jī)制就會(huì)回收掉占用的內(nèi)存，相當(dāng)于自動(dòng)刪除，而不用手動(dòng)刪除。

用棧解題

思路：

1. 變量start存放有效括號(hào)起始下標(biāo)，maxLen存放最大長(zhǎng)度；

2. 棧只存放左括號(hào)的下標(biāo)，遇到左括號(hào)，將其下標(biāo)存入棧中；

3. 遇到右括號(hào)，若此時(shí)棧為空，跳過(guò)本次循環(huán)并更新start；若棧不為空，則棧頂元素出棧；

4. 棧頂元素出棧后，若棧為空，則計(jì)算當(dāng)前下標(biāo)和start的距離，并更新maxLen；

5. 棧頂元素出棧后，若棧不為空，則計(jì)算當(dāng)前下標(biāo)和棧頂存放的下標(biāo)的距離，并更新maxLen；

6. 循環(huán)遍歷直至結(jié)束。

function test(str) {
    let stack = new Stack();
    let start = 0;
    let maxLen = 0;

    for(let i=0; i<str.length; i++) {
        // 如果是左括號(hào)，下標(biāo)入棧
        if (str[i] == '(') {
            stack.push(i);
        } else {
            // 如果是右括號(hào)
            /* 棧內(nèi)為空，說(shuō)明本次有效括號(hào)匹配已結(jié)束，跳過(guò)本次循環(huán)并更新 start */
            if (stack.isEmpty()) {
                start = i+1;
                continue;
            } else {
                // 棧內(nèi)不為空，則出棧一個(gè)左括號(hào)進(jìn)行匹配
                stack.pop();
                // 棧頂元素出棧后，棧為空
                if (stack.isEmpty()) {
                    // 根據(jù)當(dāng)前下標(biāo)和 start 去更新 maxLen
                    maxLen = Math.max(maxLen, i-start+1);
                } else {
                    // 棧不為空，根據(jù)當(dāng)前下標(biāo)和棧頂存放的下標(biāo)去更新 maxLen
                    maxLen = Math.max(maxLen, i-stack.peek());
                }
                
            }
        }       
    }
    
    return maxLen;
}

test('(()'); // 2
test(')()())'); // 4

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享JavaScript數(shù)據(jù)結(jié)構(gòu)之棧的用法案例內(nèi)容對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，遇到問(wèn)題就找億速云，詳細(xì)的解決方法等著你來(lái)學(xué)習(xí)!