Existe uma estrutura de dados existente com tamanho fixo e empurrará o elemento mais antigo / último se um novo elemento for inserido?

Estou procurando uma estrutura de dados que irá empurrar seu elemento mais antigo / último se um novo elemento for inserido. Por exemplo, vamos Drepresentar a estrutura. Dcontém 3 elementos dos Number Dvalores padrão do tipo serão inicializados para 1, 2e 3.

D = [1, 2, 3]

$D = [1, 2, 3]$

Se um Numberque contém o valor 5for inserido D, 3será empurrado para fora, enquanto 1e 2é deslocado para a direita.

D = [5, 1, 2]

$D = [5, 1, 2]$

A primeira coisa que vem à mente seria uma matriz, mas a definição não inclui o comportamento de empurrar.

data-structures arrays queues Greg M
fonte

Bem, não existe uma estrutura de dados embutida, mas é simples de implementar usando uma lista vinculada de lista com link duplo, certo?

Usuário não encontrado

Que tal usar um wrapper herdado de uma fila? Em seguida, você adicionar o método void push_replace(T val) { pop(); push(val); }.

Francesco Dondi

@FrancescoDondi provavelmente deveria serT push_replace(T val) { T old = pop(); push(val); return old; }

valbaca

Definitivamente existe agora: você apenas o definiu informalmente; talvez você deva perguntar se é bem conhecido, tem uma interface geralmente aceita e se há implementações disponíveis (não que a última seja um grande problema).

PJTraill

@valbaca Estou pensando em C ++, onde pop()não retorna nada devido a problemas com o desenrolamento da pilha, no caso de exceções ao copiar um objeto complexo, então você deve usá-lo front()antes, se precisar antes de descartar. Mas claro, se você não se importa com exceções, seu caminho pode ser melhor.

Francesco Dondi

Existe uma estrutura de dados existente com tamanho fixo e empurrará o elemento mais antigo / último se um novo elemento for inserido?

Respostas: