理解堆疊

堆疊是一個先進後出(FILO, First-in-Last-out)特性的資料結構， 但應用堆疊則必須更深入的理解相關算法的原理。

為什麼堆疊可以處理中序式，之前查看中序式轉後序式的算法過程可能沒辦法清楚明白。 在解決幾題LeetCode題目之後大概理解其原理。

保存上一狀態

之前在解 Shortest Unsorted Continuous Subarray 與 Daily Temperatures 皆是透過堆疊保存上一狀態，在需要的時候回溯到上次的情況。

電腦中記憶體區段中的stack段，保存上一狀態與區域變數等。 所以DFS或其他遞迴演算法也是透過堆疊去保存上一狀態，來達成返回上一次狀態的目的。

由此可知，堆疊的應用主要用於保存上一次的狀態，並在需要的時候重新取回資料。

中序轉後序

知道堆疊可以回溯上一個狀態之後，再次理解中序轉後序演算法的原理。

如1 + 2 * (18 / 9 + 2)我們可以嘗試轉為後序式

id stack output
1 + 1 2
2 +*(/ 1 2 18 9
3 +*(+ 1 2 18 9 / 2
4 +* 1 2 18 9 / 2 +
5 (empty) 1 2 18 9 / 2 + * +

當2變成3那種情況，因為/的要比+優先輸出，將上次遇到的/優先彈出。

查看第二個式子，1 + 2 * 3 / 3 + 1

id stack output
1 + 1 2
2 +/ 1 2 3 * 3
3 + 1 2 3 * 3 /
4 + 1 2 3 * 3 / + 1
5 (empty) 1 2 3 * 3 / + 1 +

而堆疊在這之中，保存先前的+，之後在*與/輸出之後才將其輸出。

參考

Stack Data Structures