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

前言 : 
在之前以陣列實作佇列時, 如果要排除取出資料時卻要移動所有其他的資料時所造成加深演算法複雜度與運算時間的問題時, 則環狀佇列則可以解決前面的問題. 

環狀佇列 : 
基本上環狀佇列就是一種環型結構的佇列, 它是以一種 Q(0:n-1) 的一維陣列, 同時Q(0) 為 Q(n-1) 的下一個元素. 這裡指標 front 永遠在佇列的第一個元素順時鐘方向移動的第一個位置. rear 則指向佇列目前的最後位置. 一開始 front 與 rear 均預設為 -1, 表示為空佇列, 也就是說如果 front = rear 則為空佇列. 另外考慮佇列最大長度為 MaxSize 則: 

* 佇列長度 :
- if front > rear 則 length = MaxSize - (front - rear)
- if rear > front 則 length = rear - front
- if rear = front 則 length = 0

上述之所以將 front 指向佇列的第一個元素前一個位置, 原因是環狀佇列為空佇列與滿佇列時, front 和 rear 都會指向同一個地方, 如此一來我們便無法利用 front 是否等於 rear 這個判斷式來決定到底目前是空佇列或滿佇列. 
為了解決此問題, 除了上述方式僅允許佇列最多只能存放 MaxSize-1 個資料 (亦即犧牲最後一個空間), 當 rear 指標的下一個位置是 front 的位置時, 就認定佇列已滿, 來判斷是否能夠加入資料進佇列, 底下是佇列的圖示運算過程 : 
 

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

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. #define JQueueInCircle_MaxSize 5  
6.   
7. class JQueueInCircle{  
8.     int queue[JQueueInCircle_MaxSize];  
9.     int front, rear;  
10. public:  
11.     JQueueInCircle(){  
12.         front = -1;  
13.         rear = -1;  
14.     }  
15.     bool add(int val);  // 添加新資料到佇列  
16.     bool isEmpty();  //判斷佇列是否為空  
17.     bool isFull();  // 判斷佇列是否已滿  
18.     bool get(int *val); // 取回佇列的值  
19.     int length(); // 目前佇列的資料數量.  
20.   
21. protected:  
22.     void _increaseRear();  
23. };  

* JQueueInCircle.cpp 代碼 : 

view plaincopy to clipboardprint?

1. #include "JQueueInCircle.h"  
2.   
3. bool JQueueInCircle::isEmpty() {  
4.     if(rear == front) {  
5.         return true;  
6.     } else {  
7.         return false;  
8.     }  
9. }  
10.   
11. bool JQueueInCircle::isFull(){  
12.     if((rear == (JQueueInCircle_MaxSize-1) && front==0 ) || (rear+1)==front) {  
13.         return true;  
14.     } else {  
15.         return false;  
16.     }  
17. }  
18.   
19. int JQueueInCircle::length() {  
20.     if(rear > front) {  
21.         return rear - front;  
22.     } else if(rear < front) {  
23.         return JQueueInCircle_MaxSize - front + rear;  
24.     } else {  
25.         return 0;  
26.     }  
27. }  
28.   
29. void JQueueInCircle::_increaseRear(){  
30.     if(rear==(JQueueInCircle_MaxSize-1)) {  
31.         rear = 0;  
32.     } else {  
33.         rear++;  
34.     }  
35. }  
36.   
37. bool JQueueInCircle::add(int val) {  
38.     if(!this->isFull()) {  
39.          _increaseRear();  
40.          queue[rear] = val;  
41.         return true;  
42.     } else {  
43.         cout << "[佇列已滿]" << endl;  
44.     }  
45.     return false;  
46. }  
47.   
48. bool JQueueInCircle::get(int *val) {  
49.     if(!isEmpty()) {  
50.         *val = queue[++front];  
51.         return true;  
52.     } else {  
53.         *val = -1;  
54.         cout << "[佇列為空]" << endl;  
55.     }  
56.     return false;  
57. }  

* 呼叫演算法代碼 : 

view plaincopy to clipboardprint?

1. void ch05_03(bool b) {  
2.     if(b) {  
3.         int choice=0, gval=-1;  
4.         JQueueInCircle queue;  
5.         while(choice!=-1) {  
6.             cout << "請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): " ;  
7.             cin >> choice;  
8.             switch(choice) {  
9.                 case -2: // 取出佇列值  
10.                     queue.get(&gval);  
11.                     if(gval>=0) {  
12.                         cout << "取出佇列值: " << gval << endl;  
13.                     }  
14.                     break;  
15.                 case -1:  
16.                     cout << "[離開程式!]" << endl;  
17.                     break;  
18.                 default: //Save into queue                    
19.                     queue.add(choice);  
20.                     cout << "[目前佇列長度為:" << queue.length() << "]" << endl;  
21.             }  
22.         }  
23.     }  
24. }  

執行結果 : 

請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): 1
[目前佇列長度為:1]
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): 2
[目前佇列長度為:2]
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): 3
[目前佇列長度為:3]
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): -2
取出佇列值: 1
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): 4
[目前佇列長度為:3]
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): 5
[目前佇列長度為:4]
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): -2
取出佇列值: 2
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): -2
取出佇列值: 3
請輸入一個值以存入佇列, 欲取出請輸入-2 (結束輸入-1): -1
[離開程式!]