Existe-t-il une structure de données existante de taille fixe qui repoussera l'élément le plus ancien / le dernier si un nouvel élément est inséré?

Je recherche une structure de données qui repoussera son élément le plus ancien / le dernier si un nouvel élément est inséré. Par exemple, Dreprésentons la structure. Dcontient 3 éléments des Number Dvaleurs par défaut du type seront initialisés à 1, 2et 3.

ré = [1, 2, 3]

$D = [1, 2, 3]$

Si un Numbercontenant la valeur 5est inséré dans D, 3sera poussé vers l'extérieur, tandis que 1et 2seront décalés vers la droite.

ré = [5, 1, 2]

$D = [5, 1, 2]$

La première chose qui vient à l'esprit serait un tableau, mais la définition n'inclut pas le comportement de poussée.

data-structures arrays queues Greg M
la source

Eh bien, il n'y a pas de structure de données intégrée, mais il est simple à mettre en œuvre en utilisant une liste chaînée à double liste, n'est-ce pas?

Utilisateur introuvable

Qu'en est-il de l'utilisation d'un wrapper héritant d'une file d'attente? Ensuite, vous ajoutez la méthode void push_replace(T val) { pop(); push(val); }.

Francesco Dondi

@FrancescoDondi devrait probablement êtreT push_replace(T val) { T old = pop(); push(val); return old; }

valbaca

Il y en a certainement maintenant: vous venez de le définir de manière informelle; vous devriez peut-être demander si elle est bien connue, a une interface généralement acceptée et si des implémentations sont disponibles (pas que la dernière soit un gros problème).

PJTraill

@valbaca Je pense au C ++ où pop()ne retourne rien en raison de problèmes avec le déroulement de la pile en cas d'exceptions copiant un objet complexe, vous êtes donc censé l'utiliser front()avant si vous en avez besoin avant de le jeter. Mais bien sûr, si vous ne vous souciez pas des exceptions, votre chemin peut être meilleur.

Francesco Dondi

Existe-t-il une structure de données existante de taille fixe qui repoussera l'élément le plus ancien / le dernier si un nouvel élément est inséré?

Réponses: