這篇文章帶給大家的內容是關於JavaScript資料結構之棧的用法範例,有一定的參考價值,有需要的朋友可以參考一下,希望對你有所幫助。
Leetcode 32 Longest Valid Parentheses (最長有效括號)
給定一個只包含'(' 和')' 的字串,找出最長的包含有效括號的子字串的長度。
範例1:
輸入: "(()"
輸出: 2
解釋: 最長有效括號子字串為 "()"
#範例2:
輸入: ")()())"
輸出: 4
解釋: 最長有效括號子字串為 "()()"
這題可以用動態規劃來做,也能用簡潔明了的堆疊來解決。
堆疊是一種先進後出(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();
因為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
的鍵是弱引用的,只要不存在引用,垃圾回收機制就會回收掉佔用的內存,相當於自動刪除,而不用手動刪除。
想法:
變數start
存放有效括號起始下標,maxLen
存放最大長度;
堆疊只存放左括號的下標,遇到左括號,將其下標存入堆疊中;
#遇到右括號,若此時棧為空,跳過本次循環並更新start
;若棧不為空,則棧頂元素出棧;
#堆疊頂元素出棧後,若堆疊為空,則計算目前下標與start
的距離,並更新maxLen
;
堆疊頂元素出棧後,若堆疊不為空,則計算目前下標和棧頂存放的下標的距離,並更新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] == '(') { 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('(()'); // 2 test(')()())'); // 4
以上是JavaScript資料結構之棧的用法範例的詳細內容。更多資訊請關注PHP中文網其他相關文章!