java數(shù)據(jù)結(jié)構(gòu)循環(huán)隊(duì)列的空滿判斷及長度計(jì)算

更新時(shí)間：2022年06月06日 10:08:03 作者：把蘋果咬哭的測試筆記

這篇文章主要為大家介紹了java數(shù)據(jù)結(jié)構(gòu)循環(huán)隊(duì)列的空滿判斷及長度計(jì)算，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

一、假溢出

這是因?yàn)閿?shù)組的末尾已經(jīng)被占用了，入隊(duì)會繼續(xù)在數(shù)組后面增加，于是產(chǎn)生數(shù)組越界。但是實(shí)際上，數(shù)組里是有空閑位置的，這種也可以叫“假溢出”。

為了解決“假溢出”的問題，于是乎有了循環(huán)隊(duì)列。

既然數(shù)組后面滿了，頭部有空，那繼續(xù)加進(jìn)來的元素從頭開始放即可。

接著上圖，這時(shí)候有a6入隊(duì)，于是rear的下標(biāo)指向a6的下一個(gè)元素位置，看起來沒什么問題。

但是繼續(xù)有新的元素a7入隊(duì)的時(shí)候，因?yàn)閒ront一直沒變，這時(shí)候rear指針跟front就重合了，也就是說此時(shí)front=rear。

可是在上一章的代碼里，我們是用front=rear來判斷是否為空數(shù)組的。

// 判斷隊(duì)列是否為空
    public boolean isEmpty() {
        return rear == front;
    }

現(xiàn)在是相等了，條件滿足，但是數(shù)組是滿的。

二、循環(huán)隊(duì)列判斷是空是滿

這種情況看起來確實(shí)比較辣手，那如果不讓這種情況出現(xiàn)不就可以了么？

假設(shè)，我們讓數(shù)組始終保留一個(gè)元素空間，也就是讓rear指向隊(duì)列中最后一個(gè)元素的后一個(gè)位置。比如，當(dāng)a6放入之后，此時(shí)就當(dāng)做隊(duì)列已經(jīng)滿了，這樣的話就不會出現(xiàn)上述的情況了。

為了實(shí)現(xiàn)這種思路，front也需要做調(diào)整。在上一章中，front初始位置是指在了隊(duì)頭元素的前一個(gè)，現(xiàn)在我們讓它就指在第一個(gè)元素。

隊(duì)列的最大尺寸還是maxSize，那么，現(xiàn)在判斷隊(duì)列滿的條件就可以是這樣：

(rear+1)%maxSize = front

驗(yàn)證一下，下面的2種隊(duì)列滿情況：

左圖：隊(duì)列中，maxSize=5，front=0，rear=4，判斷(4+1)% 5=0=front，隊(duì)列已滿

右圖：隊(duì)列中，maxSize=5，front=2，rear=1，判斷(1+1)% 5=2=front，隊(duì)列已滿

繼續(xù)驗(yàn)證一下，隊(duì)列沒滿的情況：

隊(duì)列中，maxSize=5，front=2，rear=0，判斷(0+1)% 5=1≠front，隊(duì)列未滿

三、循環(huán)隊(duì)列的長度計(jì)算

隊(duì)列的長度，也就是說隊(duì)列中實(shí)際存了多少個(gè)元素。

此時(shí)需要考慮rear與front之間的三種情況：

rear=front
rear>front
rear<front

第一種自然都清楚，隊(duì)列為空。

第二種，rear>front，此時(shí)隊(duì)列的長度為：rear-front

第三種，rear<front，比較復(fù)雜些。隊(duì)列長度分為2段：一段是maxSize-front，另一段則是：0+rear(結(jié)合右圖理解)。故此時(shí)隊(duì)列總長度為兩段相加：rear-front+maxSize

所以隊(duì)列長度的通用計(jì)算公式為：

(rear-front+maxSize)% maxSize

四、代碼實(shí)現(xiàn)

既然現(xiàn)在隊(duì)列是滿是空的判斷條件有了，隊(duì)列長度也能計(jì)算出來了，那么代碼就好改造了(基于上一章)，變成循環(huán)隊(duì)列。

package circle;
import java.util.Scanner;
public class CircleArrayQueue {
    public static void main(String[] args) {
        System.out.println("-----測試循環(huán)隊(duì)列-----");
        // 創(chuàng)建一個(gè)隊(duì)列
        CircleArray circleArray = new CircleArray(4);
        char key = ' '; //接受用戶輸入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 輸出一個(gè)菜單
        while (loop) {
            System.out.println("s(show): 顯示隊(duì)列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加數(shù)據(jù)到隊(duì)列");
            System.out.println("g(get): 從隊(duì)列取出數(shù)據(jù)");
            System.out.println("h(head): 顯示隊(duì)首的數(shù)據(jù)");
            key = scanner.next().charAt(0); // 接收一個(gè)字符
            switch (key) {
                case 's':
                    circleArray.showQueue();
                    break;
                case 'a':
                    System.out.println("請要添加的數(shù)");
                    int value = scanner.nextInt();
                    circleArray.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = circleArray.getQueue();
                        System.out.printf("取出的數(shù)據(jù)是：%d", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int headValue = circleArray.showHeadQueue();
                        System.out.printf("隊(duì)首數(shù)據(jù)是：%d", headValue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        System.out.println("退出程序");
    }
}
class CircleArray {
    //表示數(shù)組最大容量
    private int maxSize;
    // 隊(duì)列頭，由之前調(diào)整為指向隊(duì)列第一個(gè)元素
    private int front;
    // 隊(duì)列尾，由之前調(diào)整為指向隊(duì)列最后一個(gè)元素的后一個(gè)位置，為了空出一個(gè)元素位置
    private int rear;
    // 用于存放數(shù)據(jù)的數(shù)組
    private int[] arr;
    // 構(gòu)造器
    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }
    // 判斷隊(duì)列是否已經(jīng)存滿
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }
    // 判斷隊(duì)列是否為空
    public boolean isEmpty() {
        return rear == front;
    }
    // 添加數(shù)據(jù)到隊(duì)列
    public void addQueue(int num) {
        // 判斷隊(duì)列是否滿了
        if (isFull()) {
            System.out.println("隊(duì)列已滿，不可加入數(shù)據(jù)");
            return;
        }
        arr[rear] = num;
        // 將rear后移，要考慮取模
        rear = (rear + 1) % maxSize;
    }
    // 拿出隊(duì)列數(shù)據(jù)
    public int getQueue() {
        // 判斷隊(duì)列是否空
        if (isEmpty()) {
            // 拋出異常
            throw new RuntimeException("隊(duì)列為空，不可取數(shù)據(jù)");
        }
        int tempValue = arr[front];
        front = (front + 1) % maxSize; //也要考慮取模，防止front不停的增加，導(dǎo)致越界
        return tempValue;
    }
    // 顯示隊(duì)列所有數(shù)據(jù)
    public void showQueue() {
        // 遍歷
        if (isEmpty()) {
            System.out.println("隊(duì)列為空");
            return;
        }
        // 從front開始遍歷，遍歷多少個(gè)實(shí)際存的元素即可
        for (int i = front; i < front + CircleQueueSize(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }
    // 求出當(dāng)前隊(duì)列有效數(shù)據(jù)的個(gè)數(shù)
    public int CircleQueueSize() {
        return (rear - front + maxSize) % maxSize;
    }
    // 顯示隊(duì)里的隊(duì)首數(shù)據(jù)
    public int showHeadQueue() {
        if (isEmpty()) {
            // 拋出異常
            throw new RuntimeException("隊(duì)列為空，不可取數(shù)據(jù)");
        }
        return arr[front];
    }
}

重點(diǎn)的改動在于取模。

以上就是java數(shù)據(jù)結(jié)構(gòu)循環(huán)隊(duì)列的空滿判斷及長度計(jì)算的詳細(xì)內(nèi)容，更多關(guān)于java循環(huán)隊(duì)列空滿判斷長度計(jì)算的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: