So implementieren Sie eine kreisförmige Warteschlange in Java

1. Was sind die Probleme bei gewöhnlichen Warteschlangen?

Wie wir alle wissen, haben Warteschlangen mehrere wichtige Attribute:

• hinten: zeigt auf das Ende der Warteschlange, wo sich das letzte Element befindet.

• vorne: Punkte an der Spitze der Warteschlange Die vorherige Position beträgt ebenfalls -1

• Kapazität: Die Kapazität der Warteschlange

Die Rückseite und Vorderseite der leeren Warteschlange sind gleich -1 Beim Betreten der Warteschlange , die Vorderseite bewegt sich nicht, hinten++, wenn hinten Wenn == Kapazität - 1, ist die Warteschlange beim Entfernen aus der Warteschlange voll, hinten bewegt sich nicht, vorne++, wenn vorne == hinten Code>, die Warteschlange ist leer. Es sieht perfekt aus, aber tatsächlich stimmt etwas nicht. Wenn eine Warteschlange <code>capacity = 3 drei Elemente in der Warteschlange hat, dann front = -1; Rear = 2, und dann werden alle drei Elemente aus der Warteschlange entfernt vorne = 2, hinten = 2. Zu diesem Zeitpunkt ist die Warteschlange offensichtlich leer, es können jedoch keine weiteren Elemente zur Warteschlange hinzugefügt werden, da rear = Capacity - 1 erfüllt ist, was bedeutet, dass die Warteschlange wegwerfbar ist und danach nicht mehr verwendet werden kann Selbst wenn es leer ist, kann es nicht zur Warteschlange hinzugefügt werden, was zu einer Platzverschwendung führt, sodass die kreisförmige Warteschlange angezeigt wird. rear == capacity - 1时，队列已满；出队时，rear不动，front++，当front == rear时，队列为空。看起来很完美，但实际上有问题。假如一个队列capacity = 3，入队了三个元素，此时front = -1; rear = 2，然后再将三个元素都出队，此时front = 2, rear = 2。这时队列明明是空的，但是却不能再入队元素的，因为满足rear = capacity - 1，也就是相当于这队列是一次性的，用过之后就不能再用了，即使为空也不能再入队了，造成空间的浪费，所以环形队列就出现了。

2、环形队列实现思路：

环形队列中的几个重要属性：

• rear：指向队列尾巴的后一个位置，初始值为0

• front：指向队列的头部，即第一个元素所在的位置，初始值为0

• capacity：队列的容量

下面是环形队列的一些算法：

• 队列为空时：      front == rear

• 队列已满时：      (rear + 1) % capacity == front

• 获取队列元素个数：      (rear + capacity - front) % capacity

• 入队操作时：      rear = (rear + 1) % capacity

• 出队操作时：      front = (front + 1) % capacity;

判断队列是否已满是环形队列中最重要也是最难理解的地方。假如有一个队列capacity = 3，入队操作如下：

• 第一个元素入队：      front = 0，因为      (rear + 1) % capacity = 1 % 3 != front，所以元素可以入队，元素入队后      rear = 1；

• 第二个元素入队：      front = 0，因为      (rear + 1) % capacity = 2 % 3 != front，所以元素可以入队，元素入队后      rear = 2；

• 第三个元素入队：      front = 0，因为      (rear + 1) % capacity = 3 % 3 == front，所以元素不能入队，队列已满；

队列容量明明是3，只入队了两个元素就告诉我队列满了？没错，这种判断队列是否已满的算法需要牺牲数组的一个空间。

现在进行出队操作：

• 第一个元素出队：      front = 1，      rear = 2，      (rear + 1) % capacity = 3 % 3 = 0 != front

2. Idee zur Implementierung der Ringwarteschlange:

Mehrere wichtige Attribute in der Ringwarteschlange:

hinten: zeigt auf die Position nach dem Ende der Warteschlange, der Anfangswert ist 0 🎜🎜vorne: Punkte zum Kopf der Warteschlange Der Anfangswert ist 0🎜🎜🎜🎜Kapazität: die Kapazität der Warteschlange🎜🎜🎜🎜Im Folgenden sind einige Algorithmen für Ringwarteschlangen aufgeführt:🎜🎜🎜🎜Wenn die Warteschlange leer ist: vorne == hinten🎜🎜🎜🎜Wenn die Warteschlange voll ist: (hinten + 1) % Kapazität == vorne🎜🎜🎜🎜Ermitteln Sie die Anzahl der Warteschlangenelemente: (hinten + Kapazität - vorne) % Kapazität🎜🎜🎜🎜Beim Eintreten in die Warteschlange: hinten = (hinten + 1) % Kapazität🎜🎜🎜🎜Beim Entfernen aus der Warteschlange: front = (front + 1) % Kapazität;🎜🎜🎜🎜Die Feststellung, ob die Warteschlange voll ist, ist der wichtigste und am schwierigsten zu verstehende Teil der kreisförmigen Warteschlange. Wenn eine Warteschlange capacity = 3 vorhanden ist, lautet der Einreihungsvorgang wie folgt: 🎜🎜🎜🎜Das erste Element wird in die Warteschlange gestellt: ​front = 0, weil (rear + 1) % Capacity = 1 % 3 != front, damit das Element in die Warteschlange gestellt werden kann rear = 1;🎜🎜🎜🎜Das zweite Element wird zur Warteschlange hinzugefügt: ​front = 0, weil (hinten + 1) % Kapazität = 2 % 3 != vorne, damit das Element in die Warteschlange gestellt werden kann. rear = 2;🎜🎜🎜🎜Das dritte Element wird der Warteschlange hinzugefügt: ​front = 0, weil (hinten + 1) % Kapazität = 3 % 3 == vorne, daher können die Elemente nicht zur Warteschlange hinzugefügt werden und die Warteschlange ist voll 🎜🎜🎜🎜Die Warteschlangenkapazität beträgt offensichtlich 3, aber nur Zwei Elemente werden zur Warteschlange hinzugefügt. Sagen Sie mir, dass die Warteschlange voll ist. Ja, dieser Algorithmus zur Bestimmung, ob die Warteschlange voll ist, erfordert die Opferung eines Platzes im Array. 🎜🎜Führen Sie nun den Vorgang zum Entfernen aus der Warteschlange aus: 🎜🎜🎜🎜Das erste Element wird aus der Warteschlange entfernt:  front = 1,  hinten = 2, (hinten + 1) % Kapazität = 3 % 3 = 0 != vorne. 🎜🎜🎜🎜Sie können feststellen, dass ein Element, wenn es aus der Warteschlange entfernt wird, die Bedingungen für den Beitritt zur Warteschlange erfüllt, sodass der Array-Speicherplatz wiederverwendet werden kann. 🎜🎜🎜3. Code-Praxis: 🎜🎜

<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>

🎜🎜

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine kreisförmige Warteschlange in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!