搜尋
首頁JavaJava入門java實作循環隊列

java實作循環隊列

Dec 31, 2019 pm 05:14 PM
java循環隊列

java實作循環隊列

循環佇列的優點

普通隊列出隊操作開銷大:在出隊操作時,索引為0後面的所有元素,都需要往前移動一位,元素越多,消耗的時間也越多,時間複雜度為O(N)。

循環隊列的邏輯:

1、當元素較少時(tail位置在front後面),循環隊列與普通隊列出隊操作一樣,入隊的元素將會放在tail的位置上,隨後執行tail 操作;出隊時front位置上的元素將會置null,隨後執行front 操作;此時仍能保持著tail位置在front後面的狀態,如下圖中所示:

java實作循環隊列

2、當元素繼續添加,最後一個元素將放到索引為7的位置,此時tail位置將會移動到隊首前面索引為0的位置上,此時tail在陣列的索引為變為:(tail 1 )% capacity如下圖所示:

java實作循環隊列

##3、當元素繼續加入時,元素將會在tail位置上添加,tail繼續往後移動,如下圖所示:

java實作循環隊列

4、繼續添加元素,當tail與front還相距一個單位時,即此時數組還有一個空餘存儲空間,但當前數組已經不能繼續實現循環隊列的插入操作了,因為循環隊列判斷隊列為空的條件就是front == tail,所以此時需要進行擴容操作;因此此處有意識的浪費了一個空間。

此處可以推出,循環隊列元素滿的條件為:tail 1 == front(初步得出,後續會完善為(tail 1) % capacity == front )

5 、適當情況下,此若時持續進行出隊操作,front的位置也會從陣列最右端跳到陣列最左端開始。此時front在陣列的索引為變成:(front 1 )% capacity

程式碼實作:(相關影片教學分享: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();
    }
}

相關文章教學推薦:

java入門教學#

以上是java實作循環隊列的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文轉載於:CSDN。如有侵權,請聯絡admin@php.cn刪除

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。