程式扎記: [ 資料結構 小學堂 ] 堆疊 : 認識堆疊

標籤

2010年9月23日 星期四

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

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

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

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

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

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

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

  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 代碼 : 

  1. #include "JStack.h"  
  2.   
  3. int JStack::isEmpty(){  
  4.     if(top==-1return 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. }  
* 呼叫演算法代碼 : 

  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 <滿足後進先出>
===========================


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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!