Существует ли существующая структура данных фиксированного размера, которая вытеснит самый старый / последний элемент, если будет добавлен новый элемент?

Я ищу структуру данных, которая вытолкнет его самый старый / последний элемент, если новый элемент будет вставлен. Например, давайте Dпредставим структуру. Dсодержит 3 элемента типа Number Dзначения по умолчанию будут инициализированы в 1, 2и 3.

D знак равно [1, 2, 3]

$D = [1, 2, 3]$

Если элемент Number, содержащий значение 5, вставлен в D, 3будет вытолкнут, а 1и 2смещены вправо.

D знак равно [5, 1, 2]

$D = [5, 1, 2]$

Первое, что приходит на ум, это массив, но определение не включает в себя поведение нажатия.

data-structures arrays queues Грег М
источник

Ну, нет встроенной структуры данных, но это легко реализовать с помощью двухсвязного связанного списка, верно?

Пользователь не найден

Как насчет использования оболочки, наследующей от очереди? Затем вы добавляете метод void push_replace(T val) { pop(); push(val); }.

Франческо Донди

@FrancescoDondi, вероятно, должно бытьT push_replace(T val) { T old = pop(); push(val); return old; }

valbaca

Там определенно есть сейчас: вы просто неофициально определили это; возможно, вам следует спросить, хорошо ли он известен, имеет ли он общепринятый интерфейс и доступны ли реализации (не то, что последнее является большой проблемой).

PJTraill

@valbaca Я думаю о C ++, где pop()ничего не возвращается из-за проблем с размоткой стека в случае исключений, копирующих сложный объект, так что вы должны использовать его front()раньше, если он вам нужен, прежде чем отбрасывать. Но конечно, если вас не волнуют исключения, ваш путь может быть лучше.

Франческо Донди

Ответы:

Очереди фиксированного размера часто реализуются с использованием того, что некоторые люди называют циклическими буферами . Если вы снимите защиту от переполнения, вы получите желаемое поведение.

Конечно, в массиве не произойдет никакого реального нажатия - это будет слишком дорого - но это будет выглядеть как снаружи.

Рафаэль
источник

Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .

Рафаэль