循環(huán)佇列的優(yōu)點(diǎn)

普通隊(duì)列出隊(duì)操作開銷大：在出隊(duì)操作時(shí)，索引為0後面的所有元素，都需要往前移動(dòng)一位，元素越多，消耗的時(shí)間也越多，時(shí)間複雜度為O(N)。

循環(huán)隊(duì)列的邏輯：

1、當(dāng)元素較少時(shí)（tail位置在front後面），循環(huán)隊(duì)列與普通隊(duì)列出隊(duì)操作一樣，入隊(duì)的元素將會(huì)放在tail的位置上，隨後執(zhí)行tail 操作；出隊(duì)時(shí)front位置上的元素將會(huì)置null，隨後執(zhí)行front 操作；此時(shí)仍能保持著tail位置在front後面的狀態(tài)，如下圖中所示：

2、當(dāng)元素繼續(xù)添加，最後一個(gè)元素將放到索引為7的位置，此時(shí)tail位置將會(huì)移動(dòng)到隊(duì)首前面索引為0的位置上，此時(shí)tail在陣列的索引為變?yōu)椋?tail 1 )% capacity如下圖所示：

##3、當(dāng)元素繼續(xù)加入時(shí)，元素將會(huì)在tail位置上添加，tail繼續(xù)往後移動(dòng)，如下圖所示：

4、繼續(xù)添加元素，當(dāng)tail與front還相距一個(gè)單位時(shí)，即此時(shí)數(shù)組還有一個(gè)空餘存儲(chǔ)空間，但當(dāng)前數(shù)組已經(jīng)不能繼續(xù)實(shí)現(xiàn)循環(huán)隊(duì)列的插入操作了，因?yàn)檠h(huán)隊(duì)列判斷隊(duì)列為空的條件就是front == tail，所以此時(shí)需要進(jìn)行擴(kuò)容操作；因此此處有意識(shí)的浪費(fèi)了一個(gè)空間。

此處可以推出，循環(huán)隊(duì)列元素滿的條件為：tail 1 == front(初步得出，後續(xù)會(huì)完善為(tail 1) % capacity == front )

5 、適當(dāng)情況下，此若時(shí)持續(xù)進(jìn)行出隊(duì)操作，front的位置也會(huì)從陣列最右端跳到陣列最左端開始。此時(shí)front在陣列的索引為變成：(front 1 )% capacity

程式碼實(shí)作：（相關(guān)影片教學(xué)分享：java影片教學(xué)）

package dataStructure.chapter3;

/**
 * @Author: zjtMeng
 * @Date: 2019/12/28 20:13
 * @Version 1.0
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    /**
     * 循環(huán)隊(duì)列入隊(duì)操作
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //循環(huán)隊(duì)列元素滿的判斷條件,如果滿了就進(jìn)行擴(kuò)容操作，擴(kuò)大兩倍
        if ((tail+1)%data.length == front)
            resize(2 * getCapacity());
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;

    }

    /**
     * 循環(huán)隊(duì)列擴(kuò)容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity+1];
        //循環(huán)隊(duì)列第一種遍歷方式
        for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素與data[]中的元素，一方面存在著front的偏移量，另一方面，data[]中的元素，
//可能在有部分處于front前面，因此此處采用對(duì)數(shù)組長(zhǎng)度取余，來判斷元素的位置
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        front =0;
        tail = size;

    }

    @Override
    public E dequeue() {
        //首先判斷隊(duì)列是否為空，如果為空則拋出異常
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        E ret = data[front];
        //引用地址需要置空，否則JVM不能及時(shí)回收空間，從而可能會(huì)出現(xiàn)OOM異常
        data[front] = null;
        front = (front + 1 )% data.length;
        size--;
        //如果元素?cái)?shù)量達(dá)到隊(duì)列容積的1/4，且隊(duì)列容積/2 不等于0時(shí)，進(jìn)行縮容操作
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0 )
            resize(getCapacity() / 2);
        return ret;
    }

    /**
     * 查看隊(duì)首元素
     * @return
     */
    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

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

    /**
     * 判斷循隊(duì)列是否為空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d, capacity = %d\n",size, getCapacity()));
        res.append("front[");
        //循環(huán)隊(duì)列遍歷的第二種方法
        for (int i = front; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            //循環(huán)隊(duì)列未遍歷到隊(duì)尾的標(biāo)志
            if ((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

相關(guān)文章教學(xué)推薦：

java入門教學(xué)#

以上是java實(shí)作循環(huán)隊(duì)列的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！