Java循環佇列的介紹（程式碼範例）

這篇文章帶給大家的內容是關於Java循環佇列的介紹（程式碼範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

為了解決陣列佇列帶來的問題，這篇文章為大家介紹一下循環隊列。

想法分析圖解

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

在這裡，我們宣告了一個容量大小為8的數組，並標示了索引0-7，然後使用front#和##tail#分別來表示隊列的，隊首和隊尾；在下圖中，front和tail#的位置一開始都指向是了索引0的位置，這意味著當 front == tai的時候隊列為空 大家務必牢記這一點，以便區分後面介紹隊列快滿時的臨界條件

為了大家更能理解下面的內容，在這裡，我簡單做幾點說明

#front：表示隊列隊首，總是指向隊列中的第一個元素（當隊列空時，front指向索引為0的位置）

tail：表示隊列隊尾，總是指向隊列中的最後一個元素的下一個位置

元素入隊，維護

tail的位置，進行tail 操作

元素出隊，維護

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

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

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

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

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

#看完了元素的入隊的操作情況，那現在我們看一下，元素的出隊操作是什麼樣的？

元素

a出隊，示意圖如下：

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

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

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

到這裡，可能有的小夥伴會問，為什麼叫做，循環隊列？那現在我們試試看，我們讓元素f、g分別進行入隊操作，此時的示意圖如下：

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

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

細心的小夥伴，會發現此時我們的隊列並沒有滿，還剩兩個位置（這是因為我們元素出隊後，當前的空間，沒有被後面的元素擠掉），大家可以把我們的陣列想像成一個環狀，那麼索引7之後的位置就是索引0

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

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

假設現在又有新的元素k入隊了，那麼tail的位置等於（tail 1） % capacity 也就是（0 1）% 8 等於1就指向了索引為1的位置

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

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

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

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

了解了循環佇列的實作原理之後，下面我們用程式碼實作一下。

程式碼實作

介面定義 ：Queue

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

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

    /**
     * 获取队首元素
     *
     * @return
     */
    E getFront();

    /**
     * 获取队列中元素的个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();
}</e>

介面實作：LoopQueue

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 <p>測試類別：LoopQueueTest</p>
<pre class="brush:php;toolbar:false">public class LoopQueueTest {
    @Test
    public void testLoopQueue() {
        LoopQueue<integer> loopQueue = new LoopQueue();
        for (int i = 0; i <h5 id="測試結果">測試結果：</h5>
<pre class="brush:php;toolbar:false">原始队列: 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

完整版程式碼GitHub倉庫位址：Java版資料結構-佇列（循環佇列）

本篇文章到這裡就已經全部結束了，更多其他精彩內容可以關注PHP中文網的Java影片教學專欄！

#

以上是Java循環佇列的介紹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！