Структура данных для скользящей истории позиции

Question

У меня есть приложение, считывающее значения смещения из внешнего источника данных.Эти смещения + - от центральной точки (ном = 0).

Я хотел бы сохранить последнюю минуту этих смещений и отобразить их на графике прокрутки.Этот график должен автоматически корректировать свои минимальные / максимальные значения в соответствии с данными за последнюю минуту.

Так что я вижу, что это указывает на очередь FIFO.

Я использую Delphi 7, однако при попытке использовать класс TQueue я не вижу никакого способа получить доступ к значению в очереди (а точнее, только к вершине очереди) с помощью Peek ().1008 * Есть ли лучшая структура данных для моей проблемы?

Мне нужно сохранить 60 чисел с плавающей запятой, получить доступ ко всем из них для отображения на графике и определить максимальное значение в очереди в любой момент времени.

Answer 1

Предостережение: я не знаю Delphi. Но в терминах, не зависящих от языка, вы можете просто поддерживать некоторый кольцевой буфер с соответствующим размером. Подкрепите его массивом, и ваш указатель записи будет циклически проходить по индексам массива. Ваши чтения начинаются с указателя записи, если буфер заполнен, иначе 0, если это не так.

Чтобы найти мин / макс, вы можете сделать несколько вещей:

1. Наивный подход: пересчитывать мин и макс каждый раз. На). (Не так уж плохо для n = 60.)
2. Немного лучше: пересчитывайте минимальное и максимальное значения только при минимальном или максимальном значении. (Конечно, вам нужно обновлять его и для каждого нажатия.) O (n).
3. Асимптотически хорошо: сохраняйте свои значения в самобалансирующемся бинарном дереве поиска. Вставьте в дерево, когда вы нажимаете на круговой буфер, и удалите из дерева, когда вы выталкиваете из буфера. O (log n).