怎么在JavaScript中使用棧?很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細講解,有這方面需求的人可以來學習下,希望你能有所收獲。
成都創(chuàng)新互聯公司專業(yè)為企業(yè)提供米東網站建設、米東做網站、米東網站設計、米東網站制作等企業(yè)網站建設、網頁設計與制作、米東企業(yè)網站模板建站服務,十載米東做網站經驗,不只是建網站,更提供有價值的思路和整體網絡服務。
1.JavaScript主要用來向HTML頁面添加交互行為。 2.JavaScript可以直接嵌入到HTML頁面,但寫成單獨的js文件有利于結構和行為的分離。 3.JavaScript具有跨平臺特性,在絕大多數瀏覽器的支持下,可以在多種平臺下運行。
棧
先來看一道題
Leetcode 32 Longest Valid Parentheses (最長有效括號)
給定一個只包含 '(' 和 ')' 的字符串,找出最長的包含有效括號的子串的長度。
示例 1:
輸入: "(()"
輸出: 2
解釋: 最長有效括號子串為 "()"
示例 2:
輸入: ")()())"
輸出: 4
解釋: 最長有效括號子串為 "()()"
這道題可以用動態(tài)規(guī)劃來做,也能用簡潔明了的棧來解決。
什么是棧?
棧是一種先進后出(LIFO)的有序集合,新添加的元素在棧頂,舊元素在棧底。
以下圖為例,1、2、3、4、5、6、7先后進棧:
創(chuàng)建棧
創(chuàng)建一個類來表示棧:
class Stack { // 初始化類,創(chuàng)建數組 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存放最大長度;
棧只存放左括號的下標,遇到左括號,將其下標存入棧中;
遇到右括號,若此時棧為空,跳過本次循環(huán)并更新start;若棧不為空,則棧頂元素出棧;
棧頂元素出棧后,若棧為空,則計算當前下標和start的距離,并更新maxLen;
棧頂元素出棧后,若棧不為空,則計算當前下標和棧頂存放的下標的距離,并更新maxLen;
循環(huán)遍歷直至結束。
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 { // 如果是右括號 /* 棧內為空,說明本次有效括號匹配已結束,跳過本次循環(huán)并更新 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
看完上述內容是否對您有幫助呢?如果還想對相關知識有進一步的了解或閱讀更多相關文章,請關注創(chuàng)新互聯行業(yè)資訊頻道,感謝您對創(chuàng)新互聯的支持。
當前名稱:怎么在JavaScript中使用棧
文章來源:http://muchs.cn/article36/ghcjpg.html
成都網站建設公司_創(chuàng)新互聯,為您提供定制網站、網站排名、建站公司、網站內鏈、虛擬主機、微信公眾號
聲明:本網站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯