擁抱「資料結構」的「演算法」(07) - 堆疊 Stack
前言
對線性結構的陣列與串列有初步了解之後，接下來我們要來介紹其他種資料結構，今天就先從堆疊開始講囉！
生活常識
中秋節快到了，好想吃烤土司，大家有發現當要從常常一串的吐司中，拿取一片吐司的時候，只能從最上面拿嗎XD？隨著一片片的吐司被吃掉，最後的那一片，通常沒有人想吃XD，從吐司的例子會發現，吐司在包裝的時候，最下層的吐司是最先放進去的，但在食用的過程中，最後放進去的吐司，最先被吃掉
圖片來源:https://www.pecos.com.tw/brands-%E6%99%A8%E5%85%89.html
你家中有洗衣籃嗎？我自己習慣是等衣服堆疊累積到週末，才統一拿去洗，因為個性迷糊，常常把衛生紙、錢，或是重要的發票留在口袋裡，等到發現時，可能已經成為糨糊了！所以在將衣服丟入洗衣機時會檢查一下口袋，當我們從洗衣籃拿衣服的時候，最從最頂端的衣服開始拿，也就是拿到昨天的衣服，在拿到前天的衣服，會發現最後丟進洗衣籃的衣服，`最先被拿出來
圖片來源:https://www.pexels.com/zh-tw/photo/4546168/
類似的生活例子：自助餐的餐盤、裝箱好的書籍，都是要從最上面拿取哦！
專業知識 - 堆疊 Stack
抽象資料型態
堆疊是一種抽象資料型態(Abstract Data Type, ADT)，看到抽象內心是否有一種滿頭問號的感覺，就比如說當你聽到水果，會覺得水果抽象嗎？指的到底是蘋果還是香蕉呢？當描述是指一個大的範圍，不夠仔細、不夠具體的時候，其實就是一種抽象化的名詞。
如果你跟同事說，我買了一台車，那同事可能會進一步問你，你買機車還是汽車？買什麼牌子？是轎車來是休旅車？所以車其實也是一種抽象類別，隱藏了許多內部細節，因為我們對於車子的認知大概是以下特性，只要可以符合這些特性，就可以稱為某一種車：
- 需要駕駛
- 可以發動
- 可以煞車
- 可以移動
- 可以載物
如果要具體的描述，應該是這樣說：我買了一台白色的五人座廠逢轎車，而抽象資料型態(ADT)，其實就是讓我們可以簡易的操作某些特有方法，而不用去在意細節是如何實作的，例如：今天不管開哪一種車，你只要知道如何啟動就好，不需要解引擎是如何製造或運作的，而抽象化就是要將這些不需要知道的細節隱藏起來，只需要知道能夠使用那些功能即可，例如車子的功能有啟動、煞車與熄火
其實抽象這個詞，在演講的時候也蠻常發生的，有時候演講聽著聽著就睡著了，其中可能的原因是，講者說話方式太抽象了，常常講到一些專有名詞，例如資料結構，涵蓋的是一個很大的範圍或觀念，然後腦袋就會慢慢無法思考，而進入睡眠模式，有些地方使用抽象很好(例如一般民眾只要懂得如何開車，不需要懂車子的製造過程)，但還是要看情況來選擇，如果今天是要對車廠進行員工訓練，那就必須做細節的解說
堆疊
特性：
- 只能從堆疊的
最頂端存取資料 - 只能從堆疊的
最頂端新增或刪除資料 - 資料的存取必須符合
後進先出(Last In First Out, LIFO)
堆疊的 ADT
只要某一類別有提供以下的方法，我們都可以稱這個類別是一種堆疊：
- Create : 可建立一個空的堆疊
- Push : 可在頂端
新增資料，並得到一個新的堆疊 - Pop : 可
刪除頂端資料，並得到一個新的堆疊 - Peek : 回傳堆疊頂端的資料
堆疊的實作
一般可以使用陣列或串列去實作出堆疊，但程式碼的部分就先不討論，我們可以使用 C# 內建的 Stack 類別來操作看看
依序將12345，使用 Push 方法，存入堆疊頂端，然後再依序將資料印出
Stack<string> numbers = new Stack<string>();
numbers.Push("1");
numbers.Push("2");
numbers.Push("3");
numbers.Push("4");
numbers.Push("5");
foreach( string number in numbers ) //依序印出
{
Console.WriteLine(number);
}
Console.WriteLine("\n取出最頂端的資料 : " + numbers.Pop());
輸出結果：
5
4
3
2
1
取出最頂端的資料 : 5
透過上述程式碼與輸出，可觀察出 C# 的 Stack 類別有符合後進先出(Last In First Out, LIFO)的特性，也有提供 ADT 所定義的方法
實際應用
- 資料反序輸出，例如將
由小到大的資料改成由大到小 - 迴文判斷
- 河內塔問題
- 括號配對
今日小結
堆疊其實很像我們平常玩的撲克牌，發牌的時候只能從頂端開始，而後進先出的概念，在生活中存在很多例子，例如：冰箱的東西，大家可以試著當個生活觀察家，會發現很多有趣的現象，會更有助於我們理解這些資料結構
今日謎題
小花與小明在玩桌遊，必須從下堆卡牌中，從頂端輪流取牌，在旁邊觀戰的小乖發現了神祕訊息，你知道小乖看到什麼訊息？
昨日解謎
謎題說明：不管從哪個位置開始讀取，不段的重複讀取兩圈之後，應該就會發現 circular 這個單字一直循環出現，答案就是circular
留言
張貼留言