[ 資料結構 小學堂 ] 堆疊 : 認識堆疊

前言 : 
堆疊(Stack) 是一群相同資料型態的組合, 所有動作均在堆疊頂端進行, 具 "後進先出" (Last in, Fisrt Out, LIFO) 特性. 堆疊結構在電腦中的應用相當廣泛, 時常被用來解決電腦的問題, 例如前面所談到的遞回呼叫, 副程式的呼叫. 至於日常生活中的應用也隨處可以看到, 例如大樓電梯, 貨架上的貨品等等, 都是類似堆疊的資料結構原理. 

認識堆疊 : 
談到所謂後進先出 (Last In, First Out) 的觀念, 其實就是如同自助餐中的餐盤由桌面往上一個個疊放, 用時則由最上面先拿, 這就是一種典型的堆疊的應用. 由於堆疊是一種抽象型資料結構, 它有以下特性 : 

1. 只能從堆疊的頂端存取資料.
2. 資料的存取符合 "後進先出" 的原則. (LIFO)

至於堆疊的操作與基本運算具備以下五種工作定義 : 
* CREATE : 建立一個空堆疊 
* PUSH : 存放頂端資料, 並回傳新堆疊. 
* POP : 刪除頂端資料, 並回傳新堆疊. 
* EMPTY : 判斷堆疊是否為空堆疊, 是則返回true, 不是則返回 false 
* FULL : 判斷堆疊是否已滿, 是則返回 true, 不是則返回 false. 

基本上堆疊本身可以使用靜態陣列結構或動態鏈結串列結構來實作, 只要維持堆疊後進先出與從頂端讀取資料的兩個基本原則即可. 以陣列結構來製作堆疊的好處是製作與設計的演算法都相當簡單, 底下將以陣列來作範例介紹 : 

範例代碼 : 
* JStack.h 代碼 : 

view plaincopy to clipboardprint?

1. #include   
2. #define MAXSTACK 100 // 定義最大堆疊量  
3. using namespace std;  
4.   
5. class JStack{  
6. protected:  
7.     int *stack;  
8.     int top;  
9.   
10. public:  
11.     JStack(){  
12.         top = -1;  
13.         stack = new int[MAXSTACK];  
14.     }  
15.     ~JStack(){  
16.         delete stack;  
17.     }  
18.     virtual int isEmpty();  
19.     virtual int isFull();  
20.     virtual int push(int data);  
21.     virtual int pop();  
22. };  

* JStack.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "JStack.h"  
2.   
3. int JStack::isEmpty(){  
4.     if(top==-1) return 1;  
5.     else return 0;  
6. }  
7.   
8. int JStack::isFull(){  
9.     if(top>=MAXSTACK) return 1;  
10.     else return 0;  
11. }  
12.   
13. int JStack::push(int data){  
14.     if(isFull()) {  
15.         cout << "[堆疊已滿, 無法再加入!]" << endl;  
16.         return 0;  
17.     }else {  
18.         stack[++top] = data;  
19.         return 1;  
20.     }  
21. }  
22.   
23. int JStack::pop(){  
24.     if(isEmpty()) {  
25.         return -1;  
26.     } else {  
27.         return stack[top--];  
28.     }  
29. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch04_01(bool b){  
2.     if(b) {  
3.         int value;        
4.         JStack stack;  
5.         cout << "請依序輸入十筆資料:" << endl;  
6.         for(int i=0; i<10; i++){  
7.             cin >> value;  
8.             stack.push(value);  
9.         }  
10.         cout << "===========================" << endl;  
11.         while(!stack.isEmpty()) {  
12.             cout << "堆疊彈出順序為: " << stack.pop() << endl;             
13.         }  
14.         cout << "===========================" << endl;        
15.     }  
16. }  

執行結果 : 

請依序輸入十筆資料:
1
2
3
4
5
6
7
8
9
10
===========================
堆疊彈出順序為: 10
堆疊彈出順序為: 9
堆疊彈出順序為: 8
堆疊彈出順序為: 7
堆疊彈出順序為: 6
堆疊彈出順序為: 5
堆疊彈出順序為: 4
堆疊彈出順序為: 3
堆疊彈出順序為: 2
堆疊彈出順序為: 1 <滿足後進先出>
===========================

補充說明 : 
* [ 資料結構 小學堂 ] 鏈結串列 : 單向鏈結串列 
* [ 資料結構 小學堂 ] 陣列結構 : 矩陣的簡介與運算