Vorteile von zirkul?ren Warteschlangen

Gew?hnliche Warteschlangeneinreihungsvorg?nge sind teuer: Bei Entnahmevorg?ngen müssen alle Elemente nach Index 0 verschoben werden Je mehr Elemente vorhanden sind, desto mehr Zeit wird verbraucht und die Zeitkomplexit?t betr?gt O(N).

Die Logik der kreisf?rmigen Warteschlange:

1. Wenn nur wenige Elemente vorhanden sind (die Endposition befindet sich hinter der Vorderseite), hat die kreisf?rmige Warteschlange den gleichen Warteschlangenvorgang Als normale Warteschlange werden die Elemente der Warteschlange an der Endposition platziert und dann wird die Tail++-Operation ausgeführt. Wenn das Element aus der Warteschlange entfernt wird, wird die vordere Position auf Null gesetzt und dann wird die Front++-Operation ausgeführt ; Zu diesem Zeitpunkt kann die Heckposition noch wie folgt hinter der Vorderseite beibehalten werden. Wie im Bild gezeigt:

2. W?hrend weiterhin Elemente hinzugefügt werden, das letzte Das Element wird an Index 7 platziert. Zu diesem Zeitpunkt wird die Endposition zum Index vor dem Kopf der Warteschlange verschoben. An der Position 0 betr?gt der Endindex im Array: (Ende + 1) % Kapazit?t wie in der folgenden Abbildung gezeigt:

3. Wenn weiterhin Elemente hinzugefügt werden, wird das Element an der Schwanzposition hinzugefügt und der Schwanz bewegt sich weiter rückw?rts. wie in der folgenden Abbildung gezeigt:

4. Fügen Sie weitere Elemente hinzu, wenn der Schwanz und die Vorderseite noch eine Einheit voneinander entfernt sind. Zu diesem Zeitpunkt ist also noch ein Freier Speicherplatz im Array, aber das aktuelle Array kann den Einfügevorgang der zirkul?ren Warteschlange nicht mehr implementieren, da die Bedingung für die zirkul?re Warteschlange, um zu beurteilen, dass die Warteschlange leer ist, front == tail ist, sodass hier eine Erweiterungsoperation erforderlich ist Zeit; Hier wird also bewusst Platz verschwendet.

Hier l?sst sich ableiten, dass die Bedingung dafür, dass das kreisf?rmige Warteschlangenelement voll ist, lautet: Schwanz +1 == vorne (vorl?ufige Schlussfolgerung: Es wird auf (Schwanz + 1) % Kapazit?t == vorne verbessert)

5. Wenn der Vorgang zum Entfernen aus der Warteschlange fortgesetzt wird, springt die Position von vorne auch vom rechten Ende des Arrays zum linken Ende des Arrays. Zu diesem Zeitpunkt lautet der Frontindex im Array: (Front + 1) % Kapazit?t

Code-Implementierung: (Verwandte Video-Tutorial-Freigabe: Java-Video-Tutorial )

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

    }

    /**
     * 循環(huán)隊(duì)列擴(kuò)容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity+1];
        //循環(huán)隊(duì)列第一種遍歷方式
        for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素與data[]中的元素，一方面存在著front的偏移量，另一方面，data[]中的元素，
//可能在有部分處于front前面，因此此處采用對(duì)數(shù)組長(zhǎng)度取余，來判斷元素的位置
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        front =0;
        tail = size;

    }

    @Override
    public E dequeue() {
        //首先判斷隊(duì)列是否為空，如果為空則拋出異常
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        E ret = data[front];
        //引用地址需要置空，否則JVM不能及時(shí)回收空間，從而可能會(huì)出現(xiàn)OOM異常
        data[front] = null;
        front = (front + 1 )% data.length;
        size--;
        //如果元素?cái)?shù)量達(dá)到隊(duì)列容積的1/4，且隊(duì)列容積/2 不等于0時(shí)，進(jìn)行縮容操作
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0 )
            resize(getCapacity() / 2);
        return ret;
    }

    /**
     * 查看隊(duì)首元素
     * @return
     */
    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判斷循隊(duì)列是否為空
     * @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)隊(duì)列遍歷的第二種方法
        for (int i = front; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            //循環(huán)隊(duì)列未遍歷到隊(duì)尾的標(biāo)志
            if ((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

Empfohlene verwandte Artikel und Tutorials: Java-Einführungs-Tutorial

Das obige ist der detaillierte Inhalt vonJava implementiert eine zirkul?re Warteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!