J'ai besoin de quelque chose comme une file d'attente limitée où je ne peux insérer que 10 éléments. Un nouvel élément doit remplacer le dernier élément inséré. Il ne devrait y avoir que n éléments distinctsQuelle structure de données dois-je utiliser pour suivre les éléments récemment utilisés?
Je suis à la recherche de suggestions en Java.
ITYM une implémentation d'un algorithme LRU.
@Rich B: C'était un manque intentionnel. Si les questions GIYF sont autorisées, elles devraient l'être aussi. Cependant, la raison de l'échec était que l'OP le découvre réellement. Vous ne vous attendez pas à ce que les FAQ soient répétées encore et encore, n'est-ce pas? – dirkgently
Ceci est une application classique pour une structure de données de file d'attente. Une pile de taille 10 garderait trace des 10 premiers éléments que vous y avez ajoutés, alors qu'une file d'attente de taille 10 garderait trace des 10 éléments les plus récents. Si vous recherchez une liste de «produits récents», comme suggéré par le titre de votre question, alors une file d'attente est la voie à suivre.
modifier: est un exemple ici, à des fins de visualisation:
Disons que vous voulez garder une trace des plus récents 4 articles, et vous accès à huit points dans l'ordre suivant:
F, O, R, T, Y, T, W, O
Voici ce que vos structures de données ressembleraient au fil du temps:
access item queue stack
1 F [ F . . . ] [ . . . F ]
2 O [ O F . . ] [ . . O F ]
3 R [ R O F . ] [ . R O F ]
4 T [ T R O F ] [ T R O F ]
5 Y [ Y T R O ] [ Y R O F ]
6 T [ T Y T R ] [ T R O F ]
7 W [ W T Y T ] [ W R O F ]
8 O [ O W T Y ] [ O R O F ]
La suppression de l'élément supérieur d'une pile supprime l'élément qui a été ajouté le plus récemment, pas l'élément le plus ancien. La suppression d'un élément d'une file d'attente supprime l'élément le plus ancien. Ainsi, votre file d'attente contient automatiquement les éléments les plus récents.
éditer: avec merci à Adam Jaskiewicz, voici quelques documents sur Java's Queue implementation.
Je sais que je devrais utiliser la file, je me demande si Java a le conteneur dont j'ai besoin ... –
Une file d'attente soutenue par un mécanisme pour garder la trace des accès multiples au même élément ... –
L'OP a dit: Un nouvel élément devrait remplacer le ** dernier ** élément inséré. C'est dernier entré, premier sorti. Il ne veut pas voir les 10 plus récents, à moins qu'il ait mal formulé sa question. –
Dernière ne veut pas dire plus ancienne. Dernier serait le plus récent. –
Votre question n'est pas claire. Voulez-vous que le nouvel élément remplace l'élément OLDEST ou le NEWEST? Et cherchez-vous USE (accès) ou INSERTION? –