在這篇文章裡，我將介紹數據結構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的特性，我們可以輕鬆實現這個功能。
算法的偽代碼如下：
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)
這個表達式具備了三種類型的符號：
運算數：2 4 2 2 運算符：+ / - 圓括號：()計算它的算法如下：
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: 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
其實我們只是在一處出錯了，為什麼會列印出這麼多報錯信息呢？
原因就在於解釋器把報錯的函數經過的所有調用函數的棧列印了出來。
在函數調用的時候，我們需要切換到被調用的函數上，但是一旦函數調用結束，我們還得回到原來的位置。
利用棧，我們可以有條不紊的實現這點，即在函數調用的時候，我們把當前函數的變量和上下文入棧，等函數調用結束，我們再出棧，獲取之前的上下文和變量。
遞歸函數調用的一個特殊情況是自己調用自己，這種情況稱之為遞歸。
最簡單的示例，求解階乘：
function factorial(n) { return n == 0 ? 1 : n * factorial(n-1); }
遞歸是個很有用的利器，但是新手往往很難理解，以下來談一談我對遞歸的理解。
遞歸需要一個終止條件，否則會無限遞歸 每次遞歸需要將問題縮小，否則達不到終止條件，也會無限遞歸很顯然，遞歸是自己調用自己，這很像我們在理髮店裡面照鏡子一樣，如果沒有終止條件，我們永遠也不知道還有多少個自己。
其實用遞歸來求解問題的本質是找到比原問題更小的問題，而且能用同樣的方法來處理。另外我們需要確定遞歸在什麼時候結束，也就是確定遞歸的終止條件。
比如求階乘：
我們怎麼求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杆：
每次只能移動一個圓盤； 大盤不能疊在小盤上面。漢諾塔有很多解法，我認為最優雅的解法是遞歸法，如果你不了解漢諾塔的解法的話，在繼續閱讀前，請嘗試用遞歸法來解決它。
好吧，我承認一開始我沒想出來如何用遞歸法來解決它，但是看完了它的解法後，我覺得優雅而精妙。
漢諾塔的遞歸法偽代碼如下：
hanoi( n, a, b, c ) { if( n > 0 ) { hanoi(n-1,a,c,b); c.push( a.pop() ); hanoi(n-1,b,a,c); } }
整個算法的思路是：
將a柱子上的n-1個盤子暫時移到b柱子上 a柱子只剩下最大的盤子，把它移到目標柱子c上 最後再將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/
【編輯推薦】
【責任編輯：
林師授TEL：（010）68476606】