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

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

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

view plaincopy to clipboardprint?

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

view plaincopy to clipboardprint?

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. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

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
[佇列已空]

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