這篇文章帶給大家的內容是關於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; // undefinedWeakMap: 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中文網其他相關文章！
