滚动历史记录的数据结构

Question

我有一个应用程序读取外部数据源的偏移值.这些偏移量是+ - 从中​​心点(nom = 0).

我想保存这些偏移的最后一分钟并将它们显示在滚动图上.该图需要根据最后一分钟的数据自动调整其最小/最大值.

所以我可以看到这指向FIFO队列.

我正在使用Delphi 7,但是当尝试使用TQueue类时,我无法使用Peek()查看任何访问队列中的值(而只是队列的顶部)的方法.

我的问题有更好的数据结构吗？

我需要存储60个浮点数,访问所有这些数字以显示在图表上,并确定队列中任何时间点的最大值.

Answer 1

警告:我不知道德尔福.但是在语言不可知的术语中,您可以维护某种具有适当大小的循环缓冲区.用数组返回它,让你的写指针循环遍历数组索引.如果缓冲区已填满,则从写指针开始读取,否则返回0.

要查找最小值/最大值,您可以执行以下操作:

1. 天真的方法:每次重新计算最小值和最大值.上).(n = 60也不错.)
2. 稍微好一些:只有在弹出最小值或最大值时重新计算最小值和最大值.(当然你也需要为每次推送更新它.)O(n).
3. 渐近好:将您的值保存在自平衡二叉搜索树中.当您从缓冲区弹出时,在推入循环缓冲区时插入树中并从树中删除.O(log n).