DAY 04 : 資料結構緒論

4.1 堆疊(Stacks)

前一章我們在討論線性串列，而這一章要來討論｢後進先出的線性串列」—堆疊。

4.1.1什麼是堆疊?

堆疊是規定只能在尾端進行插入和刪除等作業的線性串列，允許插入和刪除資0料的那端，我們稱之為堆疊頂端(Top)，而另一端就叫做堆疊底端(Bottom)，沒有任何資料元素的堆疊，我們稱它為空堆疊。

前面有提到堆疊只能從點端插入或刪除資料，這代表一個資料越早進去堆疊，就會越晚出來，反過來就是最後進去的會最先出來，這就是｢後進先出」(Last in-First out, LIFO)的線性串列，又叫做LIFO結構。
接下來來講一下堆疊的插入與刪除。

4.1.2 進堆疊與出堆疊

請搭配下圖內的編號

1. 堆疊的插入稱為｢進堆疊(Push)」，也稱為推入堆疊。
2. 堆疊的刪除稱為｢出堆疊(Pop)」，也稱為彈出堆疊。
3. 儲存堆疊的長度(StackSize)是有限制的，因此堆疊頂端位置必須要小於StackSize
4. 堆疊裡沒有任何的資料元素稱為｢空堆疊」。
5. 堆疊裡以存放滿元素稱為｢滿堆疊」。

4.1.3 兩堆疊的共用空間

堆疊的儲存空間是需要事先確定儲存空間大小的，那如果後來發現空間不夠怎麼辦呢?這時候就可以讓一個陣列同時儲存兩個具有相同型別的堆疊。

兩個指標之間相差1時，也就是top1+1 == top2就代表這兩堆疊滿了。
由於兩堆疊共用空間還是有分成兩個堆疊所以還是需要堆疊號參數(stackNumber)。

不過會使用這樣的資料結構，通常是當兩個堆疊的需求相反(例:一個堆疊增長，另一個遞減)時才會使用。