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

20

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]

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]

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

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
1
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
1
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

Respostas:

44

Filas de tamanho fixo são frequentemente implementadas usando o que algumas pessoas chamam de buffers circulares . Se você remover a proteção contra a cheia, obtém o comportamento desejado.

Obviamente, nenhum empurrão real acontecerá no array - isso seria muito caro -, mas parecerá do lado de fora.

Rafael
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Raphael