摘要:棧就是和列表類似的一種數據結構它可以用來解決計算機世界里的很多問題棧是一種高效的數據結構因為數據只能在棧頂添加或刪除所以這樣的操作很快而且容易實現棧的使用遍布程序語言的方方面面從表達式求值到處理函數調用棧的操作棧只能通過列表的一端訪問這一端
棧就是和列表類似的一種數據結構, 它可以用來解決計算機世界里的很多問題. 棧是一種高效的數據結構, 因為數據只能在棧頂添加或刪除, 所以這樣的操作很快, 而且容易實現. 棧的使用遍布程序語言的方方面面, 從表達式求值到處理函數調用.棧的操作
棧只能通過列表的一端訪問, 這一端稱為棧頂.
棧被稱為 先進后出 的數據結構與 隊列 相反.
由于棧具有先進后出的特點, 所以任何不在棧頂的元素都無法訪問. 為了得到棧底的元素, 必須拿掉上面的元素.
對棧的三種主要操作:
將一個元素壓入棧 使用push().
將一個元素彈出棧 使用pop().
預覽棧頂的元素 peek().
這里需要注意的是的第三種. pop()方法雖然可訪問棧頂的元素, 但是調用該方法后, 棧頂元素也就從棧中被永久刪除. peek()只返回棧頂元素, 而不刪除.
這三種為主要方法, 但是棧還有其他方法和屬性. clear()清除棧內所有元素, length屬性記錄棧內元素的個數. 我們還可以定義一個empty屬性, 用以表示棧內是否含有元素, 不過使用length屬性也可以達到相同目的.
棧的實現實現一個棧, 首要條件是決定存儲數據的底層數據結構. 這里采用數組.
從定義Stack類的構造函數開始:
class Stack { constructor() { this._dataStore = []; this._top = 0; } push(element) { this._dataStore[this._top++] = element; } pop(element) { return this._dataStore[--this._top]; } peek() { return this._dataStore[this._top - 1]; } length() { return this._top; } clear() { this._top = 0; } }
用數組_dataStore保存棧內元素, 構造函數將其初始化為一個空數組. 變量_top記錄棧頂位置, 被構造函數初始化為0, 表示棧頂對應數組的其實位置0. 如果有元素被壓入棧, 該變量將隨之變化.
push()方法. 向棧中壓入一個新元素時, 需要將其保存在數組中變量_top所對應的位置, 然后將_top加1, 讓其指向數組中下一個空位置. 這里要注意++操作符的位置, 它放在變量后面, 新元素就會放在_top當前值對應位置, 然后再加1, 指向下一個位置.
pop()方法. 恰好與push()方法相反. 有返回值, 返回棧頂元素. 這里要注意--操作符的位置, 它放在變量前面, 先對_top減1然后再刪除對應位置元素.
peek()方法. 返回數組的第_top - 1個位置的元素, 即棧頂元素. 如果對空棧調用peek(), 結果為undefined.
length()方法. 通過返回變量_top值的方式返回棧內的元素個數.
clear()方法. 將變量_top設為0, 輕松清空一個棧.
實例 數制間的相互轉換可以利用棧將一個數字從一種數制轉化成另一種數制. 假設將數字n轉化為以b為基數的數字, 實現轉化的算法如下.
最高位為n % b, 將此位壓入棧.
使用n / b代替n.
重復步驟1和2, 直到n等于0, 且沒有余數.
持續將棧內元素彈出, 直到棧為空, 依次將這些元素排列, 就得到轉換后數字的字符串形式.
注意: 此算法只針對基數為2~9的情況.
function mulBase(num, base) { var s = new Stack(); do { s.push(num % base); num = Math.floor(num /= base); } while (num > 0); var converted = ""; while(s.length() > 0) { converted += s.pop(); }; return converted; }; console.log(mulBase(32, 2)); // 得到32的二進制值: 100000 console.log(mulBase(88, 8)); // 得到88的八進制值: 130回文
回文: 一個單詞、短語和數字, 從前往后寫和從后往前寫都是一樣的. eg: 單詞"dad"、"racecar"就是回文; 忽略空格和標點下面這個句子也是回文: "A man, a plan, a canal: Panama"; 數字101也是回文.
使用棧可以輕松判斷一個字符串是否是回文. 我們將拿到的字符串的每一個字符按從左至右的順序入棧. 當所有字符都入棧后, 棧內就保存了一個反轉后的字符串, 最后的字符在棧頂, 第一個字符在棧底.
字符串完整壓入棧內后, 通過持續彈出棧中的每一個字母就可以得到一個新的字符串, 該字符串剛好與原來的字符串順序相反. 我們只需要比較這兩個字符串即可.
function isPalindrome(word) { const s = new Stack(); for(let w of word) { s.push(w) }; let rword = ""; while(s.length() > 0) { rword += s.pop(); }; return word === rword; }; console.log(isPalindrome("hello")); // false console.log(isPalindrome("dad")); // true遞歸演示
棧常常被用來實現編程語言, 使用棧實現遞歸即為一例. 這里只是用棧來模擬遞歸過程.
為了演示如何用棧實現遞歸, 考慮一下求階乘函數的遞歸定義. 首先看5的階乘是怎么定義的: 5! = 5 * 4 * 3 * 2 * 1 = 120
下面是一個遞歸函數, 可以計算任何數字的階乘:
function factorial(n) { if(n === 0) return 1; return n * factorial(n - 1); }; // 尾掉優化 function factorial(n, total = 1) { if(n === 0) return total; return factorial(n - 1, n * total); }; console.log(factorial(5)); // 120
使用棧來模擬計算5!的過程, 首先將數字從5到1入棧, 然后使用一個循環, 將數字挨個彈出連乘, 就得到正確答案
下面使用棧模擬遞歸過程:
function fact(n) { const s = new Stack(); while(n > 1) { s.push(n--); }; let product = 1; while(s.length() > 0) { product *= s.pop(); }; return product; }; console.log(fact(5)); // 120判斷一個算數表達式中的括號是否匹配
例如判斷表達式為2.3 + 23 / 12 + (3.14159 * 0.24的算數表達式的括號是否匹配.
function fn(express) { const s = new Stack(); for (let i = 0; i < express.length; ++i) { if (express[i] === `(`) { s.push(i); } else if (express[i] === `)`) { s.pop(); } }; console.log(`在第${s.peek()}個字符是不匹配的括號`) }; fn("2.3 + 23 / 12 + (3.14159 * 0.24"); // 在第16個字符是不匹配的括號中綴表達式轉換后綴表達式
表達式詳解
一個算數表達式的后綴表達形式如下:
op1 op2 operator
使用兩個棧, 一個用來存儲操作數, 另一個用來存儲操作符, 設計并實現一個函數, 該函數可以將中綴表達式轉換為后綴表達式, 利用棧堆該表達式求值.
const express = "1+((2+3)*4)-5"; function fn(express) { const s1 = new Stack(); // 操作符棧 const s2 = new Stack(); // 操作數棧 const arr = express.split(""); arr.forEach((i, index) => { if(/^[0-9]*$/.test(i)) { s2.push(i) } else if(["+", "-", "*", "/"].includes(i)) { if(s1.length() === 0 || s1.peek() === "(") { s1.push(i) } else if (["*", "/"].includes(i) && ["+", "-"].includes(s1.peek())) { s1.push(i) } else { s2.push(s1.pop()); if(s1.length() === 0 || s1.peek() === "(") { s1.push(i); } } } else if (i === "(") { s1.push(i); } else if (i === ")") { while(s1.peek() !== "(") { s2.push(s1.pop()); } s1.pop(); } }); while(s1.length() > 0) { s2.push(s1.pop()); }; let str = "" while(s2.length() > 0) { str += ` ${s2.pop()}`; }; return str; }; console.log(fn(express))佩茲糖果盒
現實生活中的例子是佩茲糖果盒. 想象一下你有一盒佩茲糖果, 里面塞滿了紅色、黃色和白色的糖果, 但是你不喜歡黃色的糖果. 使用棧(有可能用到多個棧) 寫一段程序, 在不改變盒內其它糖果疊放順序的基礎上, 將黃色糖果移除.
const boxS = new Stack(); boxS.push("red"); boxS.push("yellow"); boxS.push("white"); boxS.push("white"); boxS.push("yellow"); boxS.push("yellow"); boxS.push("red"); boxS.push("red"); boxS.push("white"); boxS.push("yellow"); boxS.push("red"); function changeFn(sourceStack) { const s1 = new Stack(); const s2 = new Stack(); const resultS = new Stack(); while(sourceStack.length() > 0) { if(sourceStack.peek() === "yellow") { s1.push(sourceStack.pop()) } else { s2.push(sourceStack.pop()) } }; while(s2.length() > 0) { resultS.push(s2.pop()); }; return resultS; }; changeFn(boxS);
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/97848.html
摘要:對于棧來說,這個表尾稱為棧的棧頂,相應的表頭稱為棧底。棧和隊列的區別棧的插入和刪除操作都是在一端進行的,而隊列的操作卻是在兩端進行的。出棧操作出棧操作就是在棧頂取出數據,棧頂指針隨之下移的操作。 基本概念 棧和隊列都是動態的集合,在棧中,可以去掉的元素是最近插入的哪一個。棧實現了后進先出。在隊列中,可以去掉的元素總是在集合中存在的時間最長的那一個。隊列實現了先進先出的策略。 棧的官...
摘要:介紹棧是一種后進先出的線性表數據結構,分為棧頂和棧底兩端,僅允許在表的一端插入元素,這一端被稱為棧頂,另外一端稱之為棧底。 介紹 棧是一種后進先出的線性表數據結構,分為棧頂和棧底兩端,僅允許在表的一端插入元素,這一端被稱為棧頂,另外一端稱之為棧底。棧,只有兩種操作,分為入棧(壓棧)和出棧(退棧);向棧中添加元素的操作叫做入棧,相反從棧中刪除元素叫做出棧。 特點 只能從棧頂添加元素或者...
摘要:我們都知道數組是里面比較常用的一種數據結構,棧和數組類似,定義如下棧是一種遵從后進先出原則的有序集合。新增加和待刪除的元素都保存在棧的尾部,也稱棧頂,相反的另一端就叫棧底,在棧的這種數據結構里面,我們新增的元素都在棧頂,舊的元素都在棧底。 由于不是計算機專業出身,對數據結構這些了解的比較少,最近看了一些相關的書籍,這里做一些總結。本篇要說的是棧。我們都知道數組是JavaScript里面...
摘要:則會在轉移指令前執行。總結與之間的關系如果在中含有語句,那么語句的還有作用嗎先看一段代碼如果你對內存布局不是很清楚,請看這篇文章虛擬機類加載機制和字節碼執行引擎重點關注運行時棧幀結構局部變量表槽,操作數棧。 定論 問:finally語句一定會執行嗎?答: 如果沒有執行相應的try語句則不會執行。 在try語句中如果調用System.exit(0)方法則不會執行。 問:finally...
摘要:棧的應用前面介紹了那么多棧相關的知識,最后也是介紹棧的應用場景的時候了,棧的實際應用非常廣泛,例如用來存儲訪問過的任務或路徑撤銷的操作。 棧的定義 什么是棧?棧是一種遵循后進先出原則的有序集合,新添加的或者待刪除的元素都保存在棧的同一端,稱為棧頂,另一端稱為棧底,在棧里,新元素靠近棧頂,舊元素靠近棧底,用個圖來看大概這樣式的:showImg(https://segmentfault.c...
摘要:調用棧的運行機制機制程序運行到一個函數,它就會將其添加到調用棧中,當從這個函數返回的時候,就會將這個函數從調用棧中刪掉。在調用棧中每個調用偵都對應一個函數,最上方的調用幀稱為當前幀,調用棧是由所有的調用偵形成的。 showImg(https://segmentfault.com/img/remote/1460000019244497?w=900&h=600); 調用棧的英文名叫做Cal...
閱讀 2786·2021-11-22 14:45
閱讀 2925·2021-09-10 11:26
閱讀 3231·2021-09-07 10:18
閱讀 2219·2019-08-30 14:08
閱讀 617·2019-08-29 12:22
閱讀 1393·2019-08-26 13:48
閱讀 2535·2019-08-26 10:24
閱讀 1150·2019-08-23 18:35