怎么在JavaScript中使用棧

怎么在JavaScript中使用棧？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

JavaScript的特點

1.JavaScript主要用來向HTML頁面添加交互行為。 2.JavaScript可以直接嵌入到HTML頁面，但寫成單獨的js文件有利于結構和行為的分離。 3.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

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。