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)。

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

#資料結構 #DataStructure #初學者







你可能感興趣的文章

D1_Git

D1_Git

[練習] JSONP 實作

[練習] JSONP 實作

Advanced iOS App Architecture (Second Edition): Real-World App Architecture in Swift

Advanced iOS App Architecture (Second Edition): Real-World App Architecture in Swift






留言討論