Javaで循環キューを実装する方法

1. 通常のキューの問題点は何ですか?

キューにはいくつかの重要な属性があることは誰もが知っています:

• rear: キューの最後尾、つまり最後の要素の位置を指します。 、初期値は -1

• #front: キューの先頭の前の位置を指し、初期値も -1
  ## です
#capacity: キューの容量
空のキューの後部と前部は両方とも -1 に等しい。キューに参加するとき、前部は移動せず、後部は動かない

rear == 容量 - 1

の場合、キューは満杯です。デキューの場合、リアは移動せず、フロント、front == Rear の場合、キューは空です。完璧に見えますが、実際には問題があります。キュー capacity = 3 の場合、3 つの要素がキューに登録され、front = -1; Rear = 2 となり、この時点で 3 つの要素すべてがデキューされますfront = 2、リア = 2。この時点では、キューは明らかに空ですが、rear = Capacity - 1 が満たされているため、キューにこれ以上要素を追加することはできません。つまり、キューは 1 回限りであり、再度使用することはできません。使用後は、空であってもキューに追加できず、スペースが無駄になるため、循環キューが表示されます。

2. リング キュー実装のアイデア:

リング キューのいくつかの重要な属性:

rear: を指します。 queue 末尾の後の位置、初期値は 0
front: キューの先頭、つまり最初の要素の位置を指します、初期値は 0
capacity: キューの容量
リング キューのアルゴリズムの一部を次に示します:

キューが空の場合:
• フロント == リア

キューがいっぱいの場合:
• (後部 1) % 容量 == フロント

キュー要素の数を取得します。
• (後部容量 - フロント) % 容量

キューに参加する場合:
• rear = (リア 1) % 容量

デキュー時:
• front = (front 1) % Capacity;

キューが満杯かどうかの判断は、リング キューの最も重要かつ理解しにくい部分です。キュー

capacity = 3

がある場合、エンキュー操作は次のようになります:

最初の要素がキューに追加されます。
• フロント = 0

  、なぜなら (rear 1) % Capacity = 1 % 3 !=front なので、要素をキューに入れることができます。 rear = 1;

2 番目の要素がキューに追加されます。
• フロント = 0

  、なぜなら (rear 1) % Capacity = 2 % 3 !=front なので、要素をキューに入れることができます。 rear = 2;

3 番目の要素がキューに追加されます。
• フロント = 0

  、なぜなら (後部 1) % 容量 = 3 % 3 == フロント であるため、要素をキューに追加できず、キューがいっぱいです;

キュー容量は明らかに 3 で、キューのみ追加できます。2 つの要素をキューに入れたらキューがいっぱいになったと教えてください。はい、キューがいっぱいかどうかを判断するこのアルゴリズムでは、配列内のスペースを犠牲にする必要があります。

ここでデキュー操作を実行します:

最初の要素がデキューされます。
• フロント = 1

  、 リア = 2、 (リア 1) % 容量 = 3 % 3 = 0 != フロント 。

要素がデキューされると、キューに入る条件を満たしていることがわかり、配列スペースを再利用できます。

3. コードの練習:

<code>public class CircleQueue<E> {<br>    private int capacity;<br>    private int front;<br>    private int rear;<br>    private Object[] arr;<br><br>    public CircleQueue(int capacity){<br>        this.capacity = capacity;<br>        this.arr = new Object[capacity];<br>        this.front = 0;<br>        this.rear = 0;<br>    }<br><br>    public boolean isFull(){<br>        return (rear + 1) % capacity == front;<br>    }<br><br>    public boolean isEmpty(){<br>        return rear == front;<br>    }<br><br>    public void addQueue(E e){<br>        if (isFull()){<br>            throw new RuntimeException("队列已满，入队失败");<br>        }<br>        arr[rear] = e;<br>        // rear指针后移<br>        rear = (rear + 1) % capacity;<br>    }<br><br>    public E getQueue(){<br>        if (isEmpty()){<br>            throw new RuntimeException("队列为空，出队失败");<br>        }<br>        E val = (E) arr[front];<br>        front = (front + 1) % capacity;<br>        return val;<br>    }<br><br><br>    public int getSize(){<br>        return (rear + capacity - front) % capacity;<br>    }<br><br>    // 遍历<br>    public void showQueue(){<br>        if (isEmpty()){<br>            return;<br>        }<br>        for (int i = front; i < front + getSize(); i++) {<br/>            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);<br/>        }<br/>    }<br/><br/>    public static void main(String[] args){<br/>        CircleQueue<Integer> queue = new CircleQueue<>(3);<br>        queue.addQueue(1);<br>        queue.addQueue(2);<br>        queue.showQueue();<br>        //queue.addQueue(3);<br>        System.out.println(queue.getSize());<br>        System.out.println(queue.getQueue());;<br>        queue.addQueue(3);<br>        queue.showQueue();<br>    }<br>}</code>

以上がJavaで循環キューを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。