Stack 堆疊

1.什麼是Stack?

如果把input的資料當成積木，Stack就像疊積木一樣，把新加入的磚塊放在後加入的上面，要拿出也是把新加入的拿出，屬於LIFO (Last - in -First out)模型。

2. System Stack

有些語言函式的呼叫也是個Stack，比如Function A呼叫了Function B，而Function B又呼叫了Function C，用Stack結構來表示的話：

FunctionC

FunctionB

FunctionA

FunctionC會先執行，完成後才會是B與A。
當然囉，如果函式巢狀增加，這些積木也會越疊越高，而高度也是有個極限的，當到某個地步後還要疊的話，就會發生stack overflow的情形，所以在Recursive的終止條件上要特別注意。


4.Stack 的抽象資料結構

• Stack CreateS(maxStackSize) ：創造一個空Stack，並給予這個Stack最大容許儲存量
• Boolean IsFull(stack, maxStackSize)：確認stack是否滿了，避免push時把item丟入錯誤區塊
• Boolean IsEmpty(stack)：確認stack是否為空，避免pop時丟出的錯誤資料
• Stack Push(stack,item)：配合isFull使用，當還有位置放時，把item放入stack
• Element Pop(stack)：配合isEmpty使用，當裡頭還有物件，就把物件丟給item

實作stack最簡單的方法就是用一維陣列去處理它，為此我們需要兩個東西，一個是陣列stack[MAX_SIZE]來儲存，另一個就是top，用來表示目前存了多少item。

top

...

...

Stack[2]

Stack[1]

Stack[0]

在創造一個Stack時，可以把top設為一個非合理範圍，比如 -1，這樣便可在isEmpty上做判斷。
每當push就top++，如果top合理，便加入物件，pop則把top--，丟出物件。

5.一些Stack的應用

System Stack就是堆疊的基本應用，他用於在Run-time時決定Function呼叫的順序。在進行Backtracking與Recursive上，也涉及了Stack的概念。