1

我打算做一个小程序，它会显示一个每秒更新几次的图表（可能是 100/200 毫秒左右）。目的是在图中绘制 1000 多个不同的值，有点像 XY 图。

当数组包含 1000 个元素时，我想在最后添加一个新元素，并在此过程中将所有其他元素向后推。本质上，元素 999 会变成 998，而 998 会变成 997……一直到第一个元素，它会被简单地丢弃。有没有人有一个例子或一个好的算法来做到这一点，无论是使用常规数组、Vector、LinkedList 还是任何其他方法？

我的第一个想法是创建一个新数组并将我想要保留的元素复制到新数组中，扔掉前 100 个元素。此时，我将在数组末尾添加新的 100 个元素，并不断重复此过程，但肯定有更好的方法吗？

4

3 回答 3

1

您所问的是算法世界中的双端队列，即双端向量。

这就是你需要的课程。

基本上 deque 支持从序列的开头和结尾添加和删除元素。

编辑实际上，当我阅读文档时，我惊讶地发现 deque 的 sdk 实现不支持直接索引（我习惯于在 C++ 中使用这种结构）。所以我继续搜索并找到了这个答案，链接到这个库，这可能对你有帮助。

于 2012-04-21T18:36:28.737 回答
1

不要使用数组，移动所有元素的复杂性是可怕的！我想说，最适合这项任务的 Java 数据结构是Deque 。

于 2012-04-21T18:36:39.903 回答
0

我会继续重用同一个数组，然后从头开始。为了让自己更清楚，假设您的数组包含元素 1..1000

int[] array =  new int[1000];
...
array = {1, 2, ...., 1000 };

如果您现在必须添加元素 1001，而不是尝试使用数组 {2, 3, ..., 1000, 1001}，我会选择数组 {1001, 2, 3, ... 1000}跟踪我的数组实际从哪个索引开始。这通过在开始索引处保留一个简单的计数器来代替移动所有元素的困难。为了方便自己，您可以引入一个实用方法

private int startIndex = 1;//0 at the start
//I assume we are in the situation with array {1001, 2, 3, ..., 1000 }

public int convertIndex( int index ){
  return (index + startIndex) % 1000;
}
于 2012-04-21T18:49:27.043 回答