看過品客洋芋片罐子嗎？

你只有一個方式可以拿出洋芋片，就是從上方的開口拿出來。
而且想要拿到下層的洋芋片，你必須先將上層的洋芋片依序拿出。

堆疊這個資料結構就是品客洋芋片的罐子。

堆疊介紹

堆疊的概念是先進後出（FILO, First In Last Out）、後進先出（LIFO, Last In First Out）。

堆疊只要使用一個列表就可以實作出來了，當然我們還需要幾個變數用來記錄他的特徵，例如：top。另外，為了提高可讀性，我們會將堆疊的行為包裝成函式，例如：push, pop

• top：整個堆疊最重要的變數，我們可以知道現在最上層元素的索引值為何。當 top 為 -1 時，代表堆疊內無任何元素，因此初始化 top 為 -1
• push(data)：新增元素至最上層，top + 1
• pop()：移除最上層元素，top - 1（當 top = -1 時，拒絕 pop()）

stack = []
top = -1

def push(data):
    stack.append(data)
    top += 1

def pop():
    if (top >= 0):
        stack.pop()
        top -= 1
        
def getTop():
    if top < 0:
        return None
    else:
        return stack[top]

如果稍微了解物件導向的概念，以上這個程式碼可以轉化成一個類別與類別方法，如此一個程式內就可以允許多個堆疊同時運行。

老鼠走迷宮

題目敘述：
給定一個二維列表代表迷宮(row * col)，包含數字 0（代表路） 與 1（代表牆壁），回傳老鼠走迷宮的路徑。註：起點必為 list[0][0]，終點必為 list[row-1][col-1]。假設迷宮必有一條從起點到終點的路。

分析：
這個是堆疊經典的例題，關鍵是需要「回溯」，也就是說未來你需要之前使用過的資料。

當你到了一個岔路口，扣除剛走過的道路，最多有三種方向可繼續前行。
選擇一條路，然後繼續向前行，大致會遇到幾種結果：

1. 抵達終點
2. 遇到岔路口：繼續選擇前進方向
3. 死路（四周都是牆壁）：往回走

往回走聽起來很簡單，但是怎麼實踐？
那就是使用一個堆疊紀錄走過的路程！！
只要是向前走，都要把座標位置放進堆疊中；如果需要往回走，你會發現其實堆疊中的top就是我們的上一步，既然我們有所有上一步，我們就可以回到岔路口，選擇下一條路，也許可以直接抵達終點，也可能需要回溯。

作法：

1. 宣告一個變數紀錄當前座標
2. 宣告一個列表作為堆疊
3. 進入 while 迴圈，直到抵達終點
4. 迴圈內部要處理上述的事情：
   • 遇到岔路，如何向前行
   • 遇到死路，如何回溯
5. 堆疊裡存的資料即為起點至終點經過的座標

實作堆其實不難，難點在於何時該用堆疊。
堆疊的運用還有很多，如「火車進站的問題」等。

下一篇，來介紹另一種資料結構「佇列 Queue」吧!