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

    /**
     * 循環(huán)隊列入隊操作
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //循環(huán)隊列元素滿的判斷條件,如果滿了就進(jìn)行擴(kuò)容操作，擴(kuò)大兩倍
        if ((tail+1)%data.length == front)
            resize(2 * getCapacity());
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;

    }

    /**
     * 循環(huán)隊列擴(kuò)容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity+1];
        //循環(huán)隊列第一種遍歷方式
        for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素與data[]中的元素，一方面存在著front的偏移量，另一方面，data[]中的元素，
//可能在有部分處于front前面，因此此處采用對數(shù)組長度取余，來判斷元素的位置
            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不能及時回收空間，從而可能會出現(xiàn)OOM異常
        data[front] = null;
        front = (front + 1 )% data.length;
        size--;
        //如果元素數(shù)量達(dá)到隊列容積的1/4，且隊列容積/2 不等于0時，進(jìn)行縮容操作
        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[");
        //循環(huán)隊列遍歷的第二種方法
        for (int i = front; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            //循環(huán)隊列未遍歷到隊尾的標(biāo)志
            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!