3.3 用棧解決問題

棧的實際應用非常廣泛。在回溯問題中，它可以存儲訪問過的任務或路徑、撤銷的操作（後面的章節討論圖和回溯問題時，我們會學習如何應用這個例子）。Java和C#用棧來存儲變量和方法調用，特別是處理遞歸算法時，有可能拋出一個棧溢出異常（後面的章節也會介紹）。

既然我們已經瞭解了Stack類的用法，不妨用它來解決一些計算機科學問題。本節，我們將學習使用棧的三個最著名的算法示例。首先是十進制轉二進制問題，以及任意進制轉換的算法；然後是平衡圓括號問題；最後，我們會學習如何用棧解決漢諾塔問題。

從十進制到二進制

現實生活中，我們主要使用十進制。但在計算科學中，二進制非常重要，因為計算機裡的所有內容都是用二進制數字表示的（0和1）。沒有十進制和二進制相互轉化的能力，與計算機交流就很困難。

要把十進制轉化成二進制，我們可以將該十進制數字和2整除（二進制是滿二進一），直到結果是0為止。舉個例子，把十進制的數字10轉化成二進制的數字，過程大概是這樣：

大學的計算機課一般都會先教這個進制轉換。下面是對應的算法描述：

function pideBy2(decNumber){

  var remStack = new Stack,
    rem,
    binaryString = '';

  while (decNumber > 0){ //{1}
    rem = Math.floor(decNumber % 2); //{2}
    remStack.push(rem); //{3}
    decNumber = Math.floor(decNumber / 2); //{4}
  }

  while (!remStack.isEmpty){ //{5}
    binaryString += remStack.pop.toString;
  }

  return binaryString;
}

  

在這段代碼裡，當結果滿足和2做整除的條件時（行{1}），我們會獲得當前結果和2的餘數，放到棧裡（行{2}、{3}）。然後讓結果和2做整除（行{4}）。另外請注意：JavaScript有數字類型，但是它不會區分究竟是整數還是浮點數。因此，要使用Math.floor函數讓除法的操作僅返回整數部分。最後，用pop方法把棧中的元素都移除，把出棧的元素變成連接成字符串（行{5}）。

用剛才寫的算法做一些測試，使用以下代碼把結果輸出到控制台裡：

console.log(pideBy2(233));
console.log(pideBy2(10));
console.log(pideBy2(1000));

  

進制轉換算法

我們很容易修改之前的算法，使之能把十進制轉換成任何進制。除了讓十進制數字和2整除轉成二進制數，還可以傳入其他任意進制的基數為參數，就像下面算法這樣：

function baseConverter(decNumber, base){

  var remStack = new Stack,
    rem,
    baseString = '',
    digits = '0123456789ABCDEF'; //{6}

  while (decNumber > 0){
    rem = Math.floor(decNumber % base);
    remStack.push(rem);
    decNumber = Math.floor(decNumber / base);
  }

  while (!remStack.isEmpty){
    baseString += digits[remStack.pop]; //{7}
  }

  return baseString;
}

  

我們只需要改變一個地方。在將十進制轉成二進制時，餘數是0或1；在將十進制轉成八進制時，餘數是0到7之間的數；但是將十進制轉成16進制時，餘數是0到9之間的數字加上A、B、C、D、E和F（對應10、11、12、13、14和15）。因此，我們需要對棧中的數字做個轉化才可以（行{6}和行{7}）。

可以使用之前的算法，輸出結果如下：

console.log(baseConverter(100345, 2));
console.log(baseConverter(100345, 8));
console.log(baseConverter(100345, 16));

  

　請在網上下載本書的代碼，裡面還有一些棧的應用實例，如平衡圓括號和漢諾塔。