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

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

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

引言

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

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

代碼

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

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

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

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

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

    // 支持隨機訪問
    @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ù)組下標計算
    static int inc(int i, int distance, int modulus) {
        if ((i += distance) - modulus >= 0) i -= modulus;
        return i;
    }
}

實現(xiàn)細節(jié)

1. 利用Guava的EvictingQueue

SlidingQueue類基于Guava的EvictingQueue構建，提供了一個固定大小的隊列，當隊列達到容量時會自動淘汰最舊的元素。這種行為非常適合只關注最新元素的場景。

private final EvictingQueue<T> queue;

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

為了實現(xiàn)隨機訪問，SlidingQueue使用ArrayDeque作為底層數(shù)據(jù)結構。這允許通過索引高效地檢索元素，這是標準隊列實現(xiàn)所不具備的功能。

private final ArrayDeque<T> arrayDeque;

3. 支持隨機訪問

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

public T get(int index) {
    // 訪問元素數(shù)組并計算正確的索引
}

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

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

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

使用示例

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

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

輸入結果如下：

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]

結論

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