Java implémente une file d'attente circulaire

Avantages des files d'attente circulaires

Les opérations de mise en file d'attente ordinaires sont coûteuses : lors des opérations de retrait de la file d'attente, tous les éléments après l'index 0 doivent tous être déplacés avancer d'une position. Plus il y a d'éléments, plus cela prend de temps et la complexité temporelle est O(N).

La logique de la file d'attente circulaire :

1. Lorsqu'il y a peu d'éléments (la position de la queue est derrière l'avant), la file d'attente circulaire a le même fonctionnement de file d'attente. comme une file d'attente normale. Les éléments de la file d'attente seront placés en position de queue, puis l'opération tail++ sera effectuée lors du retrait de la file d'attente, l'élément en position avant sera défini sur null, puis l'opération front++ sera effectuée ; ; à ce moment, la position de la queue peut toujours être maintenue derrière l'avant, comme suit Comme le montre l'image :

2. Au fur et à mesure que les éléments continuent d'être ajoutés, le dernier L'élément sera placé à l'index 7. A ce moment, la position de la queue se déplacera vers l'index devant la tête de la file d'attente. À la position 0, l'index de la queue dans le tableau devient : (queue+ 1) % de capacité. comme le montre la figure ci-dessous :

3. Lorsque des éléments continuent d'être ajoutés, l'élément sera ajouté à la position de queue et la queue continuera à reculer, comme le montre la figure ci-dessous :

4. Continuez à ajouter des éléments, lorsque la queue et l'avant sont encore une unité l'un de l'autre. À ce stade, c'est-à-dire qu'il y a encore un espace de stockage libre dans le tableau, mais le tableau actuel ne peut plus implémenter l'opération d'insertion de la file d'attente circulaire, car la condition pour que la file d'attente circulaire juge que la file d'attente est vide est front == tail, donc une opération d'expansion est requise à ce stade du temps ; Il y a donc ici une perte d’espace consciente.

On peut en déduire ici que la condition pour que les éléments de la file d'attente circulaire soient pleins est : queue +1 == avant (conclusion préliminaire, elle sera améliorée à (queue + 1) % de capacité == avant)

5. Dans des circonstances appropriées, si l'opération de retrait de la file d'attente se poursuit, la position du front passera également de l'extrémité droite du tableau à l'extrémité gauche du tableau. À ce stade, l'indice de front dans le tableau devient : (front + 1)% de capacité

Implémentation du code : (Partage du didacticiel vidéo associé : Tutoriel vidéo 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;
    }

    /**
     * 循环队列入队操作
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //循环队列元素满的判断条件,如果满了就进行扩容操作，扩大两倍
        if ((tail+1)%data.length == front)
            resize(2 * getCapacity());
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;

    }

    /**
     * 循环队列扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity+1];
        //循环队列第一种遍历方式
        for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素与data[]中的元素，一方面存在着front的偏移量，另一方面，data[]中的元素，
//可能在有部分处于front前面，因此此处采用对数组长度取余，来判断元素的位置
            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不能及时回收空间，从而可能会出现OOM异常
        data[front] = null;
        front = (front + 1 )% data.length;
        size--;
        //如果元素数量达到队列容积的1/4，且队列容积/2 不等于0时，进行缩容操作
        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[");
        //循环队列遍历的第二种方法
        for (int i = front; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            //循环队列未遍历到队尾的标志
            if ((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

Articles et tutoriels connexes recommandés : Tutoriel d'introduction à Java

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!