# 棧 (stack)

## 棧的介紹
1. 先進後出(FILO)的有序列表
2. 是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(top)，另一端為固定的一端，稱為棧底(bottom)。
3. 入棧稱為PUSH，出棧稱為POP，PUSH和POP的順序和現實生活中堆書本是一樣的。


## 棧的應用場景
1. 子程序的調用：在跳往子程序前，會先將下個指令的地址存在棧中，直到子程序執行完後再將地址取出，以回到原來的程序中。
2. 處理遞歸調用：和子程序的調用類似，只是除了儲存下一個指令的地址外，也將參數、區域變數等數據存入到棧中。
3. 表達式的轉換[中綴表達式轉後綴表達式]與求值
4. 二元樹的遍歷
5. 圖形的深度優先搜尋法(DFS)

## 棧的其他變體

### Monotonic Stack
想像 Array 的 index 代表每個人的座號， index 內存放的是身高，我們可以透過 monotonic 來找每個人後方第一個比他高的人，如下圖:


Monotonic Stack 內可以放身高，也可以放對應的座號。

Monotonic Stack 操作框架
====================

要操作 Monotonic Stack ，就必須謹記以下性質:

1. Monotonic Stack 內的元素一定維持 monotonic 特性 (單調遞增或單調遞減) 。
2. 每個元素**都會**加入 stack ，如果加入新元素會破壞 monotonic ，就必須將 stack 頂端元素移除，不斷移除 stack 頂端元素直到不違反 monotonic ，接著再加入元素。
3. Monotonic Stack 可以幫助找到向左/向右走訪第一個比當前元素小/大的元素，左/右跟小/大總共有四種組合。

如果要向左找**第一個比 input 元素小的**元素，以下圖為例，
從 Array 的起點開始走訪並依序加入 stack ，stack 內元素都維持單調遞增的排序，直到準備放入 7 時，放入 7 會破壞單調遞增，因此必須 pop 元素直到可以維持單調遞增，當 7 可以放入 stack 之前，此時 stack 頂端元素即是第一個比 7 小的元素。
Stack 頂端的元素應該保持是向左找第一個比 input 小的元素，且 top 會是 stack 內最大的，(要找的是第一個比 input 元素小的，因此越小的應該越要在 stack 底部 ，才不會輕易被 pop out ) ，stack 內的元素 pop 出來的結果就應該遞減。

如果是要向右找呢? 很簡單，就從 array 尾端往前依序走訪處理即可，向右找第一個比 input 元素大的，stack top 元素會是 stack 內最小的， Monotonic Stack 內的元素 pop 出來就必須維持遞增。