棧引發的問題思考

• 2019 年 10 月 31 日
• 筆記

ECMAScript數組也提供了一種讓數組的行為類似於其他數據結構的方法。具體說來，數組可以表現得就像棧一樣，後者是一種可以限制插入和刪除項的數據結構。

棧是一種LIFO（Last-In-First-Out，後進先出）的數據結構，也就是最新添加的項最早被移除。而棧中項的插入（叫做推入）和移除（叫做彈出），只發生在一個位置——棧的頂部。ECMAScript為數組專門提供了 push() 和 pop() 方法，以便實現類似棧的行為。

push() 方法可以接收任意數量的參數，把它們逐個添加到數組末尾，並返回修改後數組的長度。而 pop() 方法則從數組末尾移除最後一項，減少數組的 length 值，然後返回移除的項。

棧的應用

01

可以利用棧將一個數字從一種數制轉換成另一種數制。假設想將數字 n 轉換為以 b 為基數的數字，實現轉換的演算法如下。

(1) 最高位為 n % b，將此位推入棧。

(2) 使用 n/b 代替 n。

(3) 重複步驟 1 和 2，直到 n 等於 0，且沒有餘數。

(4) 持續將棧內元素彈出，直到棧為空，依次將這些元素排列，就得到轉換後數字的字元串形式。

使用棧，在 JavaScript 中實現該演算法就是小菜一碟。下面就是該函數的定義，可以將數字轉化為二至九進位的數字：

function mulBase(num, base) {      let list = []      do {        list.push(num % base)        num = Math.floor(num /= base)      } while (num > 0)      let converted = ''      while (list.length > 0) {        converted += list.pop()      }      return converted    }    let num = 100    console.log(mulBase(num, 2)) // 1100100    console.log(num.toString(2)) // 1100100

02

迴文是指這樣一種現象：一個單詞、短語或數字，從前往後寫和從後往前寫都是一樣的。比如，單詞「dad」、「racecar」就是迴文；如果忽略空格和標點符號，下面這個句子也是迴文，「A man, a plan, a canal: Panama」；數字 1001 也是迴文。

使用棧，可以輕鬆判斷一個字元串是否是迴文。我們將拿到的字元串的每個字元按從左至右的順序推入棧。當字元串中的字元都入棧後，棧內就保存了一個反轉後的字元串，最後的字元在棧頂，第一個字元在棧底。

字元串完整壓入棧內後，通過持續彈出棧中的每個字母就可以得到一個新字元串，該字元串剛好與原來的字元串順序相反。我們只需要比較這兩個字元串即可，如果它們相等，就是一個迴文。

function isPalindrome(word) {      let list = []      for(let i = 0; i < word.length; i++) {        list.push(word[i])      }      let rword = ''      while (list.length > 0) {        rword += list.pop()      }      return word === rword    }

03

為了演示如何用棧實現遞歸，考慮一下求階乘函數的遞歸定義。首先看看 5 的階乘是怎麼定義的。

使用棧來模擬計算 5! 的過程，首先將數字從 5 到 1 推入棧，然後使用一個循環，將數字挨個彈出連乘，就得到了正確的答案：120。

function fact(n) {      let list = []      while (n > 1) {        list.push(n--);      }      let product = 1      while (list.length > 0) {        product *= list.pop()      }      return product    }    console.log(fact(5)) // 150

數據結構是電腦存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。

——《基本概念》

提問

棧可以用來判斷一個算術表達式中的括弧是否匹配。編寫一個函數，該函數接受一個算術表達式作為參數，返回括弧缺失的位置。下面是一個括弧不匹配的算術表達式的例子：

2.3 + 23 / 12 + (3.14159×0.24