數(shù)據(jù)結(jié)構(gòu)與算法的JavaScript實(shí)現(xiàn)及應(yīng)用:Stack/遞歸/漢諾
摘要
在這篇文章里，我將介紹數(shù)據(jù)結(jié)構(gòu)Stack的基本操作和它的一些應(yīng)用。
我們將看到Stack在括號(hào)匹配檢測，表達(dá)式求值，函數(shù)調(diào)用上的應(yīng)用。
遞歸是一種特殊的函數(shù)調(diào)用，由于遞歸在程序設(shè)計(jì)中十分重要且不容易理解，所以我將闡述我對(duì)遞歸的理解。
***我們將看到利用Stack和遞歸是怎么優(yōu)雅的解決一個(gè)經(jīng)典游戲：漢諾塔。
本文還將給出表達(dá)式求值和漢諾塔的HTML5演示。
Stack
簡介
Stack即棧，以下是維基百科的定義：
在計(jì)算機(jī)科學(xué)中，是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈結(jié)串行或陣列的一端（稱為堆棧頂端指標(biāo)，英語：top）進(jìn)行加入資料（英語：push）和輸出資料（英語：pop）的運(yùn)算。另外堆棧也可以用一維陣列或連結(jié)串行的形式來完成。
根據(jù)定義我們知道棧只有三種操作：入棧(push)，出棧(pop)，獲取棧頂元素(top)。而且棧只能夠操縱棧頂元素，即只能在一端進(jìn)行操作。
由于棧具有后進(jìn)入的元素率先彈出的性質(zhì)，棧又被稱為后進(jìn)先出(LIFO, Last In First Out)的結(jié)構(gòu)。
棧的操作十分簡單，我們可以用單鏈表(LinkedList)和數(shù)組來實(shí)現(xiàn)棧。
然而在JavaScript中，Array自帶pop(), push()的操作，而且我們可以利用Array[Array.length-1]來實(shí)現(xiàn)top()操作。所以沒有必要去另外實(shí)現(xiàn)一個(gè)Stack類型，用Array表達(dá)即可。
應(yīng)用
Stack的LIFO的特性使得其適于解決許多實(shí)際問題，以下我們選取它的三個(gè)應(yīng)用來加以闡述。
括號(hào)匹配檢測
我們平時(shí)在編輯器中寫代碼時(shí)，有些編輯器會(huì)自動(dòng)檢測括號(hào)是否前后匹配，不匹配的話則會(huì)報(bào)錯(cuò)提示。
利用Stack的LIFO的特性，我們可以輕松實(shí)現(xiàn)這個(gè)功能。
算法的偽代碼如下：
- //新建一個(gè)Stack s
- s = new stack()
- //讀取字符直至讀完
- while read to c != EOF:
- //如果字符是開放括號(hào) 如 '(' '[' '{'等， 入棧
- if c is opening:
- s.push( c )
- //如果字符是結(jié)束括號(hào) 如 ')' ']' '}'
- else if c is closing:
- //若棧為空或者棧頂元素與開放括號(hào)不匹配 則報(bào)錯(cuò)
- if s is empty or f s.pop() is not correspond to c:
- return error!
- //若***棧不為空，報(bào)錯(cuò)
- if s is not empty:
- return error!
- //如果沒有返回報(bào)錯(cuò)，則返回正常
- return ok
算法的原理為，遇到一個(gè)結(jié)束的括號(hào)時(shí)，我們總是要查找***一個(gè)開放的括號(hào)是否與之匹配，若找不到開放的括號(hào)，或***一個(gè)開放的括號(hào)不匹配，則報(bào)錯(cuò)。
由于總是而且僅需要尋找***一個(gè)元素，所以我們將開放的括號(hào)入棧，匹配時(shí)則出棧。
由于Stack的特性，這個(gè)算法簡單明了，且消耗的時(shí)間復(fù)雜度為線性級(jí)O(n)。
表達(dá)式求值
Stack的強(qiáng)大特性，也使得其能夠運(yùn)用在表達(dá)式求值上。
設(shè)想一個(gè)表達(dá)式：2+4/(3-1)
這個(gè)表達(dá)式具備了三種類型的符號(hào)：
- 運(yùn)算數(shù)：2 4 2 2
- 運(yùn)算符：+ / -
- 圓括號(hào)：()
計(jì)算它的算法如下：
- //分配兩個(gè)棧，ops為運(yùn)算符棧，nums為數(shù)字棧
- ops = new Stack, nums = new Stack
- //從表達(dá)式中讀取字符 直至結(jié)束
- while read c in expression != EOF:
- //若為左括號(hào)，入運(yùn)算符棧
- if c is '(':
- ops.push(c)
- //若為數(shù)字，入數(shù)字棧
- else if c is a number:
- nums.push(c)
- //若為操作符
- else if c is an operator:
- //若運(yùn)算符棧的棧頂元素比c的優(yōu)先級(jí)高或一樣高，則進(jìn)行單次運(yùn)算
- while ops.top() is equal or precedence over c:
- op = ops.pop()
- opn2 = nums.pop()
- opn1 = nums.pop()
- //進(jìn)行單次運(yùn)算，并把運(yùn)算數(shù)入數(shù)字棧
- nums.push( cal(op,opn1,opn2) )
- //若為右括號(hào)
- else if c is ')':
- //除非棧頂元素為左括號(hào)，否則運(yùn)算符棧出棧并將計(jì)算結(jié)果入數(shù)字棧
- op = ops.pop()
- while op != '(':
- opn2 = nums.pop()
- opn1 = nums.pop()
- nums.push( cal(op,opn1,opn2) )
- op = ops.pop()
- //返回?cái)?shù)字棧的棧頂元素
- return nums.top()
以下是表達(dá)式求值的DEMO：
函數(shù)調(diào)用
我們?cè)谡{(diào)試代碼的時(shí)候，碰到函數(shù)報(bào)錯(cuò)時(shí)經(jīng)常會(huì)發(fā)現(xiàn)如下類似的報(bào)錯(cuò)提示：
- /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
其實(shí)我們只是在一處出錯(cuò)了，為什么會(huì)打印出這么多報(bào)錯(cuò)信息呢？
原因就在于解釋器把報(bào)錯(cuò)的函數(shù)經(jīng)過的所有調(diào)用函數(shù)的棧打印了出來。
在函數(shù)調(diào)用的時(shí)候，我們需要切換到被調(diào)用的函數(shù)上，但是一旦函數(shù)調(diào)用結(jié)束，我們還得回到原來的位置。
利用棧，我們可以有條不紊的實(shí)現(xiàn)這點(diǎn)，即在函數(shù)調(diào)用的時(shí)候，我們把當(dāng)前函數(shù)的變量和上下文入棧，等函數(shù)調(diào)用結(jié)束，我們?cè)俪鰲?，獲取之前的上下文和變量。
#p#
遞歸
函數(shù)調(diào)用的一個(gè)特殊情況是自己調(diào)用自己，這種情況稱之為遞歸。
最簡單的示例，求解階乘：
- function factorial(n) {
- return n == 0 ? 1 : n * factorial(n-1);
- }
遞歸是個(gè)很有用的利器，但是新手往往很難理解，以下來談一談我對(duì)遞歸的理解。
- 遞歸需要一個(gè)終止條件，否則會(huì)無限遞歸
- 每次遞歸需要將問題縮小，否則達(dá)不到終止條件，也會(huì)無限遞歸
很顯然，遞歸是自己調(diào)用自己，這很像我們?cè)诶戆l(fā)店里面照鏡子一樣，如果沒有終止條件，我們永遠(yuǎn)也不知道還有多少個(gè)自己。
其實(shí)用遞歸來求解問題的本質(zhì)是找到比原問題更小的問題，而且能用同樣的方法來處理。另外我們需要確定遞歸在什么時(shí)候結(jié)束，也就是確定遞歸的終止條件。
比如求階乘：
- 我們?cè)趺辞?的階乘? 3的階乘等于3乘與2的階乘
- 我們?cè)趺辞?的階乘? 2的階乘等于2乘與1的階乘
- 我們?cè)趺辞?的階乘? 1的階乘等于1乘與0的階乘
- 我們?cè)趺辞?的階乘? 我們不需要求0的階乘，因?yàn)槲覀円阎?的階乘為1
通過這么分析問題，提出n的階乘怎么求？
回答是：如果n為0，則返回1，否則返回n乘與n-1的階乘。
于是我們便得到了階乘的遞歸表達(dá)：
- function factorial(n) {
- return n == 0 ? 1 : n * factorial(n-1);
- }
階乘的遞歸的終止條件是n==0；縮小問題的方法則是發(fā)現(xiàn)了n-1的問題和n的問題是一致的。
顯然，遞歸的基礎(chǔ)是函數(shù)調(diào)用，而函數(shù)調(diào)用的基礎(chǔ)是Stack。所以每次遞歸的開銷，則是需要不停的進(jìn)行Stack的push和pop操作，這樣會(huì)耗費(fèi)大量的空間，也可能會(huì)造成冗余運(yùn)算。
解決的辦法可能有：尾遞歸，動(dòng)態(tài)規(guī)劃。
漢諾塔
漢諾塔是一個(gè)經(jīng)典的游戲。
其維基百科的描述為：
有三根桿子A，B，C。A桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿：
- 每次只能移動(dòng)一個(gè)圓盤；
- 大盤不能疊在小盤上面。
漢諾塔有很多解法，我認(rèn)為***雅的解法是遞歸法，如果你不了解漢諾塔的解法的話，在繼續(xù)閱讀前，請(qǐng)嘗試用遞歸法來解決它。
好吧，我承認(rèn)一開始我沒想出來如何用遞歸法來解決它，但是看完了它的解法后，我覺得優(yōu)雅而精妙。
漢諾塔的遞歸法偽代碼如下：
- //將n個(gè)盤子按規(guī)則從a柱子，移動(dòng)到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);
- }
- }
整個(gè)算法的思路是：
- 將a柱子上的n-1個(gè)盤子暫時(shí)移到b柱子上
- a柱子只剩下***的盤子，把它移到目標(biāo)柱子c上
- ***再將b柱子上的n-1個(gè)盤子移到目標(biāo)柱子c上
問題的縮小策略是我們?cè)趺窗裯個(gè)盤子從a移到c，同樣適用于n-1個(gè)盤子從a移到c。
當(dāng)n一直縮小到3時(shí)，我們先把最上面的兩個(gè)盤子移動(dòng)到b，然后把***的盤子移動(dòng)到c，然后再把b上的兩個(gè)盤子移動(dòng)到c。
當(dāng)n一直縮小到2時(shí)，問題終于變得直觀了，我們將最上面的盤子移到b，然后把最下面的盤子移到c，***再把b的盤子移到c。
當(dāng)n縮小到1時(shí)，我們直接將a最上面的盤子移到c就OK了。
這就是問題的終止條件。
該算法的時(shí)間復(fù)雜度為指數(shù)級(jí)O(2^n)，推導(dǎo)詳見Complexity for towers of Hanoi?。最少求解步驟為2^n-1。
漢諾塔的傳說：
傳說印度某間寺院有三根柱子，上串64個(gè)金盤。寺院里的僧侶依照一個(gè)古老的預(yù)言，以上述規(guī)則移動(dòng)這些盤子；預(yù)言說當(dāng)這些盤子移動(dòng)完畢，世界就會(huì)滅亡。這個(gè)傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。
若傳說屬實(shí)，僧侶們需要2^64 − 1步才能完成這個(gè)任務(wù)；若他們每秒可完成一個(gè)盤子的移動(dòng)，就需要5846億年才能完成。整個(gè)宇宙現(xiàn)在也不過137億年 -.-！
以下是漢諾塔的演示demo：
