伊莉討論區

標題: 環形Queue問題 [打印本頁]

---

作者: cynthialar    時間: 2011-10-18 11:13 PM     標題: 環形Queue問題



請問一下，要如何解決環形Queue的一個空白位置處理?也就是說如果我的陣列大小是5個，但是因為環形Queue的關係，所以會有一格是沒存進去的，且會顯示滿的，我的code如下：                                                                                       

1. class homeworkqueue{
   
2.         public static void main(String[] args){
   
3.                 queue testnumber = new queue();
   
4.                 testnumber.enqueue(30);
   
5.                 testnumber.enqueue(50);
   
6.                 testnumber.enqueue(40);
   
7.                 testnumber.enqueue(10);
   
8.                 testnumber.enqueue(20);
   
9.                 //testnumber.enqueue(100);
   
10.                 for(int i = 0; i < 5; i++)
    
11.                         System.out.println(testnumber.dequeue());
    
12.         }
    
13. }
    
14. class queue{
    
15.         public int[] number = new int[5];
    
16.         public int f = 0;        //head
    
17.         public int r = 0;        //tail
    
18.         public void enqueue(int num){
    
19.                 if(is_full() == true){
    
20.                         System.out.println("It's full!!");
    
21.                 }
    
22.                 else{
    
23.                         number[f] = num;
    
24.                         f = (f + 1) % 5;
    
25.                 }
    
26.         }
    
27.         public boolean is_full(){
    
28.                 if((f + 1) % 5 == r)
    
29.                         return true;
    
30.                 else
    
31.                         return false;
    
32.         }
    
33.         public int dequeue(){
    
34.                 if(is_empty() == true){
    
35.                         System.out.print("It's empty!!   ");
    
36.                         return -1;
    
37.                 }
    
38.                 else{
    
39.                         int tmp = number[r];
    
40.                         r = (r + 1) % 5;
    
41.                         return tmp;
    
42.                 }
    
43.         }
    
44.         public boolean is_empty(){
    
45.                 if(r == f)
    
46.                         return true;
    
47.                 else
    
48.                         return false;
    
49.         }
    
50. }

複製代碼

我想過很多方法了，但是就是一直寫不出來，請問各位要如何去寫呢? 謝謝

---

作者: kwj    時間: 2011-10-19 12:32 AM



front 指的是空的格子，也就是下一個要填入的值要放的位置
但是 rare 指的是已填資料的格子，兩個變數的定義不太一樣
所以這種狀況下 front 前進時應該是要剛好跟 rare 指到同一格時才會是 full
（因為 front+1 = rare 的話，front 此時會指的格子是空的格子，因此會出現有一格一直填不到）

不過 full 跟 empty 條件都是 front == rare 的話會有點問題...
所以可以再加上一個 flag 標註現在是 full 狀態的 front == rare，還是 empty 狀態的 front == rare
參考的程式碼如下：

1. public class queue {
   
2.         private int[] number = new int[5];
   
3.         private int f = 0;
   
4.         private int r = 0;
   
5.         private int flag = 0; // default is empty
   
6. 
   
7.         public boolean enqueue(int num) {
   
8.                 boolean success = false;
   
9.                 if (is_full())
   
10.                         System.out.println("It's full!!");
    
11.                 else {
    
12.                         number[f] = num;
    
13.                         System.out.println("enqueue: " + num + " at index " + f);
    
14.                         f = (f + 1) % 5;
    
15.                         success = true;
    
16.                         if(r == f) flag = 1;
    
17.                 }
    
18.                 return success;
    
19.         }
    
20. 
    
21.         public boolean is_full() {
    
22.                 if (flag == 1 && r == f) return true;
    
23.                 else return false;
    
24.         }
    
25. 
    
26.         public int dequeue() {
    
27.                 int tmp = -1;
    
28.                 if (is_empty())
    
29.                         System.out.print("It's empty!!");
    
30.                 else {
    
31.                         tmp = number[r];
    
32.                         r = (r + 1) % 5;
    
33.                         if(r == f) flag = 0;
    
34.                 }
    
35.                 return tmp;
    
36.         }
    
37. 
    
38.         public boolean is_empty() {
    
39.                 if (flag == 0 && r == f) return true;
    
40.                 else return false;
    
41.         }
    
42. }

複製代碼

---

作者: cynthialar    時間: 2011-10-19 01:33 AM

恩恩，謝謝大哥的教導~
我再想一想您的程式邏輯~
想在問您一下，您是怎麼想到的呢??~
如何想到有這種方法??~
我想了很久都想不到，想了很多方法，轉換成程式，執行出來的東西都不如預期~
請問大哥您是如何去思考的呢??~
謝謝您~

---

作者: kwj    時間: 2011-10-19 07:51 AM



回復 3# cynthialar

自己模擬一次 cyclic queue 依序填值進去的狀況
就會發現 front+1 == rare 的話，front 指到的最後一格會填不到東西
（邏輯上其實 front +1 == rare 應該是在插入完以後才檢查
　他檢查的是下一次有沒有空間插入，而不是現在有沒有空間插入
　因為 front 指的是空的格子～而不是滿的格子）
所以應該要檢查 front == rare 才對
但如果 full 跟 empty 條件相同的話，當條件觸發時我根本沒辦法判斷現在到底是 full 還是 empty....
如果不判斷的話，初始的 empty 狀況會被誤判成 full，cyclic queue 根本沒辦法開始運作
所以就想辦法知道要怎麼判斷囉！
那首先會先注意到的是：
1. 只有在 enqueue 時需要判斷 full 的狀況
2. 只有在 dequeue 時需要判斷 empty 的狀況
那麼最簡單的處理方法就是 enqueue 時插入資料完以後檢查一下現在條件滿足了沒
滿足了這時就會是 full，因為 enqueue 不可能造成 empty～
就加個 flag 記錄一下現在 full 觸發了
而 dequeue 則是丟資料出來時檢查條件滿足了沒
沒有滿足的話就會是 empty，把 flag 記錄成 empty 觸發～

---

歡迎光臨 伊莉討論區 (http://godaddy01.mobile.wahas.com/)

Powered by Discuz!