Potrzebuję kolejki o stałym rozmiarze. Kiedy dodam element, a kolejka jest pełna, powinna automatycznie usunąć najstarszy element.

Czy istnieje taka implementacja w Javie?

Nie ma istniejącej implementacji w języku Java i środowisku wykonawczym. Wszystkie kolejki rozszerzają AbstractQueue , a jego dokument jasno stwierdza, że ​​dodanie elementu do pełnej kolejki zawsze kończy się wyjątkiem. Najlepszym rozwiązaniem (i całkiem prostym) byłoby umieszczenie kolejki we własnej klasie, aby mieć potrzebną funkcjonalność.

Ponownie, ponieważ wszystkie kolejki są dziećmi AbstractQueue, po prostu użyj tego jako wewnętrznego typu danych i powinieneś mieć elastyczną implementację działającą praktycznie w mgnieniu oka :-)

AKTUALIZACJA:

Jak opisano poniżej, dostępne są dwie otwarte implementacje (ludzie, ta odpowiedź jest dość stara!) . Szczegółowe informacje można znaleźć w tej odpowiedzi .

Właściwie LinkedHashMap robi dokładnie to, co chcesz. Musisz nadpisać removeEldestEntrymetodę.

Przykład kolejki z maksymalnie 10 elementami:

  queue = new LinkedHashMap<Integer, String>()
  {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
     {
        return this.size() > 10;   
     }
  };

Jeśli „removeEldestEntry” zwróci wartość true, najstarszy wpis zostanie usunięty z mapy.

Tak, dwa

Z mojego zduplikowanego pytania z tą poprawną odpowiedzią dowiedziałem się o dwóch:

• EvictingQueuew Google Guava
• CircularFifoQueuew Apache Commons

Robiłem produktywny użytek z guawy EvictingQueue , pracowałem dobrze.

Aby utworzyć wystąpienie EvictingQueuewywołania statycznej metody fabryki createi określić maksymalny rozmiar.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 

Właśnie zaimplementowałem kolejkę o stałym rozmiarze w ten sposób:

public class LimitedSizeQueue<K> extends ArrayList<K> {

    private int maxSize;

    public LimitedSizeQueue(int size){
        this.maxSize = size;
    }

    public boolean add(K k){
        boolean r = super.add(k);
        if (size() > maxSize){
            removeRange(0, size() - maxSize);
        }
        return r;
    }

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}

To jest to, co zrobiłem z Queueopakowaniem LinkedList, ma stały rozmiar, który podam tutaj to 2;

public static Queue<String> pageQueue;

pageQueue = new LinkedList<String>(){
            private static final long serialVersionUID = -6707803882461262867L;

            public boolean add(String object) {
                boolean result;
                if(this.size() < 2)
                    result = super.add(object);
                else
                {
                    super.removeFirst();
                    result = super.add(object);
                }
                return result;
            }
        };


....
TMarket.pageQueue.add("ScreenOne");
....
TMarket.pageQueue.add("ScreenTwo");
.....

Myślę, że to, co opisujesz, to cykliczna kolejka. Oto przykład i tutaj jest lepszy jeden

Ta klasa spełnia swoje zadanie, wykorzystując kompozycję zamiast dziedziczenia (inne odpowiedzi tutaj), co eliminuje możliwość wystąpienia pewnych skutków ubocznych (opisanych przez Josha Blocha w Essential Java). Przycinanie podstawowej LinkedList odbywa się w metodach add, addAll i offer.

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LimitedQueue<T> implements Queue<T>, Iterable<T> {

    private final int limit;
    private final LinkedList<T> list = new LinkedList<T>();

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

    private boolean trim() {
        boolean changed = list.size() > limit;
        while (list.size() > limit) {
            list.remove();
        }
        return changed;
    }

    @Override
    public boolean add(T o) {
        boolean changed = list.add(o);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return list.contains(o);
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return list.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean changed = list.addAll(c);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean offer(T e) {
        boolean changed = list.offer(e);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public T remove() {
        return list.remove();
    }

    @Override
    public T poll() {
        return list.poll();
    }

    @Override
    public T element() {
        return list.element();
    }

    @Override
    public T peek() {
        return list.peek();
    }
}

public class CircularQueue<E> extends LinkedList<E> {
    private int capacity = 10;

    public CircularQueue(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean add(E e) {
        if(size() >= capacity)
            removeFirst();
        return super.add(e);
    }
}

Użytkowanie i wynik testu:

public static void main(String[] args) {
    CircularQueue<String> queue = new CircularQueue<>(3);
    queue.add("a");
    queue.add("b");
    queue.add("c");
    System.out.println(queue.toString());   //[a, b, c]

    String first = queue.pollFirst();       //a
    System.out.println(queue.toString());   //[b,c]

    queue.add("d");
    queue.add("e");
    queue.add("f");
    System.out.println(queue.toString());   //[d, e, f]
}

Brzmi jak zwykła lista, w której metoda add zawiera dodatkowy fragment kodu, który obcina listę, jeśli stanie się zbyt długa.

Jeśli jest to zbyt proste, prawdopodobnie konieczna będzie edycja opisu problemu.

Zobacz także to pytanie SO lub ArrayBlockingQueue (uważaj na blokowanie, może to być niepożądane w twoim przypadku).

Nie jest do końca jasne, jakie masz wymagania, które skłoniły Cię do zadania tego pytania. Jeśli potrzebujesz struktury danych o stałym rozmiarze, możesz również przyjrzeć się różnym zasadom buforowania. Ponieważ jednak masz kolejkę, przypuszczam, że szukasz jakiejś funkcji routera. W takim przypadku wybrałbym bufor pierścieniowy: tablicę, która ma pierwszy i ostatni indeks. Za każdym razem, gdy dodawany jest element, po prostu zwiększasz indeks ostatniego elementu, a gdy element jest usuwany, zwiększasz indeks pierwszego elementu. W obu przypadkach dodawanie jest wykonywane modulo rozmiar tablicy i upewnij się, że w razie potrzeby zwiększasz inny indeks, to znaczy, gdy kolejka jest pełna lub pusta.

Ponadto, jeśli jest to aplikacja typu routera, możesz również poeksperymentować z algorytmem, takim jak Random Early Dropping (RED), który losowo usuwa elementy z kolejki, zanim zostanie ona zapełniona. W niektórych przypadkach RED ma lepszą ogólną wydajność niż prosta metoda pozwalająca na zapełnienie kolejki przed upuszczeniem.

Właściwie możesz napisać swój własny plik Impl oparty na LinkedList, jest to całkiem proste, po prostu zastąp metodę add i wykonaj pięciolinię.

Myślę, że najbardziej pasująca odpowiedź pochodzi z tego innego pytania .

Apache commons collections 4 ma CircularFifoQueue, którego szukasz. Cytując javadoc:

CircularFifoQueue to kolejka pierwszy na wejściu o stałym rozmiarze, która zastępuje najstarszy element, jeśli jest pełny.

Proste rozwiązanie, poniżej znajduje się kolejka „Ciąg”

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

queue.put(queueKeysCounter++, "My String");
queueKeysCounter %= QUEUE_SIZE;

Zauważ, że nie zachowa to kolejności elementów w kolejce, ale zastąpi najstarszy wpis.

Zgodnie z zaleceniami w programach OOP, powinniśmy preferować kompozycję zamiast dziedziczenia

Oto moje rozwiązanie, mając to na uwadze.

package com.choiceview;

import java.util.ArrayDeque;

class Ideone {
    public static void main(String[] args) {
        LimitedArrayDeque<Integer> q = new LimitedArrayDeque<>(3);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q);

        q.add(4);
        // First entry ie 1 got pushed out
        System.out.println(q);
    }
}

class LimitedArrayDeque<T> {

    private int maxSize;
    private ArrayDeque<T> queue;

    private LimitedArrayDeque() {

    }

    public LimitedArrayDeque(int maxSize) {
        this.maxSize = maxSize;
        queue = new ArrayDeque<T>(maxSize);
    }

    public void add(T t) {
        if (queue.size() == maxSize) {
            queue.removeFirst();
        }
        queue.add(t);
    }

    public boolean remove(T t) {
        return queue.remove(t);
    }

    public boolean contains(T t) {
        return queue.contains(t);
    }

    @Override
    public String toString() {
        return queue.toString();
    }
}