创建固定大小的堆栈

Question

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

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

Answer 1

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

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; 
    } 
} 

Answer 2

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

Answer 3

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

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

Answer 4

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

---

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

Answer 5

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

Answer 6

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

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

Answer 7

您可以使用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()); 
     } 
    } 

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

Answer 8

这里是一个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一样运作。