佇列—環狀佇列概念與範例 - 筆記長也

佇列—環狀佇列概念與範例

2018-02-04 19:49:22   資料結構

環狀佇列

一般的佇列僅是單一的線性結構,若rear加入的資料已經達到最大值,即使front刪除資料,仍然會因rear已達到最大值而回傳佇列已滿,不符合實際情況,此時則使用環狀佇列解決問題。

環狀佇列的加入

環狀佇列範例(加入佇列)

        int max = 3;
        String[] q = new String[max];
        int rear = max-1;//Let rear and front 初始為max-1
        int front = max-1;
        if (inpu == 1) { //加入佇列
                rear=(rear+1) % max; //取得新的rear(%max是為了使rear循環)
                if (rear == front) { //佇列已滿
                    if(rear==0){
                        rear=max-1; //rear為0時,使rear回預設值
                    }
                    else{
                        rear--; //若rear非預設值,則退回上一個rear
                    }
                    System.out.println("佇列已經滿了");
                } else {
                    System.out.println("請輸入要加入的資料:");
                    String insertdata = input.next();
                    q[rear] = insertdata;

                }

執行結果

run:
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
ace
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
sawamura
<1>insert <2>del <3>print <4>exit
1
佇列已經滿了
<1>insert <2>del <3>print <4>exit
 
範例之中的max值為3,因此由上述範例可以明顯看出該環狀佇列僅放了2筆資料,而不是3筆資料。

由上圖所示,當我們分別在q[0]放入A,q[1]放入B,front在q[2]。當我們要再加入一筆資料至q[2]時,rear = 2  mod 3 =2,此時符合rear=front佇列已滿的條件,故無法再加入資料至q[2],明顯不符合實際情況。

若需使用q[2]這個空間,必須再加入一個條件來判斷佇列是否已滿,我們多宣告一個tag變數來輔助判斷。

環狀佇列範例(加入,使用tag判斷)

        int max = 3;
        String[] q = new String[max];
        int rear = max-1;//Let rear and front 初始為max-1
        int front = max-1;
        int tag=0;//輔助判斷,0:未滿,1:已滿            
        if (inpu == 1) { //加入佇列
                if (rear == front && tag==1) { //佇列已滿
                    if(rear==0){
                        rear=max-1; //rear為0時,使rear回預設值
                    }
                    else{
                        rear--; //若rear非預設值,則退回上一個rear
                    }
                    System.out.println("佇列已經滿了");
                } else {
                    System.out.println("請輸入要加入的資料:");
                    rear=(rear+1) % max; //取得新的rear(%max是為了使rear循環)
                    String insertdata = input.next();
                    q[rear] = insertdata;
                    
                    if(front==rear){
                        tag=1;//每次加入佇列之後,判斷是否已經滿了
                    }
                }
  
            }

執行結果

run:
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
Ace
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
is
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
I
<1>insert <2>del <3>print <4>exit
1
佇列已經滿了

上述範例可以看出加入了3筆資料,符合實際的情況。

但請注意並比較一下有無tag的時候,當要取得下一個rear時,若使用tag來輔助判斷,則需要將取得新的rear的工作放在else之中,若放在判斷式外面,會使rear在被判斷是否等於front之前就先被循環到下一個,這樣會導致資料被覆蓋。

環狀佇列的刪除

環狀佇列刪除範例

       else if (inpu == 2) {   /*刪除佇列*/
                if (front == rear) {
                    System.out.println("此佇列為空");
                } else {
                    front=(front+1) % max;
                    System.out.println(q[front] + " 已被刪除!");
                    q[front] = null;
                }

刪除很簡單,front就是負責替rear收拾殘局的,要跟在他後面刪除資料,當front與rear相等時,代表此佇列已經被清空了。取得下一個front的方式和上面新增rear的方式一樣,%max都是為了循環。

環狀佇列刪除範例(使用TAG)

         else if (inpu == 2) { //刪除佇列
                if (front == rear && tag==0) {
                    System.out.println("此佇列為空");
                } else {
                    front=(front+1) % max;
                    System.out.println(q[front] + " 已被刪除!");
                    q[front] = null;
                    if(front==rear){
                        tag=0;
                    }
                }

上方程式碼僅是加上TAG的判斷,當TAG==0時,代表佇列為空。

執行結果

run:
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
del
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
rice
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
ya
<1>insert <2>del <3>print <4>exit
2
del 已被刪除!
<1>insert <2>del <3>print <4>exit
2
rice 已被刪除!
<1>insert <2>del <3>print <4>exit
2
ya 已被刪除!
<1>insert <2>del <3>print <4>exit
2
此佇列為空

完整的環狀佇列(使用TAG)範例

public class CircularQueue {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int max = 3;
        String[] q = new String[max];
        int rear = max - 1;//Let rear and front 初始為max-1
        int front = max - 1;
        int tag = 0;//輔助判斷,0:未滿,1:已滿
        while (true) {
            System.out.println("<1>insert <2>del <3>print <4>exit");
            int inpu = input.nextInt();
            if (inpu == 1) { //加入佇列
                if (rear == front && tag == 1) { //佇列已滿
                    if (rear == 0) {
                        rear = max - 1; //rear為0時,使rear回預設值
                    } else {
                        rear--; //若rear非預設值,則退回上一個rear
                    }
                    System.out.println("佇列已經滿了");
                } else {
                    System.out.println("請輸入要加入的資料:");
                    rear = (rear + 1) % max; //取得新的rear(%max是為了使rear循環)
                    String insertdata = input.next();
                    q[rear] = insertdata;

                    if (front == rear) {
                        tag = 1;//每次加入佇列之後,判斷是否已經滿了
                    }
                }

            } else if (inpu == 2) { //刪除佇列
                if (front == rear && tag == 0) {
                    System.out.println("此佇列為空");
                } else {
                    front = (front + 1) % max;
                    System.out.println(q[front] + " 已被刪除!");
                    q[front] = null;
                    if (front == rear) {
                        tag = 0;
                    }
                }

            } else if (inpu == 3) { //顯示佇列
                if (rear == front && tag == 0) {
                    System.out.println("此佇列為空!");
                } else {
                    for (int i = 0; i < max; i++) {
                        if (q[i] != null) {
                            System.out.println(q[i]);
                        }
                    }

                }

            } else if (inpu == 4) { //退出迴圈
                break;
            }
        }
    }
}

執行結果

run:
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
h
<1>insert <2>del <3>print <4>exit
3
h
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
g
<1>insert <2>del <3>print <4>exit
3
h
g
<1>insert <2>del <3>print <4>exit
1
請輸入要加入的資料:
f
<1>insert <2>del <3>print <4>exit
3
h
g
f
<1>insert <2>del <3>print <4>exit
2
h 已被刪除!
<1>insert <2>del <3>print <4>exit
3
g
f
<1>insert <2>del <3>print <4>exit
2
g 已被刪除!
<1>insert <2>del <3>print <4>exit
2
f 已被刪除!
<1>insert <2>del <3>print <4>exit
3
此佇列為空!

總結

1.各位應該有發現只有兩種情況時,會使rear=front:(1)佇列已滿     (2)佇列為空

2.TAG變數的加入與否,完全看需求。加入TAG是為了使空間使用效率更高,不浪費任何一個空間,若未加入TAG理論上則可以增加程式執行效率

 

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)