创建固定大小的堆栈

问题描述：

我想用Java创建堆栈，但修复了大小。例如，创建一个新的堆栈，将大小设置为10，然后当我将物品推入堆栈时，它会填满，当它填充到10时，堆栈中的最后一个物品被推出（移除）。我想使用Stack，因为它使用LIFO并且非常适合我的需求。创建固定大小的堆栈

但Stack从Vector继承的setSize（）方法似乎实际上并未限制堆栈的大小。我想我错过了Stacks的工作方式，或者Stacks不是被限制的，所以这是不可能的。请教育我！

仅供参考setSize方法从Vector继承，这意味着setSize将导致添加null以填充提供的新大小，或者丢弃超出新大小的现有对象。你可以在理论上使用这个if（stack.size（）> = 10）{stack.setSize（10）; }每当你推入堆栈，但它会更好地实现自己的自定义类。 – Thor84no

我最初试过这个只是为了看看它是否会工作。这很奇怪，但是好像当我在堆栈上执行setSize（）时，它会颠倒项目的顺序并从那里截断它们。所以我总是最终得到原来的10个物品。同样，另一个快速/脏的方法是（stack.size（）> = 10）{stack.remove（0）; }同样的问题出现在它颠倒顺序的地方，所以出于某种原因，0索引是要删除的索引。 – koopaking3

这可能意味着底层的实现实际上是这样工作的，堆栈方法以相反的顺序返回给你，这无论如何都有很大的意义。 – Thor84no

答

您可以创建一个非常简单的堆栈是这样的：

public class FixedStack<T> 
{ 
    private T[] stack; 
    private int size; 
    private int top; 

    public FixedStack<T>(int size) 
    { 
     this.stack = (T[]) new Object[size]; 
     this.top = -1; 
     this.size = size; 
    } 

    public void push(T obj) 
    { 
     if (top >= size) 
      throw new IndexOutOfBoundsException("Stack size = " + size); 
     stack[++top] = obj; 
    } 

    public T pop() 
    { 
     if (top < 0) throw new IndexOutOfBoundsException(); 
     T obj = stack[top--]; 
     stack[top + 1] = null; 
     return obj; 
    } 

    public int size() 
    { 
     return size; 
    } 

    public int elements() 
    { 
     return top + 1; 
    } 
}

我最终做了类似这样的事情。谢谢！ – koopaking3

这里有潜在的内存泄漏。 – mre

@mre：好的。等一下。我会解决的。完成。这是你的意思吗？ –

答

您可以继承Stack并重写相应的方法来实现此自定义行为。并确保给它一个明确的名称（例如FixedStack）。

答

纯粹的堆栈不会限制它的大小，因为许多问题堆栈解决了你不知道你需要多少元素。

您可以编写一个自定义堆栈来实现您描述的需求。但是，如果你这样做，你会打破LIFO。如果满足最大尺寸，并且您在堆叠上推新的东西，则会丢失之前添加的项目。所以如果你开始从你的堆栈中弹出物品，你会错过一些。

答

A LinkedBlockingDeque是一个简单的选项。使用LinkedBlockingQueue(int)构造函数，其中参数是您的堆栈限制。

如你观察到的，和Stack模型Vector无界序列。 setSize()方法会截断堆栈/向量。它不会阻止数据结构的增长超过这个规模。

'LinkedBlockingDequeue'是一个不错的选项（+1），但是当达到限制时它不会接受新项目。如果我正确理解OP，队列/堆栈应该只包含最新的10个元素，所以您仍然必须实现该自动删除。 – Thomas

@Thomas - 如果使用'add'方法，您会得到异常。但是，这不符合OP的要求。 –

答

您需要的是像LinkedList这样的双端队列。虽然这不会自动删除前面的元素，但通过继承/装饰它，您可以添加该功能。

答

这不是不可能:)你只需要提供你自己的实现。

我会从this这样的RingBuffer开始，并相应地进行调整。

答

您可以使用LinkedHashMap的并覆盖其removeEldestEntry方法：

public class FixedStack extends LinkedHashMap<Long, String> { 

    private final int capacity; 

    public FixedStack(int capacity) { 
     this.capacity = capacity; 
    } 

    @Override 
    protected boolean removeEldestEntry(final Map.Entry<Long, String> eldest) { 
     return super.size() > capacity; 
    } 
}

，并测试它：

public static void main(String[] args) { 

     FixedStack stack = new FixedStack(10); 

     long added = 0; 
     for (Locale locale : Locale.getAvailableLocales()) { 
      if (locale.getDisplayCountry().length() > 0) { 
       stack.put(added, locale.getDisplayCountry()); 
       System.out.println(locale.getDisplayCountry()); 
       added++; 
      } 
     } 
     System.out.println(String.format(">>>>>>>>> %s added", 
       added)); 
     Iterator<Entry<Long, String>> iterator = stack.entrySet().iterator(); 
     while (iterator.hasNext()) { 
      System.out.println(iterator.next().getValue()); 
     } 
    }

你只需要决定你想用什么作为关键，我在示例中使用了一个简单的计数器。

答

这里是一个SizedStack类型扩展Stack：

import java.util.Stack; 

public class SizedStack<T> extends Stack<T> { 
    private int maxSize; 

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

    @Override 
    public T push(T object) { 
     //If the stack is too big, remove elements until it's the right size. 
     while (this.size() >= maxSize) { 
      this.remove(0); 
     } 
     return super.push(object); 
    } 
}

使用方法如下：SizedStack<Float> mySizedStack = new SizedStack<Float>(10);。除了尺寸之外，它与其他Stack一样运作。

这太棒了！我会建议用'if（this.size（）== maxSize）'替换'while（this.size（）> maxSize）'，以便初始化'SizedStack'的大小将是实际允许的最大大小叠加。 –

我把它改成'while（this.size（）> = maxSize）'来照顾你注意到的错误的错误。谢谢。尽管如此，它仍然应该是一个安全循环的while循环;如果尺寸大于maxSize，会发生什么？我知道这似乎不可能，但错误是错误:)。 – Calvin

创建固定大小的堆栈

相关推荐