環形Queue問題

cynthialar

請問一下，要如何解決環形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

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

不過 full 跟 empty 條件都是 front == rare 的話會有點問題...
...

瀏覽完整內容，請先 註冊 或 登入會員

cynthialar

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

kwj

回復

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

cynthialar

自己模擬一次 cyclic queue 依序填值進去的狀況
就會發現 front+1 == rare 的話，front 指到的最後一格會填不到東西
（邏輯上其實 front +1 == rare 應該是在插入完以後才檢查
...

瀏覽完整內容，請先 註冊 或 登入會員