程式扎記: [ 資料結構 小學堂 ] 佇列 : 佇列的應用 (雙向佇列)

標籤

2010年10月6日 星期三

[ 資料結構 小學堂 ] 佇列 : 佇列的應用 (雙向佇列)

前言 : 
雙向佇列 (Deques) 是英文名稱 (Double-ends Queues) 的縮寫, 雙向佇列就是一種前後兩端都可以輸入或取出資料的有序串列. 更詳細請參考以下範例代碼 : 

範例代碼 : 
這裡以鏈結串列來實現雙向佇列. 
* JQueueInLS.h 代碼 : 

  1. #include   
  2. #include   
  3.   
  4. using namespace std;  
  5.   
  6. struct QueueData{  
  7.     int data;  
  8.     struct QueueData *next;  
  9. };  
  10.   
  11. typedef struct QueueData QueueNode;  
  12. typedef QueueNode *QueueByLinkedList;  
  13.   
  14. class JQueueInLS{  
  15.     int maxSize;  
  16.     QueueByLinkedList front;  
  17.     QueueByLinkedList rear;  
  18. public:  
  19.     JQueueInLS(int size){  
  20.         front = NULL;  
  21.         rear = NULL;  
  22.         maxSize = size;  
  23.     }  
  24.     JQueueInLS(){  
  25.         front = NULL;  
  26.         rear = NULL;  
  27.         maxSize = 20;  
  28.     }  
  29.     ~JQueueInLS(){  
  30.         while(front != NULL) {  
  31.             QueueByLinkedList tmpList = front;  
  32.             front = front->next;  
  33.             delete tmpList;  
  34.         }  
  35.     }  
  36.   
  37.     bool add(int val);  // 添加新資料到佇列  
  38.     bool isEmpty();  //判斷佇列是否為空  
  39.     bool isFull();  // 判斷佇列是否已滿  
  40.     bool get(int *val); // 取回佇列的值  
  41.     int length(); // 目前佇列的資料數量.  
  42.     int dequeue(int action); //action=1 : 從前端取資料, action=2 : 從後端取資料  
  43. };  
* JQueueInLS.cpp 代碼 : 

  1. #include "JQueueInLS.h"  
  2.   
  3. bool JQueueInLS::add(int val) {  
  4.     if(!isFull()) {  
  5.         if(rear == NULL) {  
  6.             rear = new QueueNode;  
  7.         } else {  
  8.             rear->next = new QueueNode;  
  9.             rear = rear->next;  
  10.         }  
  11.         rear->data = val;  
  12.         if(this->front == NULL) {          
  13.             front = rear;         
  14.         }   
  15.         rear->next = NULL;  
  16.         return true;  
  17.     } else {  
  18.         cout << "[佇列已滿]" << endl;  
  19.     }  
  20.     return false;  
  21. }  
  22.   
  23. bool JQueueInLS::get(int *val) {  
  24.     if(!this->isEmpty()) {  
  25.         *val = front->data;  
  26.         QueueByLinkedList tmpList = front;  
  27.         front = front->next;  
  28.         delete tmpList;  
  29.         return true;  
  30.     } else {  
  31.         *val = -1;  
  32.         cout << "[佇列為空]" << endl;  
  33.     }  
  34.     return false;  
  35. }  
  36.   
  37. bool JQueueInLS::isEmpty(){  
  38.     if(front == NULL) {  
  39.         return true;  
  40.     }  
  41.     return false;  
  42. }  
  43.   
  44. bool JQueueInLS::isFull(){  
  45.     if(this->length() >= this->maxSize) {  
  46.         return true;  
  47.     } else {  
  48.         return false;  
  49.     }  
  50. }  
  51.   
  52. int JQueueInLS::length() {  
  53.     if(this->front != NULL) {  
  54.         QueueByLinkedList tmpPoint = front;  
  55.         int size = 0;  
  56.         while(tmpPoint != NULL) {  
  57.             size++;  
  58.             tmpPoint = tmpPoint->next;  
  59.         }  
  60.         return size;  
  61.     } else {  
  62.         return 0;  
  63.     }  
  64. }  
  65.   
  66. int JQueueInLS::dequeue(int action) {  
  67.     if(action == 1) { // 從前端取資料  
  68.         int tmp = -1;  
  69.          this->get(&tmp);  
  70.         return tmp;  
  71.     } else if(action == 2) { //從後端取資料  
  72.         if(!this->isEmpty()) {  
  73.             int val = rear->data;  
  74.             if(rear == front) {  
  75.                 delete rear;  
  76.                 rear = NULL;  
  77.                 front = NULL;  
  78.             } else {  
  79.                 QueueByLinkedList tmpPoint = front;  
  80.                 while(tmpPoint->next != rear) {  
  81.                     tmpPoint = tmpPoint->next;  
  82.                 }  
  83.                 delete rear;  
  84.                 rear = tmpPoint;  
  85.                 tmpPoint->next = NULL;  
  86.             }  
  87.             return val;  
  88.         } else {  
  89.             cout << "[佇列已空]" << endl;             
  90.         }  
  91.     } else { // 不合法 action  
  92.         cout << "[Illegal Action]" << endl;  
  93.     }  
  94.     return -1;  
  95. }  
* 呼叫演算法代碼 : 

  1. void ch05_04(bool b) {  
  2.     if(b) {  
  3.         char ch = 'S';  
  4.         int val;  
  5.         int gval=-1;  
  6.         JQueueInLS queue;  
  7.         while(ch != 'E') {  
  8.             cout << "[A]存入一個數值, [F] 從前端取出資料, [B]從後端取出資料, [E] 結束, [L] 目前佇列長度 :";  
  9.             cin >> ch;  
  10.             switch(ch) {  
  11.                 case 'A':  
  12.                     cout << "請輸入數值: ";  
  13.                     cin >> val;  
  14.                     queue.add(val);  
  15.                     break;  
  16.                 case 'F':  
  17.                     gval = queue.dequeue(1);  
  18.                     if(gval>=0) {  
  19.                         cout << "取出數值為: " << gval << endl;  
  20.                     }  
  21.                     break;  
  22.                 case 'B':  
  23.                     gval = queue.dequeue(2);  
  24.                     if(gval>=0) {  
  25.                         cout << "取出數值為: " << gval << endl;  
  26.                     }  
  27.                     break;  
  28.                 case 'E':  
  29.                     cout << "[離開程式]" << endl;  
  30.                     break;  
  31.                 case 'L':  
  32.                     cout << "目前佇列資料數目為: " << queue.length() << endl;  
  33.                     break;  
  34.                 default:  
  35.                     cout << "不合法字元! (" << ch << ")"  << endl;  
  36.                     break;  
  37.             }  
  38.         }  
  39.     }  
  40. }  


執行結果 : 

[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :A
請輸入數值: 1
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :A
請輸入數值: 2
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :A
請輸入數值: 3
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :A
請輸入數值: 4
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :A
請輸入數值: 5
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :F
取出數值為: 1
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :B
取出數值為: 5
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :F
取出數值為: 2
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :B
取出數值為: 4
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :F
取出數值為: 3
[A]存入一個數值, [F] 從前端取出資料, [B ]從後端取出資料, [E] 結束, [L] 目前佇列長度 :B
[佇列已空]


補充說明 : 
* [ 資料結構 小學堂 ] 佇列 : 認識佇列

沒有留言:

張貼留言

網誌存檔

關於我自己

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