data-structures - 可从任何地方读取的类似队列的数据结构

Question

我正在 Yoyo Game Maker 中开发一款游戏，其中我的元素沿着传送带移动。由于项目只朝一个方向移动，我认为使用队列或类似队列的数据结构来存储项目最有意义。但是，为了能够呈现项目，我需要能够在队列中的任何位置读取所有项目，而不仅仅是头部或尾部。

     [[a] [b] [c] [d]]
             |
             V

a <- [[ ] [b] [c] [d]] <- e
             |
             V

     [[b] [c] [d] [e]]
       |   |   |   |
       V   V   V   V

       b   c   d   e

我可以简单地使用一个数组，该数组每一轮手动将其所有值向前移动一个槽(使用 for 循环)，但不知何故，这似乎效率低下、滞后，或者至少是糟糕的形式。无论如何，一想到使用这样的系统，我的编程本能就会退缩。

这是一个正确的假设吗？数组真的是实现这种结构的最佳方式吗？我什至应该担心效率，还是这种情况下的差异可以忽略不计？

一些建议或示例(在任何编程语言中)将不胜感激。

Answer 1

使用数组可能“看起来”效率低下，但很可能并非如此。考虑在任何时候传送带上实际有多少元素。如果您想快速随机访问数据结构中的任何索引，则必须使用数组、DS 列表或 DS 网格(这里没有意义，很难)。

使用 DS 列表，您可以使用 ds_list_delete(your_list, 0) 来“出列”，就像 DS 队列一样，以及 ds_list_insert(your_list, 0, value) 将项目“入队”。

遍历列表就非常简单了:

for ( var i = 0; i < ds_list_size( your_list ); i++ ) {
   var item = your_list[|i];
}

可能还需要补充一点，在我正在开发的游戏中，对象是使用组件构建的，这基本上意味着所有敌人、玩家等在他们的步骤中都有一个 for 循环事件迭代并在需要时更新所有组件。我在游戏中最多有大约 80 个这样的对象，而且性能还不是问题。

您应该始终首先尝试获得一个有效的解决方案，然后在特定于您的游戏的条件下对其进行测试:例如。如果你打算在结构中需要 100 个项目，试试那个，如果性能不令人满意，然后再优化。