J'ai besoin d'une file d'attente de taille fixe. Lorsque j'ajoute un élément et que la file d'attente est pleine, elle doit automatiquement supprimer l'élément le plus ancien.

Existe-t-il une implémentation pour cela en Java?

Il n'existe aucune implémentation existante dans le langage Java et le Runtime. Toutes les files d'attente étendent AbstractQueue , et son document indique clairement que l'ajout d'un élément à une file d'attente complète se termine toujours par une exception. Il serait préférable (et assez simple) d'envelopper une file d'attente dans une classe à vous pour avoir les fonctionnalités dont vous avez besoin.

Encore une fois, comme toutes les files d'attente sont des enfants de AbstractQueue, utilisez simplement cela comme type de données interne et vous devriez avoir une implémentation flexible en un rien de temps :-)

METTRE À JOUR:

Comme indiqué ci-dessous, il existe deux implémentations ouvertes disponibles (cette réponse est assez ancienne, les amis!), Voir cette réponse pour plus de détails.

En fait, LinkedHashMap fait exactement ce que vous voulez. Vous devez remplacer la removeEldestEntryméthode.

Exemple pour une file d'attente de 10 éléments maximum:

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

Si "removeEldestEntry" renvoie true, l'entrée la plus ancienne est supprimée de la carte.

Oui, deux

De ma propre question en double avec cette réponse correcte , j'ai appris deux:

• EvictingQueuedans Google Guava
• CircularFifoQueuedans Apache Commons

J'ai fait un usage productif de la goyave EvictingQueue, j'ai bien travaillé.

Pour instancier un EvictingQueueappel, la méthode de fabrique statique createet spécifiez votre taille maximale.

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

Je viens d'implémenter une file d'attente de taille fixe de cette façon:

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

C'est ce que j'ai fait avec Queueenveloppé avec LinkedList, il est de taille fixe que je donne ici est 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");
.....

Je pense que ce que vous décrivez est une file d'attente circulaire. Voici un exemple et voici une meilleure une

Cette classe fait le travail en utilisant la composition au lieu de l'héritage (autres réponses ici), ce qui supprime la possibilité de certains effets secondaires (comme couvert par Josh Bloch dans Essential Java). Le rognage de la LinkedList sous-jacente se produit sur les méthodes add, addAll et 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);
    }
}

Utilisation et résultat du test:

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]
}

Sonne comme une liste ordinaire où la méthode add contient un extrait de code supplémentaire qui tronque la liste si elle devient trop longue.

Si cela est trop simple, vous devrez probablement modifier la description de votre problème.

Voir également cette question SO , ou ArrayBlockingQueue ( faites attention au blocage, cela peut être indésirable dans votre cas).

Les exigences que vous avez qui vous ont amené à poser cette question ne sont pas très claires. Si vous avez besoin d'une structure de données de taille fixe, vous pouvez également envisager différentes stratégies de mise en cache. Cependant, comme vous avez une file d'attente, ma meilleure supposition est que vous recherchez un type de fonctionnalité de routeur. Dans ce cas, j'irais avec un tampon en anneau: un tableau qui a un premier et un dernier index. Chaque fois qu'un élément est ajouté, vous incrémentez simplement le dernier index d'élément, et lorsqu'un élément est supprimé, incrémentez le premier index d'élément. Dans les deux cas, l'ajout est effectué en fonction de la taille du tableau, et veillez à incrémenter l'autre index si nécessaire, c'est-à-dire lorsque la file d'attente est pleine ou vide.

De plus, s'il s'agit d'une application de type routeur, vous pouvez également essayer un algorithme tel que Random Early Dropping (RED), qui supprime des éléments de la file d'attente de manière aléatoire avant même qu'elle ne se remplisse. Dans certains cas, RED s'est avéré avoir de meilleures performances globales que la méthode simple permettant à la file d'attente de se remplir avant de tomber.

En fait, vous pouvez écrire votre propre impl basé sur LinkedList, c'est assez simple, il suffit de remplacer la méthode add et de faire le personnel.

Je pense que la meilleure réponse correspondante vient de cette autre question .

Apache commons collections 4 a un CircularFifoQueue qui est ce que vous recherchez. Citant le javadoc:

CircularFifoQueue est une file d'attente premier entré, premier sorti avec une taille fixe qui remplace son élément le plus ancien s'il est plein.

Une solution simple, ci-dessous est une file d'attente de "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

Notez que cela ne maintiendra pas l'ordre des éléments dans la file d'attente, mais remplacera l'entrée la plus ancienne.

Comme indiqué dans les POO, nous devrions préférer la composition à l'héritage

Voici ma solution en gardant cela à l'esprit.

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