築夢角落

致力於用最生活化的例子讓所有人都能懂程式,也喜歡分享動漫、小說心得,以及自己的所見所聞、所思所想。

堆疊(stack)是什麼?何時會用到這種資料結構?

最後更新時間 : 2022-11-19 | viewed : 25

簡單介紹什麼是堆疊

今天來簡單介紹什麼是堆疊,以及堆疊常見的應用。

 

目次

 

什麼是堆疊?


堆疊在程式設計中是一種資料結構,具有先進後出的特性。

所謂的先進後出,是指越早進入堆疊的資料要比較晚才能取出來

舉例來說,如果我們在一根直立的木棍上,依序放入很多甜甜圈,當你想取出最底下的甜甜圈時,就一定要先拿走在它之上的甜甜圈,這就是先進後出的概念。

 

常見應用


因為堆疊具有先進後出的特徵,所以經常會被用在記錄返回路徑,比如我們在逛網頁的時候,瀏覽器會知道我們開啟每個網頁的順序,所以我們才能不斷返回上一頁,最終回到第一頁

 

如何實作堆疊?


堆疊實作一般會用到陣列(Array)串列(Linked list)

以上面甜甜圈的例子來說,陣列就是直立的木棍,存入陣列的資料就是甜甜圈。

來看個程式例子,這裡我們以 javascript 為例:

let stack = [];
let topIndex = -1;

// 存入(push)堆疊
stack[++topIndex] = "a";
stack[++topIndex] = "b";
stack[++topIndex] = "c";

// 從堆疊取出(pop)
let c = stack[topIndex--];
stack = stack.slice(0, stack.length - 1);
let b = stack[topIndex--];
stack = stack.slice(0, stack.length - 1);
let a = stack[topIndex--];
stack = stack.slice(0, stack.length - 1);

stack = stack.slice(0, stack.length - 1); 在這裡的意思是,把陣列裡最後一個元素移除,同時陣列的長度也會縮減,若最後 stack 的長度為 0,表示堆疊裡已經沒有東西了。

也可以寫成 stack = stack.slice(0, topIndex); 因為此例中的 topIndex = stack.length - 1

因為這不是單純邏輯上的巧合,所以這樣寫可能會更符合堆疊的語義,當 topIndex = -1 時,也表示堆疊清空。

不過這在作法上並不是唯一的選擇,你也可以填入 0 或 null 等等,去表示某個堆疊位址是沒有值的,藉此保證堆疊空間的大小是固定不變的

 

在上例中我們可以發現,一個資料結構是不是堆疊,主要是跟我們存取資料的方式有關,如果我們用別的步驟存取資料,這個名為 stack 的陣列就不是堆疊了。

為了有效限制存取方式,藉此保證陣列一定會以堆疊的形式被使用,通常來說都會進行某種程度的封裝或抽象化。

事實上,javascript 就內建堆疊的使用方式,所以上面的程式可以改寫成這樣

let stack = [];

// 存入(push)堆疊
stack.push("a");
stack.push("b");
stack.push("c");

// 從堆疊取出(pop)
let c = stack.pop();
let b = stack.pop();
let a = stack.pop();

push() 會從陣列前端開始存入資料,pop() 會從陣列尾端依序取出資料,執行結果會跟第一個例子一模一樣

經過封裝或抽象化後的程式碼有了清楚的語義,變得更白話,這樣是不是更容易維護了呢~

 

經典例子


程式設計中最經典的堆疊應用題型老鼠走迷宮

如果我們希望有隻老鼠能成功走出迷宮,我們必須讓老鼠知道哪些路徑已經探索過,不要重複走進死路,這時堆疊就能派上用場。

假設迷宮的地板有格子,最簡單的作法就是讓老鼠按照上、右、下、左的順序,一次往一個方向前進一個格子,步驟大致如下:

(1) 站在起點,把起點的座標丟入堆疊,並在地圖上標記這格為已探索。

(2) 檢查上方是否有未探索過的路,若有則前進一格,並把這格的座標丟入堆疊,另在地圖上標記為己探索。

(3) 如果上方不能走,就檢查右方是否有未探索過的路,若有則前進一格,並把這格的座標丟入堆疊,另在地圖上標記為已探索,然後再次從(2)開始判斷。

(4) 如果右方不能走,就檢查下方是否有未探索過的路,若有則前進一格,並把這格的座標丟入堆疊,另在地圖上標記為已探索,然後再次從(2)開始判斷。

(5) 如果下方不能走,就檢查左方是否有未探索過的路,若有則前進一格,並把這格的座標丟入堆疊,另在地圖上標記為已探索,然後再次從(2)開始判斷。

(6) 如果左方不能走,表示老鼠走到死路了,我們要依照堆疊的記錄沿途返回,每返回一格都要再次從(2)開始判斷。


畫成流程圖來看會比較清楚(點圖可放大):

老鼠走迷宮流程圖

從執行結果來看,因為老鼠有用堆疊記錄行走順序,所以可以沿途返回而不會迷路,並且地圖上有標記哪些路已探索,所以不會去重複探索那些已知的死路,只要迷宮確實有出口,老鼠就能用機械化的步驟走出迷宮,而最後堆疊裡的記錄也會是老鼠走出迷宮的路徑記錄。

這個解決問題的過程正好也是深度優先搜尋(DFS)演算法的一種應用。

 

呼叫堆疊


現代程式語言幾乎都有函式(function)的設計,讓我們先來看一段 javascript 程式碼。

1.  let a = 10;
2.  let b = 20;
3.  let result = 0;
4.
5.  result = add(a, b);
6.  console.log("結果: " + result);
7.
8.  function add(a, b) {
9.    return a + b;
10. }

以上面的例子來說,當程式碼執行到第 5 行時,遇到了 add(),但是 add() 的定義是在第 8 行,所以程式必須先跳到第 8 行執行完該程式區塊後,再返回第 5 行,把 add() 的結果賦值給 result,接著才執行第 6 行顯示結果。

函式呼叫同樣有沿路返回的特性,所以許多程式語言的底層會使用堆疊來實現,一般稱為「呼叫堆疊(Call stack)」。

如此一來,當你的函式裡還有另一個函式、一層又一層呼叫下去時,程式依然知道最終該返回哪一行繼續執行。

(為求說明簡單,此處省略了程式計數器記憶體位址等較複雜的觀念,但概念上大致相同。)

 

其他應用


堆疊還有很多其他應用,比如在系統程式設計中,四則運算會利用堆疊來達成先乘除、後加減、括號優先處理的目的。

某些程式語言在呼叫函式時,可以傳入不定數量的參數,也和堆疊的運用有關。

總的來說,在解決工程學問題時,堆疊是很常見的應用,但是大多數程式語言的函式庫都已經提供了現成工具,讓我們在開發商務軟體或系統時,能在不知不覺中使用堆疊,減少了直接碰觸堆疊的需要。

 

總結


堆疊是一種典型資料結構,應用情境很多,只是一般的業務邏輯比較少有機會運用,所以有時難以察覺它的重要性。

比較有可能的或許是Debug,比如在瀏覽器的開發人員工具裡就有觀察呼叫堆疊的視窗。

開發人員工具的呼叫堆疊

只要在 js 程式碼某處寫一行 debugger(或是在開發人員工具中找到 js 程式碼,指定中斷點),讓程式中斷、改用單步執行,就能看到函式的呼叫順序,藉此尋找問題。

我自己幾乎不會這麼做,但的確在公司見過有人這麼做,供大家參考。


業務邏輯是泛指所有與解決工程學問題無關程式邏輯,通常出現在 OSI 模型中的應用層,是構成應用程式核心功能的主要部份。大部份軟體公司的工作都活躍在應用層,舉凡網頁前後端、手機APP、Word、Excel,這些程式開發大多屬於應用層的範疇。)

 

 
我要留言!
 

X
暱稱(選填)
email(選填,僅站長可見。)
留言 To:#