Comment implémenter une file d'attente circulaire en Java

1. Quels sont les problèmes avec les files d'attente ordinaires ?

Tout le monde sait que les files d'attente ont plusieurs attributs importants :

• rear : pointe vers la queue de la file d'attente, où se trouve le dernier élément, et la valeur initiale est -1

• front : pointe vers le tête de file d'attente La position précédente, la valeur initiale est également -1

• capacité : la capacité de la file d'attente

L'arrière et l'avant de la file d'attente vide sont égaux à -1. l'avant ne bouge pas, l'arrière++, quand arrière Quand == capacité - 1, la file d'attente est pleine lors du retrait de la file d'attente, l'arrière ne bouge pas, avant++, quand avant == arrière , la file d'attente est vide. Cela semble parfait, mais il y a en fait quelque chose qui ne va pas. Si une file d'attente capacity = 3 a trois éléments mis en file d'attente, alors front = -1; Rear = 2, puis les trois éléments seront retirés de la file d'attente. Ce sera le cas lorsque . avant = 2, arrière = 2. À ce stade, la file d'attente est évidemment vide, mais aucun élément supplémentaire ne peut être ajouté à la file d'attente, car rear = capacité - 1 est satisfait, ce qui signifie que la file d'attente est jetable et ne peut plus être utilisée après il est utilisé même s'il est vide, il ne peut pas être ajouté à nouveau à la file d'attente, provoquant une perte d'espace, donc la file d'attente circulaire apparaît. 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. Idée d'implémentation de la file d'attente en anneau :

Plusieurs attributs importants dans la file d'attente en anneau :

arrière : pointe vers la position après la queue de la file d'attente, la valeur initiale est 0 🎜🎜avant : points à la tête de la file d'attente La valeur initiale est 0🎜🎜🎜🎜capacité : la capacité de la file d'attente🎜🎜🎜🎜Voici quelques algorithmes pour les files d'attente en anneau :🎜🎜🎜🎜Lorsque la file d'attente est vide : avant == arrière🎜🎜🎜🎜Lorsque la file d'attente est pleine : (arrière + 1) % capacité == avant🎜🎜🎜🎜Obtenez le nombre d'éléments de la file d'attente : (arrière + capacité - avant) % capacité🎜🎜🎜🎜En rejoignant la file d'attente : arrière = (arrière + 1) % de capacité🎜🎜🎜🎜Lors du retrait de la file d'attente : front = (front + 1) % de capacité ;🎜🎜🎜🎜Déterminer si la file d'attente est pleine est la partie la plus importante et la plus difficile à comprendre de la file d'attente circulaire. S'il y a une file d'attente capacity = 3, l'opération de mise en file d'attente est la suivante : 🎜🎜🎜🎜Le premier élément est mis en file d'attente : ​front = 0, car (arrière + 1) % capacité = 1 % 3 != avant, donc l'élément peut être mis en file d'attente une fois l'élément mis en file d'attente. rear = 1;🎜🎜🎜🎜Le deuxième élément est ajouté à la file d'attente : ​front = 0, car (arrière + 1) % capacité = 2 % 3 != avant, donc l'élément peut être mis en file d'attente une fois l'élément mis en file d'attente. rear = 2;🎜🎜🎜🎜Le troisième élément est ajouté à la file d'attente : ​front = 0, car (arrière + 1) % capacité = 3 % 3 == avant, donc les éléments ne peuvent pas être ajoutés à la file d'attente et la file d'attente est pleine 🎜🎜🎜🎜La capacité de la file d'attente est évidemment de 3, mais seulement ; deux éléments sont ajoutés à la file d'attente. Dites-moi que la file d'attente est pleine ? Oui, cet algorithme pour déterminer si la file d'attente est pleine nécessite de sacrifier un espace dans le tableau. 🎜🎜Effectuez maintenant l'opération de retrait de la file d'attente : 🎜🎜🎜🎜Le premier élément est retiré de la file d'attente :  avant = 1,  arrière = 2, (arrière + 1) % capacité = 3 % 3 = 0 != avant. 🎜🎜🎜🎜Vous pouvez constater que lorsqu'un élément est retiré de la file d'attente, il remplit les conditions pour rejoindre la file d'attente, de sorte que l'espace du tableau peut être réutilisé. 🎜🎜🎜3. Pratique du code : 🎜🎜

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

🎜🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!