0

这是我到目前为止的地方：

我有以下用例（作为公正的 jUnit 测试）来展示我想要实现的目标：

buffer.add(o1);
assertEquals(1, buffer.size());
buffer.mark();
buffer.add(o2);
assertEquals(2, buffer.size());
buffer.add(o3);
assertEquals(3, buffer.size());
assertSame(o1, buffer.get());
assertSame(o2, buffer.get());
assertSame(o3, buffer.get());
buffer.rewind();
// NOTE: It must be possible to enter the same object multiple times
//       into the buffer.
buffer.add(o2);
assertSame(o2, buffer.get());
assertSame(o3, buffer.get());
assertSame(o2, buffer.get());

我尝试使用包装的列表（几乎重新发明了轮子）、包装的双队列（这完全是一团糟）来解决这个问题，而我刚刚失败的第三次尝试是一个包装的 LinkedList，在其中我得到了除倒带之外的所有其他工作（ ）。我最近尝试的伪代码是这样的：

if [backBuffer is empty]
    [get latest object]
    increment currentIndex
    if [markIndex < currentIndex]
        [put object to backbuffer]
    return object
else
    [get object from backbuffer at index backBufferIndex]
    increment backBufferIndex
    return object

这根本不起作用，经过一些编辑后，我设法开始阅读，直到 rewind() 被调用，所以基本上我第三次制作了一堆冗余代码。在这一点上我确实感到有点沮丧，因为我从来都不擅长算法，这就是我现在来找你的原因：请帮助我实现这个和/或指出我更正本机 Java API 解决方案，目前我只是感到难过，因为我无法让它发挥作用。

4

3 回答 3

1

您是否尝试过使用一些附加参数来包装其中一种 Java Collection 类型。

例如，创建一个包装 ArrayList 的新类。除了数组列表，保留私有成员变量

  • mark - 标记为倒带的最后一个索引
  • current - 在 get() 上检索的下一个索引

您还将添加以下方法

  • get() - 返回当前索引处的数组列表中的对象并递增当前
  • mark() - 将 mark 设置为 current 的值
  • rewind() - 将 current 设置为 mark 的值

还有一些细节需要解决（如何处理无效索引、最初设置的标记等），但这可能会给您一个良好的开端。

于 2009-09-06T18:28:33.507 回答
1

假设你有一个简单的 FIFO 对象，它实现add和get操作size，你可以用伪代码实现这个扩展的 FIFO，如下所示：

constructor()
{
    FIFO current = new FIFO();
    FIFO alternate = new FIFO();
}

add(Object x)
{
    return current.add(x);
}

get()
{
    Object x = current.get();
    alternate.add(x);
    return x;
}

size()
{
    return current.size();
}

mark()
{
    alternate = new FIFO();
}

rewind()
{
    while (current.size > 0)
    {
        alternate.add(current.get());
    }
    current = alternate;
    alternate = new FIFO();
}

我认为这是一个相当干净的实现。

于 2009-09-07T03:03:49.620 回答
0

您能否详细说明一下要求。我无法理解应该倒带做什么。是否应该添加自 mark() 以来添加的所有元素？

于 2009-09-06T18:24:41.377 回答