<span class="bsf-rt-reading-time"><span class="bsf-rt-display-label" prefix="閱讀時間:"></span> <span class="bsf-rt-display-time" reading_time="5"></span> <span class="bsf-rt-display-postfix" postfix="mins"></span></span><!-- .bsf-rt-reading-time -->【資料結構】堆疊 (Stack) 是什麼?3張圖馬上搞懂

【資料結構】堆疊 (Stack) 是什麼?3張圖馬上搞懂

堆疊在日常生活中的應用俯拾皆是,像是搭電梯、堆積木、疊衣服…等等,對於我們來說這些事情非常直覺,所以其實不太容易察覺到,而以概念來說堆疊不難理解,只是它跟陣列還有指標息息相關,如果還不熟悉的話記得回去複習一下!

思考時間:大家來想想看,上述這些事情有什麼共同點嗎?

答案會在後面的介紹中揭曉 。

現在,就先開始介紹堆疊 (Stack)!

堆疊 (Stack) 是什麼?

Stack 是一個有序的串列,在 Stack 上的所有操作都會在同一個端點進行,而這個端點通常會被稱為 – top

回想一下上面的問題,不知道大家想到了什麼?

發現了嗎~上述的事情都有一個特性 – 後進先出 (LIFO, Last-In-First-Out)

舉個例子:

搭電梯的時候,最後進來的人通常會站在最外面,因此如果後面的人想要出電梯,一定要最後進來的人先出去,這就是後進先出的概念。

也就是 Stack 最大的特性!

Stack 概念圖
Stack 概念圖

p.s. 頂端稱為top,底部稱為bottom!

Stack的基礎 – 區域變數(以C語言為例)

重要概念#1:全域變數 v.s. 區域變數

  • 全域變數 (global variable) – 在編譯階段配置記憶體空間。
  • 區域變數 (local variable) – 在執行階段進入function之後才配置記憶體空間。

*** 區域變數在function結束執行之後,記憶體空間也就隨之釋放 ***

重要概念#2:function的參數屬於區域變數

C語言在呼叫function的時候,會需要處理function的參數和其中的區域變數,這時候就會將變數和參數都用Stack儲存,在程式呼叫function之前,會把區域變數、參數、程式返回位址全都存入Stack,等到需要的時候,再從Stack把值一一取出來,回復到原來的狀態。

Stack 實作方法?

方式#1:利用陣列

#define MAX_STACK_SIZE 50

typedef struct {
    int age;
    char name[10];
} person;

person stack[MAX_STACK_SIZE];
int top = -1;

top 一開始會設為 -1,表示stack為空。

方式#2:利用鏈結串列 (Linked list)

這邊先附上程式碼,關於鏈結串列 (Linked list) 的教學我之後會盡快補上!

那時,大家可以先去看看 Linked list 的概念之後,再回來看這段程式碼。

#define MAX_STACKS 10

typedef struct {
    int age;
    char name[10];
} person;

typedef struct stack *stackPointer;
typedef struct stack {
    person data;
    stackPointer link;
};

stackPointer top[MAX_STACKS];

Stack最常用到的4個function

Function#1:Push (Insert)

目的:將資料放進 Stack 的『最上面』。

stack push & pop
push & pop
void push(person data) {
    if (top >= MAX_STACK_SIZE-1)
        stackFull();
    stack[++top] = data;
}

Function#2:Pop (Delete)

目的:將『最上面』的資料從 Stack 中移除。

stack push & pop
push & pop
void pop() {
    if (top == -1)
        return stackEmpty();
    return stack[top--];
}

p.s. pop其實並沒有真正移除資料,只是將top的值-1,因為之後作push的時候,自然就會將舊的資料蓋過去了。

Function#3:isFull(判斷Stack是否已滿)

int isFull() {
    if (top >= MAX_STACK_SIZE-1)
        return true;
    return false;
}

有發現嗎?上面在push之前,我們先檢查了Stack是不是滿了!

如果滿了,就不能再push。

Function#4:isEmpty(判斷Stack是否已空)

int isEmpty() {
    if (top == -1)
        return true;
    return false;
}

這邊也同樣,在pop前,要先檢查Stack是否為空!

如果空了,就不能pop。

如果Stack已滿,繼續push會發生什麼事呢?

這就會發生非常著名的 Stack Overflow

stack overflow
Stack Overflow

Stack的廣泛應用

Stack最大的特性是『後進先出』,換句話說就是『儲存先前的資訊』,所以時常會被用來處理需要『回復到先前狀態』的問題,因為最近的資訊會被儲存在最上方,而這類的問題也被稱為Back-Tracking(回溯)Problem

像是:文書軟體(Word, Excel, Powerpoint, Notion…)中的上一步功能、Google瀏覽器的上一頁功能…等等,就是這個概念!

#1:字串反轉

概念:將字串中的字元,逐一push進去Stack,全部結束後,再pop出來。

string reverse
字串反轉概念圖

#2:老鼠走迷宮

假設:

迷宮共有8個方位可以走,而行走的優先順序是上、下、左、右、右上、右下、左上、左下,行走方式是依照上述八個方向的優先順序嘗試,每走一步,如果是死路,那麼就要透過Stack回溯,直到找出正確的路。

老鼠走迷宮
老鼠走迷宮

#3:河內塔問題(Tower of Hanoi)

規則:

  1. 每次只可以移動一個圓盤。
  2. 不論什麼情況,圓盤必須保持上小下大的原則。

玩法:將A柱上所有的圓盤移到C柱。

河內塔!

當圓盤數=3,示範步驟如下:

step 1

從A柱將1號圓盤移到C柱。

step 2

從A柱將2號圓盤移到B柱。

step 3

從C柱將1號圓盤移到B柱。

step 4

從A柱將3號圓盤移到C柱。

step 5

從B柱將1號圓盤移到A柱。

step 6

從B柱將2號圓盤移到C柱。

step 7

從A柱將1號圓盤移到C柱。

Done!

實際操作看看吧!

#4:function的呼叫與返回

副函式呼叫與返回

當Program A呼叫Program B的時候,會將返回位址a存進Stack中,當在Program B呼叫Program C的時候,會再將返回位址b存進Stack中,當Program C結束執行的時候,就會從Stack取初返回位址的值,因此就會先回到b,再回到a。

總結

以上就是堆疊 (Stack) 的基本觀念跟應用,希望大家理解之後能夠去思考如何靈活運用,因為Stack只是工具,而能夠使用工具來達成目的才是最重要的!

對文章有任何問題的話,都歡迎在下面留言讓我知道哦!

By Hani

This Post Has 13 Comments

    1. Han I

      哈哈哈哈,看來我太晚創立Hani CS Daily了!

  1. ting wei

    一個簡單堆疊得背後,原來有這麼深奧的邏輯與應用,內容也寫得很詳盡,很好的文章。

    1. Han I

      謝謝你,希望對你有幫助!

  2. Wei

    對於程式語言完全沒有涉略的我
    都可以因為你的圖示而讓我比較知道這些是用在哪裡
    非常用心!
    謝謝版主細心分享。

    1. Han I

      圖真的畫了很久XDD,對你有幫助我很開心!

  3. 這對於程式有興趣的人,真的是很好的資訊欸! 感謝分享ㄋㄟ~~

  4. 小葉

    剛好最近在自學程式語言,看完文章的介紹後,真的會對函數的應用更加上手

    1. Han I

      謝謝你~如果有想要看的主題也可以跟我說喔!

  5. 尹辰

    大學有學過程式語言過,這對有在學語言的會有幫助,謝站長分享

  6. Brian

    程式語言設計是一個好深好深的技能
    版主能夠整理得這麼淺顯易懂真的很威!
    通常學習一個簡單的語言,大概需要花費多少時間才能有個基礎呢?

    1. Han I

      Hi Brian,其實程式語言的學習非常的深且廣,而語言本身只是工具,主要還是要看你想要透過語言來達成什麼目的。
      如果只是想要了解一個語言的基礎,其實不會花非常多的時間!

Leave a Reply