創建固定大小的堆棧

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一樣運作。