我知道这个问题已经问过很多次了,但搜索一个小时后我仍然遇到问题。
我想使用一个 lifo 堆栈,它可以存储最大数量的元素。达到最大数量后,首先删除该元素并将其替换为新元素,这样在第一次弹出时我可以获取该元素并且第二步我必须获取 size-1 的元素。
我尝试过:
1) 使用修改后的堆栈,如所述 here问题是它总是返回我添加的前 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;
}
}
最佳答案
我认为最有效的方法是使用固定数组,其大小等于最大元素数,以及指向当前队列“顶部”元素的索引。
当您添加一个新元素时,您将其添加到索引+1处(如果需要,则回绕到元素0),并且可能会覆盖不再适合的元素。当您弹出一个元素时,您会执行相反的操作。
这样您的数据结构就不必重新排序,并且您可以使用比集合更轻量的数组。
关于具有元素限制的 Java 堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15840443/