java - 帮我实现一个可倒带的缓冲区

Question

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

我有以下用例(作为公正的 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() 被调用，所以基本上我第三次制作了一堆冗余代码。在这一点上我确实感到有点沮丧，因为我从来都不擅长算法，这就是我现在来找你的原因:请帮助我实现这个和/或指出我纠正 native Java API 解决方案，目前我只是感到难过，因为我无法让它工作。

Answer 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();
}

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