Stack堆疊的資料結構

Posted By Mr. Thursday

不知道各位是否有接聽電話插撥 (call waiting) 的經驗? 我們會先把第一個接聽的人先暫時停著,然後接聽新打來的電話。不知道目前插撥最多能接聽多少通電話?假設依照這個方法一直接聽新的插撥電話,就會一直把上一通電話暫時儲存,等新接通的電話結束後,再回復上一通、上上一通、一直到第一通接聽的電話。

堆疊 (Stack) 就是類似的資料結構。「堆疊」有兩個方法 (method) 可以呼叫:推進 (push) 和 彈出 (pop)。透過這兩個方法的使用,我們可以達到讓資料「先進後出」的效果 (LIFO: Last In First Out)。甚麼是先進後出呢?讓我們再舉一個例子:搭電梯。當我們搭電梯的時候,通常最先進電梯的會擠在後面,後進電梯的比較靠近門口。如果都是同一層離開電梯,剛才比較慢近來電梯的人,反而是比較早離開電梯的人,這就是「先進後出」(LIFO) 的效果了。

再回到剛才接聽插撥電話的例子,正好就是先進後出的例子!最後插撥的先結束對話,最早打來的最慢結束對話。接下來讓我們看看,堆疊實際運作的情形,會向下面這一張動畫所顯示的:

 push

上面這張圖就是顯示堆疊 (stack) 把三個數字 1、2、3分別push到堆疊裡面的過程。堆疊本身看起來就像是我們把書本放在桌上的樣子一般,最早放的書本會在最底下,最後放的書本會在最上面。當我們把書本從最上面開始拿 (pop) 的時候,會拿到最後放的書本,最後才拿到一開始放下去的書本。因此把數字從堆疊 (stack) 裡面 pop出來的過程,會像下面這張動畫顯示的樣子:

pop

從上面這張圖,我們可以看出來,我們依照1、2、3的順序把數字 push 到堆疊裡面,pop的時候出來的順序就會變成 3、2、1,也就是先進後出了!

堆疊在遞迴式走訪樹的應用

介紹完了堆疊,最常應用到堆疊這個資料結構的演算法,應該就是「遞迴」 (recursive) 方法了。所謂遞迴,就像是站在兩面鏡子之間,相同的影像不停地反射,只是每反射一次都小一些。之前接聽插撥的例子也是遞迴的例子,就是先暫停目前的工作,但是不是忘記,而是先依照順序存起來,然後先處理新的工作。等到新的工作處理完,再按照先進後出的順序,把剛才暫停的工作回覆過來處理好

 post

因此,之前在〈由樹的前序、中序、後序走法來談資料結構〉裡面提到的前序、中序、後序的走法,也可以透過遞迴加上堆疊的資料結構來完成!譬如說上面這棵樹,我們從樹根7開始,發現有分支就往下走,但是我們先不把樹根忘掉,因此把樹根7 push到堆疊裡面。接者按照同樣的方法,往樹葉的方向走,一直走到樹葉的部分 ,再按照先進後出的順序,把堆疊pop出來的東西印出來,就是後序走訪這棵樹的方式了!

遞迴走訪樹的演算法如下 (移到文章後面以方便整理版面)

讓我們跑跑上面這一段演算法,演算法可以運作的東西,就是堆疊(stack)這個資料結構,以及輸入的這棵的資料結構。最後會輸出後序走訪這棵樹的過程。(請參考文章後面的過程,這邊先略過整理一下版面)

演算法和資料結構的用途 

因此到目前為止,我們終於知道了演算法和資料結構的初步的概念,也終於看到了一些基本的應用,像是「樹」、「堆疊」、「遞迴」等應用。然而或許還是會有些疑惑,就是演算法和資料結構,要怎樣子在電腦上面跑呢?如果說電腦聽不懂人類的自然語言,電腦又要怎樣子聽懂演算法的敘述呢?這邊我想先用一個比方來說明,也就是作文的比方。

當我們寫一篇作文的時候,我們可能會有一些寫作方法,譬如說第一段寫主旨,第二段寫例子,第三段寫反立推翻第一個例子,第四段寫結論,如此起承轉合,完成一篇文章。我們可能進一步把題目分成敘述文、論說文、和抒情文。不同種類的文章,我們會有不同的段落起承轉合。然而各類題目的段落安排方式,和我們用字淺詞的方式,可以分開來。甚至同樣的段落安排,我們可以用英文來寫。

因此演算法和電腦的關係,有些類似上面寫作比方的關係。電腦只看得懂機器0101碼,但是我們有高階程式語言,像是C, C++, 或是JAVA,透過編譯器 (compiler) 或是直譯器 (Interpreter),可以把我們寫的程式翻譯成機器看的懂的機器0101碼。程式語言,就如同寫作的時候,可能用中文寫,也可能用英文寫。但是演算法和資料結構,則是像寫作的時後段落安排的方法,論說文一種方法,敘述文一種方法,抒情文一種方法,是一種介於作文題目和文章句子之間的轉換過程

整理起來,寫作可以分成下面四個層次:

  1. 作文題目和題型 (敘述文、論說文、抒情文、其他題型)
  2. 段落安排 (針對題型的解決方法)
  3. 文章實際的句子 (可以是中文、也可以是英文)
  4. 每個單字的字母筆劃,或是中文字的筆劃 (包括標點符號的使用)

演算法資料結構對應這個層次的比方:

  1. 要電腦處理的問題和問題類型 (排序、搜尋、比對)
  2. 演算法和資料結構 (針對問題提出的解決方法)
  3. 實際寫出程式 (演算法可以和程式一一對應,但不限任一種程式語言)
  4. 程式透過編譯器(compiler)翻譯成機器0101碼

不知道看完這個例子,各位是否更了解資料結構的角色呢?電腦看不懂演算法或資料結構,但是演算法和資料結構,卻是問題解法和程式語言之間的橋樑

下面列出剛才提到的地迴走訪樹的演算法和執行過程。 (tree) 除了可以排序、搜尋、搭配遞迴和堆疊以外,還有本體論 (Ontology) 的應用。其他各種樹狀結構,像是壘堆 (heap)、追求效率而發明的紅黑樹 (Red-Black Tree) 和費布那西樹 (Fibonacci Tree)等等。日後有機會再一一向各位介紹吧!

遞迴走訪樹的演算法如下

1. 設定目前節點在樹根

2. 如果目前節點有子節點 (child node),就把目前節點先 push到堆疊,然後往下走。有兩個子節點的話先走左邊再走右邊的子節點。

3. 如果目前節點沒有子節點 (child node),或是子節點已經拜訪過,就印出目前節點的號碼,並且 pop 出堆疊上一次儲存的節點,設定成現在要拜訪的節點,然後回到步驟2,直到堆疊變成空堆疊為止。

執行遞迴和堆疊來後序拜訪一棵樹的執行過程

step1:

current node: 7

stack: (empty)

printed order: (empty)

step2:

current node: 7

stack: 7   (###push 7###)

printed order: (empty)

step3:

current node: 3  (###go to left child node###)

stack: 7

printed order: (empty)

step4:

current node: 3

stack: 7, 3  (###push 3###)

printed order: (empty)

step5:

current node: 1  (###go to left child node###)

stack: 7, 3 

printed order: (empty)

step6:

current node: 1

stack: 7, 3

printed order: 1 (###print 1 because no other child nodes###)

 step7:

current node: 3  (###go back to node 3###)

stack: 7  (###pop 3###)

printed order: 1

step8:

current node: 2  (###go to right child node)

stack: 7, 3  (###push 3 again###)

printed order: 1

step9:

current node: 2

stack: 7, 3

printed order: 1, 2 (###print 2 because no other child nodes###)

step10:

current node: 3  (###go back to node 3###)

stack: 7  (###pop 3###)

printed order: 1, 2

step11:

current node: 3 

stack: 7 

printed order: 1, 2, 3 (###print 3 because child nodes are visited###)

step12:

current node: 7 (###go back to node 7###)

stack: (empty) (###pop 7###)

printed order: 1, 2, 3

step13:

current node: 6 (###go to right child node###)

stack: 7 (###push back 7###)

printed order: 1, 2, 3

step14:

current node: 6

stack: 7, 6  (###push 6###)

printed order: 1, 2, 3

step15:

current node: 4  (###go to left child node###)

stack: 7, 6 

printed order: 1, 2, 3

step16:

current node: 4

stack: 7, 6

printed order: 1, 2, 3, 4 (###print 4 because no other child nodes###)

 step17:

current node: 6  (###go back to node 6###)

stack: 7  (###pop 6###)

printed order: 1, 2, 3, 4

step18:

current node: 5  (###go to right child node)

stack: 7, 6  (###push 6 again###)

printed order: 1, 2, 3, 4

step19:

current node: 5

stack: 7, 6

printed order: 1, 2, 3, 4, 5 (###print 5 because no other child nodes###)

step20:

current node: 6  (###go back to node 6###)

stack: 7  (###pop 6###)

printed order: 1, 2, 3, 4, 5

step21:

current node: 6 

stack: 7 

printed order: 1, 2, 3, 4, 5, 6 (###print 6 because child nodes are visited###)

step22:

current node: 7 (###go back to node 7###)

stack: (empty) (###pop 7###)

printed order: 1, 2, 3, 4, 5, 6

step23:

current node: 7

stack: (empty)

printed order: 1, 2, 3, 4, 5, 6, 7 (###print 7 because child nodes are visited###)

done!

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!
  • Irene

    LIFO 是否可譯為後進先出 .

  • Irene

    LIFO 是否可譯為後進先出 .

  • LIFO可以翻譯成 後進先出
    不過中文好像比較習慣說 先進後出
    所以兩種都可以…?

  • LIFO可以翻譯成 後進先出
    不過中文好像比較習慣說 先進後出
    所以兩種都可以…?

  • 新手

    正確的是後進先出,因為LIFO翻譯來講就是後進先出,不是兩種都可以。

  • 新手

    正確的是後進先出,因為LIFO翻譯來講就是後進先出,不是兩種都可以。

  • Guest

    以中文來說都嘛可以,先進來的後出去,後進來的先出去,阿不是都一樣,弄懂堆疊就好了。

  • Minerva

    以中文來說都嘛可以,先進來的後出去,後進來的先出去,阿不是都一樣,弄懂堆疊就好了!