Ukuran-antrian terbatas yang menampung elemen N terakhir di Jawa

Sebuah pertanyaan yang sangat sederhana & cepat di perpustakaan Java: apakah ada kelas yang sudah jadi yang mengimplementasikan a Queuedengan ukuran maksimum tetap - yaitu selalu memungkinkan penambahan elemen, tetapi akan secara diam-diam menghapus elemen kepala untuk mengakomodasi ruang untuk elemen yang baru ditambahkan.

Tentu saja, sangat mudah untuk mengimplementasikannya secara manual:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

Sejauh yang saya lihat, tidak ada implementasi standar di stdlibs Java, tetapi mungkin ada satu di Apache Commons atau sesuatu seperti itu?

Koleksi Apache commons 4 memiliki CircularFifoQueue <> yang Anda cari. Mengutip javadoc:

CircularFifoQueue adalah antrian masuk pertama keluar dengan ukuran tetap yang menggantikan elemen tertua jika penuh.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

Jika Anda menggunakan versi yang lebih lama dari koleksi Apache commons (3.x), Anda dapat menggunakan CircularFifoBuffer yang pada dasarnya adalah hal yang sama tanpa obat generik.

Pembaruan : jawaban yang diperbarui setelah rilis koleksi commons versi 4 yang mendukung obat generik.

Guava sekarang memiliki EvictingQueue , antrian non-pemblokiran yang secara otomatis mengusir elemen dari kepala antrian ketika mencoba untuk menambahkan elemen baru ke dalam antrian dan penuh.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]

Saya suka solusi @FractalizeR. Tapi saya juga akan menyimpan dan mengembalikan nilai dari super.add (o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

Gunakan komposisi tidak meluas (ya maksudku meluas, seperti dalam referensi ke kata kunci meluas di java dan ya ini adalah warisan). Komposisi lebih unggul karena sepenuhnya melindungi implementasi Anda, memungkinkan Anda untuk mengubah implementasi tanpa berdampak pada pengguna kelas Anda.

Saya sarankan mencoba sesuatu seperti ini (saya mengetik langsung ke jendela ini, jadi pembeli waspada terhadap kesalahan sintaksis):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Opsi yang lebih baik (berdasarkan jawaban oleh Asaf) mungkin untuk membungkus Apache Collections CircularFifoBuffer dengan kelas generik. Sebagai contoh:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

Satu-satunya hal yang saya tahu yang memiliki ruang terbatas adalah antarmuka BlockingQueue (yang misalnya diimplementasikan oleh kelas ArrayBlockingQueue) - tetapi mereka tidak menghapus elemen pertama jika diisi, tetapi sebaliknya memblokir operasi put sampai ruang bebas (dihapus oleh utas lainnya) ).

Sepengetahuan saya implementasi sepele Anda adalah cara termudah untuk mendapatkan perilaku seperti itu.

Anda dapat menggunakan MinMaxPriorityQueue dari Google Guava , dari javadoc:

Antrian prioritas min-max dapat dikonfigurasi dengan ukuran maksimum. Jika demikian, setiap kali ukuran antrian melebihi nilai itu, antrian secara otomatis menghapus elemen terbesarnya sesuai dengan pembandingnya (yang mungkin merupakan elemen yang baru saja ditambahkan). Ini berbeda dari antrian terbatas konvensional, yang memblokir atau menolak elemen baru saat penuh.

LRUMap adalah kemungkinan lain, juga dari Apache Commons.

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html

    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}