91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Java循環隊列的案例分析

發布時間:2020-10-29 11:13:33 來源:億速云 閱讀:123 作者:小新 欄目:編程語言

Java循環隊列的案例分析?這個問題可能是我們日常學習或工作經常見到的。希望通過這個問題能讓你收獲頗深。下面是小編給大家帶來的參考內容,讓我們一起來看看吧!

思路分析圖解

啰嗦一下,由于筆者不太會弄貼出來的圖片帶有動畫效果,比如元素的移動或者刪除(畢竟這樣看大家比較直觀),筆者在這里只能通過靜態圖片的方式,幫助大家理解實現原理,希望大家不要見怪,如果有朋友知道如何搞的話,歡迎在評論區慧言。

在這里,我們聲明了一個容量大小為8的數組,并標出了索引0-7,然后使用fronttail分別來表示隊列的,隊首和隊尾;在下圖中,fronttail的位置一開始都指向是了索引0的位置,這意味著當front == tai的時候 <font color = 'red'>隊列為空</font> 大家務必牢記這一點,以便區分后面介紹隊列快滿時的臨界條件

Java循環隊列的案例分析

為了大家更好地理解下面的內容,在這里,我簡單做幾點說明

front:表示隊列隊首,始終指向隊列中的第一個元素(當隊列空時,front指向索引為0的位置)

tail:表示隊列隊尾,始終指向隊列中的最后一個元素的下一個位置

元素入隊,維護tail的位置,進行tail++操作

元素出隊,維護front的位置,進行front++操作上面所說的,元素進行入隊和出隊操作,都簡單的進行++操作,來維護tailfront的位置,其實是不嚴謹的,正確的維護tail的位置應該是(tail + 1) % capacity,同理front的位置應該是(front + 1) % capacity,這也是為什么叫做循環隊列的原因,大家先在這里知道下,暫時不理解也沒關系,后面相信大家會知曉。

下面我們看一下,現在如果有一個元素a入隊,現在的示意圖:

Java循環隊列的案例分析

我們現在看到了元素a入隊,我們的tail指向的位置發生了變化,進行了++操作,而front的位置,沒有發生改變,仍舊指向索引為0的位置,還記得筆者上面所說的,front的位置,始終指向隊列中的第一個元素,tail的位置,始終指向隊列中的最后一個元素的下一個位置

現在,我們再來幾個元素b、c、d、e進行入隊操作,看一下此時的示意圖:

Java循環隊列的案例分析

想必大家都能知曉示意圖是這樣,好像沒什么太多的變化(還請大家別著急,筆者這也是方便大家理解到底是什么循環隊列,還請大家原諒我O(∩_∩)O哈!)

看完了元素的入隊的操作情況,那現在我們看一下,元素的出隊操作是什么樣的?

元素a出隊,示意圖如下:

Java循環隊列的案例分析

現在元素a已經出隊,front的位置指向了索引為1的位置,現在數組中所有的元素不再需要往前挪動一個位置

這一點和我們的數組隊列(我們的數組隊列需要元素出隊,后面的元素都要往前挪動一個位置)完全不同,我們只需要改變一下front的指向就可以了,由之前的O(n)操作,變成了O(1)的操作

我們再次進行元素b出隊,示意圖如下:

Java循環隊列的案例分析

到這里,可能有的小伙伴會問,為什么叫做,循環隊列?那么現在我們嘗試一下,我們讓元素f、g分別進行入隊操作,此時的示意圖如下:

Java循環隊列的案例分析

大家目測看下來還是沒什么變化,如果此時,我們再讓一個元素h元素進行入隊操作,那么問題來了我們的tail的位置該如何指向呢?示意圖如下:

Java循環隊列的案例分析

根據我們之前說的,元素入隊:維護tail的位置,進行tail++操作,而此時我們的tail已經指向了索引為7的位置,如果我們此時對tail進行++操作,顯然不可能(數組越界)

細心的小伙伴,會發現此時我們的隊列并沒有滿,還剩兩個位置(這是因為我們元素出隊后,當前的空間,沒有被后面的元素擠掉),大家可以把我們的數組想象成一個環狀,那么索引7之后的位置就是索引0

如何才能從索引7的位置計算到索引0的位置,之前我們一直說進行tail++操作,筆者也在開頭指出了,這是不嚴謹的,應該的是(tail + 1) % capacity這樣就變成了(7 + 1) % 8等于 0

所以此時如果讓元素h入隊,那么我們的tail就指向了索引為0的位置,示意圖如下:

Java循環隊列的案例分析

假設現在又有新的元素k入隊了,那么tail的位置等于(tail + 1) % capacity 也就是(0 + 1)% 8 等于1就指向了索引為1的位置

Java循環隊列的案例分析

那么問題來了,我們的循環隊列還能不能在進行元素入隊呢?我們來分析一下,從圖中顯示,我們還有一個索引為0的空的空間位置,也就是此時tail指向的位置

按照之前的邏輯,假設現在能放入一個新元素,我們的tail進行(tail +1) % capacity計算結果為2(如果元素成功入隊,此時隊列已經滿了),此時我們會發現表示隊首的front也指向了索引為2的位置

如果新元素成功入隊的話,我們的tail也等于2,那么此時就成了 tail == front ,一開始我們提到過,當隊列為空的tail == front,現在呢,如果隊列為滿時tail也等于front,那么我們就無法區分,隊列為滿時和隊列為空時收的情況了

所以,在循環隊列中,我們總是浪費一個空間,來區分隊列為滿時和隊列為空時的情況,也就是當  ( tail + 1 ) % capacity == front的時候,表示隊列已經滿了,當front == tail的時候,表示隊列為空。

Java循環隊列的案例分析

了解了循環隊列的實現原理之后,下面我們用代碼實現一下。

代碼實現

接口定義 :Queue<E>

public interface Queue<E> {
    /**
     * 入隊
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出隊
     *
     * @return
     */
    E dequeue();

    /**
     * 獲取隊首元素
     *
     * @return
     */
    E getFront();

    /**
     * 獲取隊列中元素的個數
     *
     * @return
     */
    int getSize();

    /**
     * 判斷隊列是否為空
     *
     * @return
     */
    boolean isEmpty();
}

接口實現:LoopQueue<E>

public class LoopQueue<E> implements Queue<E> {
    /**
     * 承載隊列元素的數組
     */
    private E[] data;
    /**
     * 隊首的位置
     */
    private int front;
    /**
     * 隊尾的位置
     */
    private int tail;
    /**
     * 隊列中元素的個數
     */
    private int size;

    /**
     * 指定容量,初始化隊列大小
     * (由于循環隊列需要浪費一個空間,所以我們初始化隊列的時候,要將用戶傳入的容量加1)
     *
     * @param capacity
     */
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
    }

    /**
     * 模式容量,初始化隊列大小
     */
    public LoopQueue() {
        this(10);
    }


    @Override
    public void enqueue(E e) {
        // 檢查隊列為滿
        if ((tail + 1) % data.length == front) {
            // 隊列擴容
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }


    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊列為空");
        }
        // 出隊元素
        E element = data[front];
        // 元素出隊后,將空間置為null
        data[front] = null;
        // 維護front的索引位置(循環隊列)
        front = (front + 1) % data.length;
        // 維護size大小
        size--;

        // 元素出隊后,可以指定條件,進行縮容
        if (size == getCapacity() / 2 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return element;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("隊列為空");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }


    // 隊列快滿時,隊列擴容;元素出隊操作,指定條件可以進行縮容
    private void resize(int newCapacity) {
        // 這里的加1還是因為循環隊列我們在實際使用的過程中要浪費一個空間
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // 注意這里的寫法:因為在數組中,front 可能不是在索引為0的位置,相對于i有一個偏移量
            newData[i] = data[(i + front) % data.length];
        }
        // 將新的數組引用賦予原數組的指向
        data = newData;
        // 充值front的位置(front總是指向隊列中第一個元素)
        front = 0;
        // size 的大小不變,因為在這過程中,沒有元素入隊和出隊
        tail = size;
    }


    private int getCapacity() {
        // 注意:在初始化隊列的時候,我們有意識的為隊列加了一個空間,那么它的實際容量自然要減1
        return data.length - 1;
    }

    @Override
    public String toString() {
        return "LoopQueue{" +
                "【隊首】data=" + Arrays.toString(data) + "【隊尾】" +
                ", front=" + front +
                ", tail=" + tail +
                ", size=" + size +
                ", capacity=" + getCapacity() +
                '}';
    }
}

測試類:LoopQueueTest

public class LoopQueueTest {
    @Test
    public void testLoopQueue() {
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            loopQueue.enqueue(i);
        }
        // 初始化隊列數據
        System.out.println("原始隊列: " + loopQueue);
        // 元素0出隊
        loopQueue.dequeue();
        System.out.println("元素0出隊: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素1出隊: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素2出隊: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素3出隊: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素4出隊,發生縮容: " + loopQueue);
        // 隊首元素
        System.out.println("隊首元素:" + loopQueue.getFront());
    }
}
測試結果:
原始隊列: LoopQueue{【隊首】data=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【隊尾】, front=0, tail=10, size=10, capacity=10}
元素0出隊: LoopQueue{【隊首】data=[null, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【隊尾】, front=1, tail=10, size=9, capacity=10}
元素1出隊: LoopQueue{【隊首】data=[null, null, 2, 3, 4, 5, 6, 7, 8, 9, null]【隊尾】, front=2, tail=10, size=8, capacity=10}
元素2出隊: LoopQueue{【隊首】data=[null, null, null, 3, 4, 5, 6, 7, 8, 9, null]【隊尾】, front=3, tail=10, size=7, capacity=10}
元素3出隊: LoopQueue{【隊首】data=[null, null, null, null, 4, 5, 6, 7, 8, 9, null]【隊尾】, front=4, tail=10, size=6, capacity=10}
元素4出隊,發生縮容: LoopQueue{【隊首】data=[5, 6, 7, 8, 9, null]【隊尾】, front=0, tail=5, size=5, capacity=5}
隊首元素:5

感謝各位的閱讀!看完上述內容,你們對Java循環隊列的案例分析大概了解了嗎?希望文章內容對大家有所幫助。如果想了解更多相關文章內容,歡迎關注億速云行業資訊頻道。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

历史| 梁平县| 嵩明县| 中西区| 山丹县| 山阳县| 利辛县| 电白县| 阳新县| 溆浦县| 永宁县| 彩票| 铜陵市| 南安市| 莱西市| 渭南市| 石屏县| 延庆县| 读书| 体育| 大邑县| 佛冈县| 东乌| 云浮市| 翼城县| 广南县| 商丘市| 宝清县| 昭苏县| 洛南县| 安顺市| 宜良县| 建宁县| 唐河县| 南宫市| 昭觉县| 洞头县| 阳城县| 汉中市| 渭源县| 武平县|