快捷導(dǎo)航

在Java中實(shí)現(xiàn)支持隨機(jī)訪問的固定窗口隊(duì)列的代碼示例

更新時(shí)間：2025年10月31日 08:25:46 作者：樺說編程

本文介紹了一種在Java中實(shí)現(xiàn)的自定義滑動隊(duì)列,利用了Google Guava庫中的EvictingQueue,這種滑動隊(duì)列允許以固定大小管理隊(duì)列,并能夠隨機(jī)訪問元素,我們將探討這種數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)、實(shí)現(xiàn)和使用,需要的朋友可以參考下

引言

本文介紹了一種在Java中實(shí)現(xiàn)的自定義滑動隊(duì)列，利用了Google Guava庫中的EvictingQueue。這種滑動隊(duì)列允許以固定大小管理隊(duì)列，并能夠隨機(jī)訪問元素。我們將探討這種數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)、實(shí)現(xiàn)和使用。

隊(duì)列是計(jì)算機(jī)科學(xué)中的基本數(shù)據(jù)結(jié)構(gòu)，用于以先進(jìn)先出（FIFO）的方式存儲和管理數(shù)據(jù)。然而，在某些場景下，例如實(shí)時(shí)數(shù)據(jù)處理或滑動窗口算法，需要一個(gè)固定大小的隊(duì)列來自動淘汰舊元素。本文介紹了一種自定義的SlidingQueue實(shí)現(xiàn)，它通過擴(kuò)展標(biāo)準(zhǔn)隊(duì)列的功能，結(jié)合淘汰和隨機(jī)訪問特性來滿足這些需求。

代碼

public class SlidingQueue<T> extends ForwardingQueue<T> {

    private final EvictingQueue<T> queue;
    // view
    private final ArrayDeque<T> arrayDeque;
    private int cachedHead = -1;
    private Object[] cachedElements = null;

    @SneakyThrows
    public SlidingQueue(int size) {
        this.queue = EvictingQueue.create(size);
        this.arrayDeque = (ArrayDeque<T>) FieldUtils.readField(queue, "delegate", true);
    }

    // 只允許添加和刪除操作，其他操作都不允許修改隊(duì)列內(nèi)容
    @Override
    public boolean add(T element) {
        cachedHead = -1;
        return queue.add(element);
    }

    @Override
    public T remove() {
        cachedHead = -1;
        return queue.remove();
    }

    // 使用標(biāo)準(zhǔn)實(shí)現(xiàn)，下面兩個(gè)方法委托給上面的add和remove方法
    @Override
    public boolean offer(T o) {return standardOffer(o);}
    @Override
    public T poll() {return standardPoll();}

    // 默認(rèn)實(shí)現(xiàn)，委托給不可變視圖，所有的寫操作都默認(rèn)禁止
    @Override
    protected Queue<T> delegate() {
        return UnmodifiableQueue.unmodifiableQueue(queue);
    }

    // 支持隨機(jī)訪問
    @SneakyThrows
    public T get(int index) {
        Object[] elements;
        int head;
        if (cachedHead == -1) {
            cachedElements = elements = (Object[]) FieldUtils.readField(arrayDeque, "elements", true);
            cachedHead = head = (int) FieldUtils.readField(arrayDeque, "head", true);
        } else {
            elements = cachedElements;
            head = cachedHead;
        }
        return (T) elements[inc(head, index, elements.length)];
    }

    // 環(huán)形數(shù)組下標(biāo)計(jì)算
    static int inc(int i, int distance, int modulus) {
        if ((i += distance) - modulus >= 0) i -= modulus;
        return i;
    }
}

實(shí)現(xiàn)細(xì)節(jié)

1. 利用Guava的EvictingQueue

SlidingQueue類基于Guava的EvictingQueue構(gòu)建，提供了一個(gè)固定大小的隊(duì)列，當(dāng)隊(duì)列達(dá)到容量時(shí)會自動淘汰最舊的元素。這種行為非常適合只關(guān)注最新元素的場景。

private final EvictingQueue<T> queue;

2. 使用ArrayDeque實(shí)現(xiàn)高效訪問

為了實(shí)現(xiàn)隨機(jī)訪問，SlidingQueue使用ArrayDeque作為底層數(shù)據(jù)結(jié)構(gòu)。這允許通過索引高效地檢索元素，這是標(biāo)準(zhǔn)隊(duì)列實(shí)現(xiàn)所不具備的功能。

private final ArrayDeque<T> arrayDeque;

3. 支持隨機(jī)訪問

SlidingQueue提供了get(int index)方法，支持對隊(duì)列中元素的隨機(jī)訪問。這是通過直接訪問ArrayDeque的內(nèi)部數(shù)組實(shí)現(xiàn)的。

public T get(int index) {
    // 訪問元素?cái)?shù)組并計(jì)算正確的索引
}

4. 處理循環(huán)索引

隊(duì)列使用循環(huán)數(shù)組來存儲元素，這需要對索引進(jìn)行仔細(xì)處理。inc方法用于在數(shù)組范圍內(nèi)計(jì)算正確的索引。

static int inc(int i, int distance, int modulus) {
    if ((i += distance) - modulus >= 0) i -= modulus;
    return i;
}

使用示例

SlidingQueue可用于需要固定大小、自動淘汰且支持隨機(jī)訪問的場景。以下是一個(gè)示例，演示了其用法：

public static void main(String[] args) {
    SlidingQueue<Integer> q = new SlidingQueue<>(5);
    for (int i = 0; i < 10; i++) {
        q.offer(i);
        System.out.format("iteration(i = %d): \n", i);
        int[] array = IntStream.range(0, q.size()).map(q::get).toArray();
        System.out.println("array extracted:" + Arrays.toString(array));
    }
}

輸入結(jié)果如下：

iteration(i = 0): 
array extracted:[0]
iteration(i = 1): 
array extracted:[0, 1]
iteration(i = 2): 
array extracted:[0, 1, 2]
iteration(i = 3): 
array extracted:[0, 1, 2, 3]
iteration(i = 4): 
array extracted:[0, 1, 2, 3, 4]
iteration(i = 5): 
array extracted:[1, 2, 3, 4, 5]
iteration(i = 6): 
array extracted:[2, 3, 4, 5, 6]
iteration(i = 7): 
array extracted:[3, 4, 5, 6, 7]
iteration(i = 8): 
array extracted:[4, 5, 6, 7, 8]
iteration(i = 9): 
array extracted:[5, 6, 7, 8, 9]

結(jié)論

SlidingQueue實(shí)現(xiàn)為管理具有淘汰和隨機(jī)訪問功能的固定大小隊(duì)列提供了一個(gè)強(qiáng)大的解決方案。通過利用Guava的EvictingQueue和Java的ArrayDeque，這種數(shù)據(jù)結(jié)構(gòu)既高效又多功能，適用于各種應(yīng)用，包括實(shí)時(shí)數(shù)據(jù)處理和滑動窗口算法。