首頁 > web前端 > js教程 > 主體

JavaScript資料結構之棧的用法範例

不言
發布: 2019-01-18 11:10:37
轉載
2122 人瀏覽過

這篇文章帶給大家的內容是關於JavaScript資料結構之棧的用法範例,有一定的參考價值,有需要的朋友可以參考一下,希望對你有所幫助。

堆疊

先來看一題

Leetcode 32 Longest Valid Parentheses (最長有效括號)

給定一個只包含'(' 和')' 的字串,找出最長的包含有效括號的子字串的長度。

範例1:

輸入: "(()"
輸出: 2
解釋: 最長有效括號子字串為 "()"

#範例2:

輸入: ")()())"
輸出: 4
解釋: 最長有效括號子字串為 "()()"

這題可以用動態規劃來做,也能用簡潔明了的堆疊來解決。

什麼是堆疊?

堆疊是一種先進後出(LIFO)的有序集合,新加入的元素在堆疊頂,舊元素在堆疊底部。

以下圖為例,1、2、3、4、5、6、7先後進堆疊:

JavaScript資料結構之棧的用法範例

建立堆疊

建立一個類別來表示堆疊:

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();
登入後複製

注意

因為JavaScript 的類別內暫時無法定義私有成員,所以可以在類別外存取到儲存堆疊元素的陣列items,這個操作是很危險的。

stack.items; // [1, 2, 3, 4]
登入後複製

這時可以使用閉包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的鍵是弱引用的,只要不存在引用,垃圾回收機制就會回收掉佔用的內存,相當於自動刪除,而不用手動刪除。

用堆疊解題

想法:

  1. 變數start存放有效括號起始下標,maxLen 存放最大長度;

  2. 堆疊只存放左括號的下標,遇到左括號,將其下標存入堆疊中;

  3. #遇到右括號,若此時棧為空,跳過本次循環並更新start;若棧不為空,則棧頂元素出棧;

  4. #堆疊頂元素出棧後,若堆疊為空,則計算目前下標與start的距離,並更新maxLen;

  5. 堆疊頂元素出棧後,若堆疊不為空,則計算目前下標和棧頂存放的下標的距離,並更新maxLen;

  6. 循環遍歷直至結束。

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
登入後複製

以上是JavaScript資料結構之棧的用法範例的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:cnblogs.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板