擁抱「資料結構」的「演算法」(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

只要某一類別有提供以下的方法,我們都可以稱這個類別是一種堆疊:

  1. Create : 可建立一個空的堆疊
  2. Push : 可在頂端新增資料,並得到一個新的堆疊
  3. Pop : 可刪除頂端資料,並得到一個新的堆疊
  4. 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


留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

Visual Studio 自動排版格式化程式碼

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明