0

我知道这个问题已经问了很多次,但是搜索了一个小时后我仍然有问题。

我想使用一个 lifo 堆栈,它可以存储最大数量的元素。达到最大数量后,首先删除元素并将其替换为新元素,因此在第一个 pop 中我可以获得这个元素,在第二个我必须获得 size-1 的元素。

我尝试了什么:

1)使用修改后的堆栈,如此处所述问题是它总是返回我添加的前 5 个元素(如果大小为 5)。

class StackSizable<E> extends Stack<E>{

    int maxSize;
    StackSizable(int size)
    {
        super();
        this.maxSize=size;
    }

    @Override
    public E push(E elt) {
        super.push(elt);
        while (this.size() > this.maxSize) {
            this.removeElementAt(this.size() - 1);
        }
        return null;
    }
}

2)使用 ArrayDeque ,我看不出与简单 Stack 有任何区别,它没有设置任何限制(我用错了吗?)

ArrayDeque<State> lifo = new ArrayDeque<State>(5);
lifo.pop();
lifo.push(state);

我想在益智游戏中使用它来实现撤消重做功能

已解决:正如汤姆所说,我最终使用了固定大小的堆栈,主要是为了性能

public class FixedStack<T> { private T[] stack; private int size; private int top; private int popBalance = 0;//its used to see if all the elements have been popped public FixedStack(T[] stack) { this.stack = stack; this.top = 0; this.size = stack.length; } public void push(T obj) { if (top == stack.length)top = 0; stack[top] = obj; top++; if (popBalance < size - 1)popBalance++; } public T pop() { if (top - 1 < 0)top = size; top--; T ob = stack[top]; popBalance--; return ob; } public void clear() { top = 0; } public int size() { return size; } public boolean poppedAll() { if (popBalance == -1)return true; return false; } }
4

2 回答 2

4

我认为最有效的方法是使用一个固定数组,其大小等于您的最大元素数,以及一个指向当前队列“顶部”元素的索引。

当你添加一个新元素时,你在 index+1 处添加它(如果需要,返回到元素 0)并可能覆盖不再适合的元素。当你弹出一个元素时,你会做相反的事情。

这样,您的数据结构就不必重新排序,并且您可以使用比集合更轻量的数组。

于 2013-04-05T18:08:14.193 回答
3

当达到最大尺寸时,您的线路

this.removeElementAt(this.size() - 1);

然后立即删除最后推送的元素(您刚刚推送的),这是堆栈的顶部。您需要删除第一个元素(堆栈底部):

this.removeElementAt(0);
于 2013-04-05T18:01:32.157 回答