資料結構- 堆疊(Stack)

堆疊

堆疊(Stack)，一種後進先出(Last In First Out)的資料結構，新增、彈出必須要在堆疊頂端執行，舉例來說：當兵的時候，原本正在寢室休息，後來被班長叫去出公差，必須要完成出公差這件事情，才可以再回到寢室休息

操作

對於堆疊的操作主要有兩種

1. 新增(Push)：將資料置放於堆疊的頂端，堆疊頂堆資料變成新置入的資料

2. 彈出(Pop)：將堆疊頂端的資料移除，堆疊頂端變成移除後的最後一筆資料

Note：新增、刪除皆是在堆疊的頂端進行操作

特性

• 具有後進先出(Last In First Out, LIFO)，先進後出(First In Last Out, FILO)的性質

• 新增(Push)、彈出(Pop)，都是從堆疊頂端進行操作，故新增、移除時間複雜度為O(1)

• 搜尋時要先將資料做彈出(Pop)，再將彈出的資料跟搜尋的資料做比對，直到比對成功，故搜尋時間複雜度為O(n)

參考資料：

• 堆疊

• 《演算法圖鑑》第一章：資料結構

• Data