循環(huán)キューの利點(diǎn)

通常のキューのデキュー操作は高価です。デキュー操作中、インデックス 0 以降のすべての要素を移動する必要があります。要素が多いほど、より多くの時間が消費(fèi)され、時間計算量は O(N) になります。

循環(huán)キューのロジック:

1. 要素が少ない場合 (末尾の位置が先頭の後ろにある場合)、循環(huán)キューは同じキューイング操作を行います。通常のキューと同様に、キューの要素は末尾の位置に配置され、末尾の操作が実行されます。要素がデキューされると、先頭の位置にある要素は null に設(shè)定され、その後、先頭の操作が実行されます。

#2. 図に示すように、このとき、末尾の位置は前部の後ろに維持することができます。追加すると、最後の要素はインデックス 7 に配置されます。このとき、末尾の位置はキューの先頭のインデックスの前に移動します。位置 0 では、配列內(nèi)の末尾のインデックスは次のようになります。(tail 1) 以下の図に示す容量%:

3. 要素が追加され続けると、要素は末尾の位置に追加され、末尾が続きます。次の図に示すように、後方に移動します:

#4. 後部と前部がまだ 1 単位離れているときに、要素を追加し続けます。 、配列にはまだ空き記憶領(lǐng)域がありますが、現(xiàn)在の配列では循環(huán)キューの挿入操作を?qū)g裝できなくなりました。これは、循環(huán)キューがキューが空であると判斷するための條件が前 == 末尾であるため、拡張現(xiàn)時點(diǎn)では操作が必要なので、ここでは意識的にスペースを無駄にしています。

ここで、循環(huán)キュー要素が満杯になるための條件は次のとおりであると推測できます: 末尾 1 == フロント (暫定的な結(jié)論。(末尾 1) % 容量 == フロントに改善されます)

5 . 適切な狀況下で、デキュー操作が継続すると、フロントの位置も配列の右端から配列の左端にジャンプします。このとき、配列內(nèi)のフロントのインデックスは次のようになります: (フロント 1)% 容量

コード実裝: (関連ビデオ チュートリアルの共有: java ビデオ チュートリアル

)

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

    }

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

    }

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

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

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

    /**
     * 判斷循隊列是否為空
     * @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)隊列遍歷的第二種方法
        for (int i = front; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            //循環(huán)隊列未遍歷到隊尾的標(biāo)志
            if ((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

おすすめの関連記事とチュートリアル: Java 入門チュートリアル

###

以上がJavaは循環(huán)キューを?qū)g裝しますの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。