c# - 始终根据最新位置获取最旧数组索引的算法

Question

这几乎是一个不可能问的问题，但是任何关于算法的建议将不胜感激(我会尽我所能解释)；

我有一个大小为 ~4000 字节的数组，其中包含字节格式的数据。

对于这个演示，我将稍微简化一下；假设它的大小为 7(表示数据“ block ”，而不是单个值!)；

 |  0  |  1  |  2  |  3  |  4  |  5  |  6  |

我在位置 0 添加一个值，数组的重置为“0”

键:N = 最新，O = 最旧，X = 已填充

 |  N  |    |    |    |    |    |    | 

我现在需要添加另一个值。这将在下一个可用位置输入。

 |  O  |  N  |    |    |    |    |    | 

现在位置 [0] 是数组中“最旧”的部分，而位置 [1] 是最新的。

这已经(目前)通过一直寻找正确的方式解决，看不到任何值，然后从位置 [0] 开始直到它看到一个值。

让我们再添加一个:

 |  O  |  X  |  N  |    |    |    |    | 

请注意，最旧的值没有改变位置，因为它仍然是数组中最旧的部分。

我现在要“清除”数组中最旧的部分(在这个例子中它当前是 pos [0])。这使得“O”移动到下一个位置。

 |    |  O  |  N  |    |    |    |    | 

让我们添加另一个值。因为它会去第一个“空”空间，所以它会去位置 [0]；这意味着第一个位置现在位于位置 [0]。

 |  N  |  O  |  X  |    |    |    |    | 

我现在要清除另一个；再次，通过从最新值的右边看，我看到一个值在位置 1。所以我要清除它。

 |    |    |  O/N  |    |    |    |    | 

这意味着位置 [2] 现在是可用的最新值和最旧值。

添加另一个使；

 |  N  |    |  O  |    |    |    |    | 

添加另一个；

 |  X  |  N  |  O  |    |    |    |    | 

并添加另一个；

 |  X  |  X  |  O  |  N  |    |    |    | 

我现在想删除最旧的值。因此，通过从“最新”变量的位置向右看，我看到 pos[0] 有一个值，所以一定是它。 UH-OH 这不是最旧的值!

---

正如您(希望)所说，我无法通过向右查找我的下一个值来获得最早的票 - 这个问题只是偶尔发生，并且很难找到解决方案。

我只知道添加的最近值的索引，这很难找到解决方案。 (尝试了很多涂鸦和图表，很多弄皱的纸)。

因此，如果有人对我如何始终找到最旧值的索引有任何想法，我将不胜感激! (我也知道这是一个相当复杂的问题，所以如果有人想要/需要澄清，我会很乐意进一步编辑/解释!)我已经标记了 c#，但实际上我只需要一个 BASIC 算法来实现任何进展说实话!!!

============================================= =====================================

编辑

答案已建议分配到“最新”位置的右侧；喜欢:

 |    |    |  O  |  N  |     |     |    | 
 |    |    |  O  |  X  |  N  |     |    | 
 |    |    |  O  |  X  |  X  |  N  |    | 
 |    |    |  O  |  X  |  X  |  X  |  N |
 |  N |    |  O  |  X  |  X  |  X  |  X |  
 |  X |  N |  O  |  X  |  X  |  X  |  X | 

我认为这可以工作，但任何人都知道这是否会失败(比如，我在某个时间/等等删除了一个值？)

Answer 1

我猜你被迫使用数组；如果不是，那么您应该考虑切换到合适的数据结构，例如 Queue 。

如果你确实被迫使用数组，并且只能保留指向最新 block 的指针，那么我建议始终在最新 block 的右侧添加新 block ，索引在数组处回绕到零大小。

这使您可以通过查看最新 block 右侧的 block 来确定最旧的 block 是什么，直到找到一个非空 block :这是您最旧的 block 。将其清零以将其从数组中删除并继续:)

让我们举例说明:

 | N |   |   |   |   |   |   |   // newBlockIndex at 0, adding, newBlockIndex becomes 1
 | X | N |   |   |   |   |   |   // newBlockIndex at 1, adding, newBlockIndex becomes 2
 | X | X | N |   |   |   |   |   // newBlockIndex at 2, adding, newBlockIndex becomes 3
 |   | X | N |   |   |   |   |   // newBlockIndex at 3, removing, no item before index 0, we delete it
 |   | X | X | N |   |   |   |   // newBlockIndex at 3, adding, newBlockIndex becomes 4
...

编辑添加关于您的编辑，我认为该机制非常强大。即使您错误地删除了一个项目(任何项目，即使是最新的项目)，下一个操作也可以成功，因为 latest 和 newest 是根据它们在当前索引中的位置定义的。最新的项目位于索引左侧的第一个项目，最旧的项目位于右侧的第一个项目。

即使您不检查数组大小并完全填充它(尽管我不推荐这样做)，该算法也会用最新的项目覆盖最旧的项目:它可能不好，但与队列的概念。当然，如果数组已满，您总是可以决定分配一个更大的新数组并将当前数组复制到更大的数组