Quelle implémentation de file d'attente utiliser en Java?

Question

J'ai besoin d'utiliser une structure FIFO dans mon application. Il doit avoir au plus 5 éléments. Je voudrais avoir quelque chose de facile à utiliser (je ne me soucie pas de la simultanéité) qui implémente l'interface de collection.

J'ai essayé le LinkedList, qui semble provenir de la file d'attente, mais il ne semble pas me permettre de définir sa capacité maximale. Il me semble que je veux juste au maximum 5 éléments mais j'essaie d'en ajouter 20, ça va juste continuer à augmenter en taille pour l'adapter. Je voudrais quelque chose qui travaillerait de la façon suivante:

XQueue<Integer> queue = new XQueue<Integer>(5); //where 5 is the maximum number of elements I want in my queue. 
for (int i = 0; i < 10; ++i) { 
    queue.offer(i); 
} 

for (int i = 0; i < 5; ++i) { 
    System.out.println(queue.poll()); 
} 

Ce serait imprimé:

5 
6 
7 
8 
9 

Merci

Answer 1

Créer votre propre sous-classe de celui que vous voulez, et passer outre la ajouter la méthode de sorte qu'il

• vérifie si le nouvel objet s'adaptera et échoue sinon
• appels super.add()

(et les constructeurs).

Si vous voulez le bloquer lors de l'insertion s'il est plein, c'est différent.

Answer 2

On dirait que ce que vous voulez est une structure FIFO de taille limitée, qui expulse les éléments les plus anciens lorsque de nouveaux sont ajoutés. Je recommande une solution basée sur une implémentation de tableau cyclique, où vous devez suivre l'index de la queue queue et la tête de la file d'attente, et les augmenter (de manière cyclique) selon les besoins.

EDIT: Voici ma mise en œuvre (notez que c'est une collection). Cela fonctionne bien avec votre scénario de test.

public class XQueue <T> extends AbstractQueue<T>{ 
    private T[] arr; 
    private int headPos; 
    private int tailPos; 
    private int size; 

    @SuppressWarnings("unchecked") 
    public XQueue(int n){ 
     arr = (T[]) new Object[n]; 
    } 

    private int nextPos(int pos){ 
     return (pos + 1) % arr.length; 
    } 

    @Override 
    public T peek() { 
     if (size == 0) 
      return null; 
     return arr[headPos]; 
    } 

    public T poll(){ 
     if (size == 0) 
      return null; 
     size--; 
     T res = arr[headPos]; 
     headPos = nextPos(headPos);  
     return res; 
    } 

    @Override 
    public boolean offer(T e) { 
     if (size < arr.length) 
      size++; 
     else 
      if (headPos == tailPos) 
       headPos = nextPos(headPos); 
     arr[tailPos] = e; 
     tailPos = nextPos(tailPos); 
     return true; 
    } 

    @Override 
    public Iterator<T> iterator() { 
     return null; //TODO: Implement 
    } 

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

Answer 3

Je n'ai vu aucune limitation comme celle de l'API. Vous pouvez utiliser ArrayList en modifiant le comportement de la méthode add avec la fonctionnalité de classe anonyme:

new ArrayList<Object>(){ 
    public boolean add(Object o){ /*...*/ } 
} 

Answer 4

Peut-être un ArrayBlockingQueue pourrait faire l'affaire. Regardez here. Essayez quelque chose comme ceci:

BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(5); 

for (int i = 0; i < 10; i++) { 
    while (!queue.offer(i)) { 
    queue.poll();   
    } 
} 

for (int i = 0; i < 5; i++) { 
    System.out.println(queue.poll()); 
} 

Answer 5

Vous avez trois choix

1) Subclass an Abstract Collection

2) Limiter la taille à cinq et faire la logique autour du code où vous faites l'insert.

3) Utiliser LinkedListHashMap La méthode removeEldestEntry (Map.Entry) peut être substituée pour imposer une politique de suppression automatique des mappages périmés lorsque de nouveaux mappages sont ajoutés à la carte. (Vous utiliserez alors un Iterator pour obtenir les valeurs - qui seront retournées dans l'ordre d'insertion)

Votre meilleur pari est # 1 - C'est vraiment facile si vous regardez le lien.

Answer 6

Avez-vous regardé la bibliothèque Apache Commons Collections?Le BoundedFifoBuffer devrait répondre exactement à vos besoins.

Answer 7

Si je me souviens bien, j'ai fait exactement ce que vous voulez en utilisant une LinkedList.

Ce que vous devez faire est de vérifier la taille de la liste, si elle est 5 et que vous voulez ajouter des objets, il suffit de supprimer le premier élément et continuer à le faire si la taille est 5.