摘要

在這篇文章里，我將介紹數據結構Stack的基本操作和它的一些應用。

我們將看到Stack在括號匹配檢測，表達式求值，函數調用上的應用。

遞歸是一種特殊的函數調用，由于遞歸在程序設計中十分重要且不容易理解，所以我將闡述我對遞歸的理解。

***我們將看到利用Stack和遞歸是怎么優雅的解決一個經典游戲：漢諾塔。

本文還將給出表達式求值和漢諾塔的HTML5演示。

Stack

簡介

Stack即棧，以下是維基百科的定義：

在計算機科學中，是一種特殊的串行形式的數據結構，它的特殊之處在于只能允許在鏈結串行或陣列的一端（稱為堆棧頂端指標，英語：top）進行加入資料（英語：push）和輸出資料（英語：pop）的運算。另外堆棧也可以用一維陣列或連結串行的形式來完成。

根據定義我們知道棧只有三種操作：入棧(push)，出棧(pop)，獲取棧頂元素(top)。而且棧只能夠操縱棧頂元素，即只能在一端進行操作。

由于棧具有后進入的元素率先彈出的性質，棧又被稱為后進先出(LIFO, Last In First Out)的結構。

棧的操作十分簡單，我們可以用單鏈表(LinkedList)和數組來實現棧。

然而在JavaScript中，Array自帶pop(), push()的操作，而且我們可以利用Array[Array.length-1]來實現top()操作。所以沒有必要去另外實現一個Stack類型，用Array表達即可。

應用

Stack的LIFO的特性使得其適于解決許多實際問題，以下我們選取它的三個應用來加以闡述。

括號匹配檢測

我們平時在編輯器中寫代碼時，有些編輯器會自動檢測括號是否前后匹配，不匹配的話則會報錯提示。

利用Stack的LIFO的特性，我們可以輕松實現這個功能。

算法的偽代碼如下：

//新建一個Stack s  
s = new stack()  
//讀取字符直至讀完  
while read to c != EOF:  
    //如果字符是開放括號 如 '(' '[' '{'等， 入棧  
    if c is opening:  
        s.push( c )  
    //如果字符是結束括號 如 ')' ']' '}'  
    else if c is closing:  
        //若棧為空或者棧頂元素與開放括號不匹配 則報錯  
        if s is empty or f s.pop() is not correspond to c:  
            return error!     
//若***棧不為空，報錯  
if s is not empty:  
    return error!     
//如果沒有返回報錯，則返回正常  
return ok 

算法的原理為，遇到一個結束的括號時，我們總是要查找***一個開放的括號是否與之匹配，若找不到開放的括號，或***一個開放的括號不匹配，則報錯。

由于總是而且僅需要尋找***一個元素，所以我們將開放的括號入棧，匹配時則出棧。

由于Stack的特性，這個算法簡單明了，且消耗的時間復雜度為線性級O(n)。

表達式求值

Stack的強大特性，也使得其能夠運用在表達式求值上。

設想一個表達式：2+4/(3-1)

這個表達式具備了三種類型的符號：

1. 運算數：2 4 2 2
2. 運算符：+ / -
3. 圓括號：()

計算它的算法如下：

//分配兩個棧，ops為運算符棧，nums為數字棧  
ops = new Stack, nums = new Stack  
//從表達式中讀取字符 直至結束  
while read c in expression != EOF:  
    //若為左括號，入運算符棧  
    if c is '(':  
        ops.push(c)  
    //若為數字，入數字棧  
    else if c is a number:  
        nums.push(c)  
    //若為操作符  
    else if c is an operator:  
        //若運算符棧的棧頂元素比c的優先級高或一樣高，則進行單次運算  
        while ops.top() is equal or precedence over c:  
            op = ops.pop()  
            opn2 = nums.pop()  
            opn1 = nums.pop()  
            //進行單次運算，并把運算數入數字棧  
            nums.push( cal(op,opn1,opn2) )  
    //若為右括號  
    else if c is ')':  
        //除非棧頂元素為左括號，否則運算符棧出棧并將計算結果入數字棧  
        op = ops.pop()  
        while op != '(':  
            opn2 = nums.pop()  
            opn1 = nums.pop()  
            nums.push( cal(op,opn1,opn2) )  
            op = ops.pop()  
//返回數字棧的棧頂元素  
return nums.top() 

以下是表達式求值的DEMO：

函數調用

我們在調試代碼的時候，碰到函數報錯時經常會發現如下類似的報錯提示：

/Users/tim/Codes/JavaScript/dsaginjs/DSinJS/Stack/InfixExpression.js:59 
    return prioty[a] ) prioty[b];  
                     ^  
SyntaxError: Unexpected token )  
    at Module._compile (module.js:439:25)  
    at Object.Module._extensions..js (module.js:474:10)  
    at Module.load (module.js:356:32)  
    at Function.Module._load (module.js:312:12)  
    at Function.Module.runMain (module.js:497:10)  
    at startup (node.js:119:16)  
    at node.js:902:3 

其實我們只是在一處出錯了，為什么會打印出這么多報錯信息呢？

原因就在于解釋器把報錯的函數經過的所有調用函數的棧打印了出來。

在函數調用的時候，我們需要切換到被調用的函數上，但是一旦函數調用結束，我們還得回到原來的位置。

利用棧，我們可以有條不紊的實現這點，即在函數調用的時候，我們把當前函數的變量和上下文入棧，等函數調用結束，我們再出棧，獲取之前的上下文和變量。

#p#

遞歸

函數調用的一個特殊情況是自己調用自己，這種情況稱之為遞歸。

最簡單的示例，求解階乘：

function factorial(n) {  
    return n == 0 ? 1 : n * factorial(n-1);  
} 

遞歸是個很有用的利器，但是新手往往很難理解，以下來談一談我對遞歸的理解。

1. 遞歸需要一個終止條件，否則會無限遞歸
2. 每次遞歸需要將問題縮小，否則達不到終止條件，也會無限遞歸

很顯然，遞歸是自己調用自己，這很像我們在理發店里面照鏡子一樣，如果沒有終止條件，我們永遠也不知道還有多少個自己。

[[111099]]

其實用遞歸來求解問題的本質是找到比原問題更小的問題，而且能用同樣的方法來處理。另外我們需要確定遞歸在什么時候結束，也就是確定遞歸的終止條件。

比如求階乘：

• 我們怎么求3的階乘? 3的階乘等于3乘與2的階乘
• 我們怎么求2的階乘? 2的階乘等于2乘與1的階乘
• 我們怎么求1的階乘? 1的階乘等于1乘與0的階乘
• 我們怎么求0的階乘? 我們不需要求0的階乘，因為我們已知0的階乘為1

通過這么分析問題，提出n的階乘怎么求？

回答是：如果n為0，則返回1，否則返回n乘與n-1的階乘。

于是我們便得到了階乘的遞歸表達：

function factorial(n) {  
    return n == 0 ? 1 : n * factorial(n-1);  
} 

階乘的遞歸的終止條件是n==0；縮小問題的方法則是發現了n-1的問題和n的問題是一致的。

顯然，遞歸的基礎是函數調用，而函數調用的基礎是Stack。所以每次遞歸的開銷，則是需要不停的進行Stack的push和pop操作，這樣會耗費大量的空間，也可能會造成冗余運算。

解決的辦法可能有：尾遞歸，動態規劃。

漢諾塔

漢諾塔是一個經典的游戲。

其維基百科的描述為：

有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：

1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。

[[111100]]

漢諾塔有很多解法，我認為***雅的解法是遞歸法，如果你不了解漢諾塔的解法的話，在繼續閱讀前，請嘗試用遞歸法來解決它。

好吧，我承認一開始我沒想出來如何用遞歸法來解決它，但是看完了它的解法后，我覺得優雅而精妙。

漢諾塔的遞歸法偽代碼如下：

//將n個盤子按規則從a柱子，移動到c柱子  
hanoi( n, a, b, c )  
{  
    if( n > 0 )  
    {  
        hanoi(n-1,a,c,b);  
        //將a柱子的最上面的盤子移到c柱子  
        c.push( a.pop() );  
        hanoi(n-1,b,a,c);  
    }  
} 

整個算法的思路是：

1. 將a柱子上的n-1個盤子暫時移到b柱子上
2. a柱子只剩下***的盤子，把它移到目標柱子c上
3. ***再將b柱子上的n-1個盤子移到目標柱子c上

問題的縮小策略是我們怎么把n個盤子從a移到c，同樣適用于n-1個盤子從a移到c。

當n一直縮小到3時，我們先把最上面的兩個盤子移動到b，然后把***的盤子移動到c，然后再把b上的兩個盤子移動到c。 
當n一直縮小到2時，問題終于變得直觀了，我們將最上面的盤子移到b，然后把最下面的盤子移到c，***再把b的盤子移到c。 
當n縮小到1時，我們直接將a最上面的盤子移到c就OK了。

這就是問題的終止條件。

該算法的時間復雜度為指數級O(2^n)，推導詳見Complexity for towers of Hanoi?。最少求解步驟為2^n-1。

漢諾塔的傳說：

傳說印度某間寺院有三根柱子，上串64個金盤。寺院里的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。

若傳說屬實，僧侶們需要2^64 − 1步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要5846億年才能完成。整個宇宙現在也不過137億年 -.-！

以下是漢諾塔的演示demo：

原文鏈接：http://wuzhiwei.net/ds_app_stack/