堆疊 (C++)
C++ Stacks
堆疊是一種有序串列 (ordered list) 的資料結構，而元素的加入與刪除都是在稱之為頂端 (top) 的同一端處理，且遵循後進先出 (Last-In, Fist-Out; LIFO) 的原則。當我們將元素加入堆疊的動作稱之為推入 (push)；反之，將元素從堆疊中刪除的動作則稱之為彈出 (pop)。
圖一 堆疊的推入 (push) 與彈出 (pop)
範例程式一
#include <iostream>
#include <stack> /* 提供 stack 容器對接器 (container adaptor) 的標頭檔 */
using namespace std;
int main() {
stack<int> my_stack; /* 建立堆疊 */
int i, num;
for (i = 0; i < 5; i++)
{
cout << "推入第 " << i << " 個整數元素：";
cin >> num;
my_stack.push(num); /* 將元素推入堆疊 */
}
cout << "\n堆疊內元素由頂端至底部依序彈出\n" << endl;
while (!my_stack.empty()) { /* 當堆疊中還有元素時繼續執行 while 迴圈 */
int current_top = my_stack.top(); /* 回傳堆疊最頂端的元素並指定給變數 current_top */
cout << current_top << "\n"; /* 輸出堆疊最頂端的元素 */
my_stack.pop(); /* 移除 (彈出) 堆疊最頂端的元素 */
}
return 0;
}
範例程式一輸出
堆疊的應用
堆疊常用在下列這幾個部分：
1. 函數呼叫 (function calls)
作業系統利用呼叫堆疊 (call stack) 來管理函數呼叫過程，每一次函數被呼叫，系統會在呼叫堆疊中會推入一個對應該函數的呼叫框 (call frame) 或堆疊框 (stack frame) 至堆疊的頂端。 呼叫框內包含函數執行所需要的參數 (parameters)、區域變數 (local Variables)、呼叫的函數在其結束執行後的返回位址、以及執行此函數前的 CPU 暫存器狀態 ( 以供函數執行完畢後，呼叫前的暫存器狀態能回復 )。當函數執行完畢返回時，該呼叫框就會被彈出 ( 或刪除 )。
如果有一個 fun_B() 函數在 fun_A() 函數內被呼叫，系統在呼叫堆疊中會先推入 fun_A() 函數的呼叫框，再推入 fun_B() 函數的呼叫框。當 fun_B() 函數執行完畢，fun_B() 函數的呼叫框會被彈出，程式回到返回位址去執行，呼叫框內的參數與區域變隨之刪除，此時 fun_A() 函數的呼叫框會出現在最頂端 (top)。如圖二所示，處理器內的堆疊指標暫存器 (stack pointer) 會存放呼叫堆疊最新頂端的位址 ( 指向堆疊最新的頂端 )。 當執行時呼叫一新的函數，該函數對應的呼叫框會被推入呼叫堆疊中；而當函數執行完畢，它的呼叫框會被彈出 ( 刪除 )，如圖三所示。如此一來有了堆疊，多個函數的呼叫與其返回的順序才不會發生錯誤。
圖二 當函數被呼叫時，其對應的呼叫框會被推入堆疊中
圖三 當函數執行完畢時，其對應的呼叫框會被彈出堆疊
範例程式二
#include <iostream>
using namespace std;
void fun_A();
void fun_B();
void fun_C();
int main() {
cout << "呼叫 fun_A() " << endl;
fun_A();
return 0;
}
void fun_A()
{
cout << "呼叫 fun_B() " << endl;
fun_B();
cout << "fun_A() 執行完畢" << endl;
return;
}
void fun_B()
{
cout << "呼叫 fun_C() " << endl;
fun_C();
cout << "fun_B() 執行完畢" << endl;
return;
}
void fun_C()
{
cout << "fun_C() 執行完畢" << endl;
return;
}
範例程式二輸出
2. 遞迴 (Recursion)
一般利用程式來解決問題常見的方法為迭代法 (iteration)，也就是迴圈結構。 但當一個問題可以分解成多個同樣類型的小問題時，遞迴就會是可讓問題解決變簡單的常用方法。在程式中遞迴就是一種利用函數呼叫函數本身的方式來解決問題，這樣的函數被稱為遞迴函數。而每一次呼叫函數本身，該函數對應的呼叫框就會被推入堆疊。此外，遞迴函數必須有遞迴終止條件，以避免無窮無盡的呼叫函數本身，造成堆疊溢位。
例如將數字由十進制轉換成二進制，就可以利用遞迴來處理。以十進制數字 35 為例，若要將其轉換成二進制，我們可以將 35 除以 2 得到商數為 17 ( 第一個商數 ) 且餘數為 1 ( 第一個餘數 )。 接著再將第一個商數 17 除以 2 得到商為 8 ( 第二個商數 ) 且餘數為 1 ( 第二個餘數 )。繼續將第二個商數 8 除以 2 得到商為 4 ( 第三個商數 ) 且餘數為 0 ( 第三個餘數 )。再將第三個商數 4 除以 2 得到商為 2 ( 第四個商數 ) 且餘數為 0 ( 第四個餘數 )。 繼續將第四個商數 2 除以 2 得到商為 1 ( 第五個商數 ) 且餘數為 0 ( 第五個餘數 )。最後將第五個商數 1 除以 2 得到商為 0 ( 第六個商數 ) 且餘數為 1 ( 第六個餘數 )，因為商已經是 0 就可以停止。轉換出來的結果為由第六個餘數依序由左開始往右寫至第一個餘數，即 100011，如圖四所示。
圖四 十進制數字 35 轉換成二進制 10011
由上可知，整個十進制數字轉二進制的過程，都是重複在將商數除以 2 得到新的商再取餘數，而商是愈除愈小，最終商的值會為 0。因此我們可以用遞迴函數來處理這轉換，且遞迴終止條件為商的值為 0 時。
範例程式三
#include <iostream>
#include<cmath> /* 執行 x 的 y 冪次計算的 double pow(double x, double y) 函數定義於此函數庫 */
using namespace std;
void dec_to_bin(int decNum, int& binDigit, int cnt); /* 宣告將十進制數字轉二進制的函數 */
int main()
{
int count = -1; /* 變數 count 代表權值 */
int bin = 0; /* 變數 bin 代表轉二進制結果，初始化為 0 */
int dec_num; /* 變數 dec_num 代表十進制值數字 */
cout << "十進制轉二進制" << endl;
cout << "輸入十進制值：";
cin >> dec_num;
dec_to_bin(dec_num, bin, count);
cout << "二進制值為：" << bin << endl;
return 0;
}
void dec_to_bin(int decNum, int& binDigit, int cnt)
{
if (decNum == 0) /* 遞迴終止條件 */
return;
else
{
cnt++; /* 權值遞加一 */
binDigit += (decNum % 2) * static_cast<int>(pow(10, cnt)); /* 累加找到的二進制位元值 */
/* 乘上 10 的該位元權值冪次，方便顯示 */
dec_to_bin(decNum / 2, binDigit, cnt);
}
}
範例程式三輸出
3. 運算式求值 (Expression Evaluation)
運算式在求值時，少不了會用到堆疊這一種資料結構的協助。運算式的表示法有前綴運算式 (prefix expressions)、中綴運算式 (infix expressions) 以及後綴運算式 (postfix expressions) 這三種。前綴運算式，其運算子 (operator) 在兩個運算元 (operand) 之前；中綴運算式，其運算子是在兩個運算元之間；後綴運算式，其運算子則是在兩個運算元之後。例如 X+Y 這一個簡單的運算式，X 與 Y 為運算元，+ 則是運算子，它就是屬於中綴運算式；若該運算式要轉換為前綴運算式，會變成 +XY；該運算式若要轉換為後綴運算式，則變成 XY+。
前綴運算式的求值
前綴運數式要求值，首先要先建立一個儲存運算元的堆疊，再將運算式由右至左逐一進行掃描式檢查。如果檢查到的字元是運算元，則將該運算元推入堆疊中；如果檢查到的字元是運算子，則將堆疊中最頂端的兩個運算元接連彈出，以執行運算。接著再將運算結果推入推疊，重複此流程直到堆疊只剩單一的元素為止，而此單一的元素即為運算的最終結果。例如下面的前綴運算式求值
/-914
如圖五所示，將運算式由右至左逐一檢查，先將 4 推入堆疊，再將 1 推入堆疊，接著將 9 推入堆疊。繼續往左檢查碰到運算子「-」後，將堆疊最頂端的兩個運算元 9 與 1 分別連續彈出，進行 9 - 1 結果為 8 的運算。再將此結果 8 推入堆疊。 繼續往左檢查，碰到運算子「/」後，將堆疊最頂端的兩個運算元 8 與 4 分別連續彈出，進行 8 / 4 結果為 2 的運算。2 再推入堆疊，堆疊只剩此單一的元素，2 即是最終的運算結果。
圖五 前綴運算式 /-914 的求值過程
中綴運算式的求值
中綴運算式例如 5 - 4*(3+2) + 1 雖然是符合人類習慣的一種運算式類型，但是對於編譯器而言它在編譯時相較其它類型運算式，就顯得複雜且困難得多。因為它必須注意到運算子的運算優先權 ( 例如先乘除後加減 ) 與結合性 ( 了解運算順序是否影響運算結果 ) ，以及刮號內的運算式部分擁有最高的運算優先權的運算規則。例如上面的中綴運算式 5 - 4*(3+2) + 1 求值，編譯器無論由左至右還是由右至左要先掃描一次，找到優先權最高的 (3+2) 運算後得到 5，再掃描一次找到優先權次高的 4*5 得到 20，最後再進行 5 - 20 + 1 的運算得到的結果為 -14。
由上述可知，中綴運算式的求值過程，常需要多次的掃描，非常沒有效率。因此一般編譯器會先將中綴運算式轉成較容易求值的前綴運算式或後綴運算式後，再利用堆疊以更有效率的方式來完成求值運算。
後綴運算式的求值
類似前綴運算式求值，不一樣的是必須將運算式由左至右逐一檢查。 如果檢查到的字元是運算元，則將該運算元推入堆疊中；如果檢查到的字元是運算子，則將堆疊中最頂端的兩個運算元彈出，以執行運算。 接著將運算結果推入推疊，重複此流程直到堆疊只剩單一的元素為止，而此單一的元素即為運算的最終結果。例如下面的後綴運算式求值
452*-3+
如圖六所示，將運算式由左至右逐一檢查，先將 4 推入堆疊，再將 5 推入堆疊，接著將 2 推入堆疊。繼續往右檢查碰到運算子「*」後，將堆疊最頂端的兩個運算元 2 與 5 分別連續彈出，進行 5 * 2 結果為 10 的運算。再將此結果 10 推入堆疊。 繼續往右檢查，碰到運算子「-」後，將堆疊最頂端的兩個運算元 10 與 4 分別連續彈出，進行 4 - 10 結果為 -6 的運算。 -6 再推入堆疊， 繼續往右檢查碰到運算元 3 後，將 3 推入堆疊。 繼續往右檢查，碰到運算子「+」後，將堆疊最頂端的兩個運算元 3 與 -6 分別連續彈出，進行 -6 +3 結果為 -3 的運算。最後將 -3 推入堆疊，堆疊只剩此單一的元素，-3 即是最終的運算結果。
圖六 後綴運算式 452*-3+ 求值
4. 運算式轉換 (Expression Conversion)
中綴運算式轉後綴運算式
中綴運算式要轉後綴運算式，要先建立一個儲存運算子的堆疊，以及一個儲存轉換結果的列表，再由左至右掃描中綴運算式，遇到運算元就直接輸出至結果列表；遇到運算子，判斷堆疊內的運算子的優先權是否小於該運算子。若不是，則先將堆疊內符合前述條件的運算子彈出加入結果列表，再將遇到運算子推入堆疊；否則直接將該運算子推入。如果遇到左括號，直接將左括號推入堆疊；遇到右括號，則將堆疊內左括號前的所有運算子彈出輸出至結果列表，再彈出左括號後將其捨棄。最後將堆疊內剩下的運算子全部彈出且輸出至結果列表。例如下面的中綴運算式要轉後綴運算式
(7 - 3) / 2 + (5 - 4) * 3 + 6
如圖七所示，從左至右開始掃描，先碰到左括號「 ( 」，將其推入堆疊。再來遇到運算元 7 ，將其輸出至結果列表，接著遇到運算子 「-」，將其推入堆疊。 接著遇到 3，輸出至結果列表。 再來碰到右括號「 ) 」，將堆疊內左括號「 ( 」前的運算子彈出並輸出至結果列表，左括號「 ( 」彈出捨棄。 繼續掃描，遇到「/」，將其推入堆疊。 接著遇到 2，輸出至結果列表，接著遇到運算子 「+」，將其推入堆疊。再來碰到左括號「 ( 」，將其推入堆疊，接著遇到 5，輸出至結果列表。 再下去遇到運算子 「-」，將其推入堆疊。 接下來遇到 4，輸出至結果列表。 繼續下去遇到右括號「 ) 」，將堆疊內左括號「 ( 」前的運算子彈出並輸出至結果列表，左括號「 ( 」彈出捨棄。 再過來遇到的是「*」，將其推入堆疊。 再過來是 3 ，輸出至結果列表。再繼續遇到了「+」，將其推入堆疊。最後會遇到 6 ，將其輸出至結果列表，此時堆疊剩下一運算元，再將此運算元輸出至結果列表，即完成轉換。 最後的結果為 73-2/54-3*+6+。
圖七 中綴運算式轉後綴運算式
5. 字串反轉 (String Reversal)
利用堆疊後進先出的特性，可輕易地將字串反轉。如下面的範例程式四所示：
範例程式四
#include <iostream>
#include <stack>
#include <string> /* 提供 string 類別，方便建立與操作字串 */
using namespace std;
string reverse_my_string(string& myStr);
int main()
{
string my_string = "abcdef";
cout << "my_string:" << my_string << endl;
cout << "my_reversed_string:" << reverse_my_string(my_string) << endl;
}
string reverse_my_string(string& myStr)
{
stack<char> my_stack;
string my_reversed_string = "";
int i;
for (i = 0; i < myStr.size(); i++)
my_stack.push(myStr[i]);
while (!my_stack.empty())
{
my_reversed_string += my_stack.top();
my_stack.pop();
}
return my_reversed_string;
}
範例程式四輸出
6. 復原 (Undo) 與重作 (Redo) 功能
程式執行動作的復原 ( 或回上一步 ) 與重作功能，可利用復原堆疊 (undo stack) 與重作堆疊 (redo stack) 來完成。 每當使用者在程式中執行一個動作，該動作相關的資訊就會被推入復原堆疊。 而當使用者按下復原按鈕，復原堆疊最頂端的動作紀錄就會彈出，並執行其逆轉動作，且該彈出的動作紀錄還會被推入重作堆疊。 而當使用者按下重作按鈕，重作堆疊最頂端的動作紀錄就會彈出並執行。
此外，瀏覽器的「上一頁」(back) 與「下一頁」(forward) 的功能也可以借助兩個堆疊來完成。 瀏覽器會建置一個上一頁堆疊 (back stack) ，用來存放已瀏覽過網頁的 URL，而目前正在瀏覽網頁的 URL 會是位於此堆疊的最頂端。 瀏覽器另外會再建置一個下一頁堆疊 (forward stack)，當使用者按下上一頁按鈕，瀏覽器會先將目前網頁的 URL 推入下一頁堆疊，再從上一頁堆疊中彈出 URL 並載入該 URL 的網頁。 而當使用者按下了下一頁按鈕，瀏覽器會先將目前網頁的 URL 推入上一頁堆疊，再將下一頁堆疊頂端的 URL 彈出並載入該 URL 的網頁。
7. 遞迴回溯法 (Recursive Backtracking)
遞迴回溯法是一種在解決問題的可能方法的組合中，逐一去嘗試，一旦發現行不通，就退回先前的可再接續另一種方法的點去嘗試，直到找到正確解為止的方法。以老鼠走迷宮為例：
圖八 迷宮
圖八所示為一迷宮，左上角為起點，右下角為終點，標示為 "0" 者為可通行，標示為 "1" 者則不可通行。迷宮的座標如圖九所示，回溯法的簡單樹狀圖則如圖十所示。
圖九 迷宮座標
圖十 回溯法的樹狀圖
留言
張貼留言