Java 循環キューの概要 (コード例)

この記事では、Java 循環キューの概要 (コード例) を紹介します。これには一定の参考価値があります。必要な友人は参照できます。お役に立てば幸いです。

配列キューによって引き起こされる問題を解決するために、この記事では循環キューについて紹介します。

アイデア分析イラスト

投稿した写真に移動や削除などのアニメーション効果を持たせるのが作者は苦手なので申し訳ありません。要素 (結局のところ、これは誰にとってもより直感的です)。作者は、ここでは静的な画像を通して実装原理を理解することしかできません。外さないでほしいと思います。その方法を知っている人がいたら、知恵を共有してください。コメントエリア。

ここでは、容量 8 の配列を宣言し、インデックス 0 ～ 7 をマークし、それぞれ front と tail を使用して、 queue、キューの先頭と末尾。以下の図では、front と tail の位置は、最初はインデックス 0 の位置を指します。これは、 のときを意味します。フロント == tai<font color="red"></font>キューは空です キューを区別するには、全員がこの点に留意する必要があります後ほど紹介します ほぼ満杯の場合の危機的状況

以下の内容を皆様によく理解していただくために、ここで簡単に説明します

front: キューの先頭を表し、常にキューの最初の要素を指します (キューが空の場合、front はインデックス 0 の位置を指します)

tail: キューの末尾を示し、常にキュー内の最後の要素の次の位置を指します

要素はキューに追加され、tail の位置になりますが維持され、tail 操作

要素がデキューされ、front の位置が維持され、front 操作が実行されます。要素は簡単な方法でキューに入れたり、キューから取り出したりできます。tail と front の位置を維持することは実際には厳密ではありません。テールを維持する正しい位置は (テール 1) % 容量である必要があります。同様に、フロントの位置は (フロント 1 ) % 容量でなければなりません。これが循環キューと呼ばれる理由です。ここで最初に知っておきましょう。まだ理解していなくても問題ありません。きっとわかると思います。それは後で。

見てみましょう。要素 a がチームに参加すると、現在の図:

要素 a がチームに参加することがわかります。 tail が指す位置は変更され、操作が実行されましたが、front の位置は変更されず、依然としてインデックス 0 の位置を指します。著者が上で述べたことを思い出してください。front の位置は常に の最初の要素を指します。キュー。末尾の位置は常にキュー内の最後の要素の次の位置を指します。

ここで、さらにいくつかの要素 b、c、d、e をキューに追加しましょう回路図を見てみましょう:

回路図が次のようになっていることは誰もが知っていると思いますが、それほど多くはないようです。 (心配しないでください。著者は、皆さんがそれが何なのかを理解できるようにするためにここにいます)キューに入る要素の操作を見てみましょう。要素をキューから取り出す操作はどのようなものですか?

要素 a

がデキューされました。概略図は次のとおりです:

要素 a がデキューされ、フロントの位置はインデックスを指します。これは 1 の位置です。これで、配列内のすべての要素が 1 つ前に移動する必要がなくなりました。

これは、配列キューと一致します (配列キューでは、要素がデキューされ、後続の要素が前方 (1 つの位置) に移動する必要があるのはまったく異なります。前方の方向を変更するだけです。前の O(n) 操作から、O(1) 操作になります。

要素 b を再度デキューします。概略図は次のとおりです。

この時点で、友人の中には、なぜそれが a と呼ばれるのか疑問に思う人もいるかもしれません。循環列？それでは試してみましょう 要素 f と要素 g をそれぞれキューに入れます この時の図は次のようになります:

実行しても変化はありませんこの時点で、別の要素 h 要素をキューに追加すると、尻尾の位置をどのように向けるべきかという疑問が生じます。概略図は次のとおりです。

前に述べたように、要素はキューに入れられます: 尾部の位置を維持し、尾部操作を実行します。この時点で、尾部はインデックス 7 の位置を指しています。もし今だと、明らかに末尾（範囲外の配列）を操作することは不可能です

注意深い友人なら、この時点ではキューがいっぱいではなく、2 つの位置が残っていることに気づくでしょう（これは、要素の後にあるためです）がデキューされ、後続の要素によって絞り出されていない現在の空間です)、配列をリングとして想像すると、インデックス 7 の後の位置がインデックス 0

インデックス 7 の位置からインデックス 0

# までどのように計算できますか?インデックス 0 の位置については、前に末尾演算について説明しました。著者は、これが厳密ではないことも最初に指摘しました。(末尾 1) % 容量である必要があるため、(7 1) % 8 は 0## になります

#したがって、この時点で要素 h をキューに追加すると、末尾はインデックス 0 の位置を指すことになります。図は次のとおりです。

仮定 新しい要素 k がキューに追加されたので、末尾の位置は (tail 1) % Capacity、つまり (0 1) % 8 に等しくなります。それが 1 に等しい場合、これはインデックス 1 の位置を指します

次に問題は、循環キューは引き続き要素をエンキューできるかということです。それを分析しましょう。この図は、インデックス 0 の空のスペース位置がまだあることを示しています。これは、この時点で tail が指す位置です。

前のロジックに従って、新しい要素を配置できると仮定します。 now では、テールが (テール 1) % 容量計算を実行し、結果は 2 になります (要素がキューに正常に追加された場合、この時点でキューはいっぱいです)。この時点で、フロントがヘッドを表していることがわかります。キューの もインデックス 2 の位置を指します

新しい要素がキューに正常に追加された場合、テールも 2 に等しいため、テール == フロントになります。キューが空のときは、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 <p>テスト結果: </p>
<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 中国語 Web サイトの Java ビデオ チュートリアル 列に注目してください。

#

以上がJava 循環キューの概要 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。