Crear una pila de tamaño fijo

Question

Quiero crear una pila en Java, pero repare el tamaño. Por ejemplo, cree una nueva pila, establezca el tamaño en 10, luego, cuando coloque elementos en la pila, se llene y cuando se llene hasta diez, el último elemento de la pila se empujará (se eliminará). Quiero usar Stack porque usa LIFO y se adapta muy bien a mis necesidades.

Pero el método setSize() que Stack hereda de Vector no parece limitar realmente el tamaño de la pila. Creo que me falta algo acerca de cómo funcionan las pilas, o quizás las pilas no estaban destinadas a ser restringidas por lo que es imposible. ¡Por favor, enséñame!

Answer 1

Puede crear una pila muy simple como esto:

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

Puede crear la subclase Stack y anular los métodos apropiados para implementar este comportamiento personalizado. Y asegúrese de darle un nombre claro (por ejemplo, FixedStack).

Answer 3

Una pila pura no limitaría su tamaño, ya que muchos de los problemas que resuelven las pilas no saben cuántos elementos va a necesitar.

Puede escribir una pila personalizada que implemente las necesidades que describió. Sin embargo, romperás LIFO si lo haces. Si se alcanza el tamaño máximo y empuja algo nuevo en la pila, solo pierde el elemento agregado anteriormente. Entonces, si luego comienzas a sacar elementos de tu pila, te perderás algunos.

Answer 4

A LinkedBlockingDeque es una opción simple. Use el constructor LinkedBlockingQueue(int) donde el parámetro es el límite de su pila. secuencias sin límites

---

Como usted observó, Stack y Vector modelo. El método setSize() trunca la pila/vector. No impide que la estructura de datos crezca más allá de ese tamaño.

Answer 5

Lo que necesita es una cola de doble terminación como LinkedList. Sin embargo, esto no soltaría elementos automáticamente en el frente, pero al subclasar/decorarlo podría agregar esa funcionalidad.

Answer 6

Esto no es imposible :) Solo tiene que proporcionar su propia implementación.

Comenzaría con un RingBuffer como this y lo ajustaría en consecuencia.

Answer 7

Puede utilizar LinkedHashMap y anular su método 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; 
    } 
} 

Y para probarlo:

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

Solo tienes que decidir qué quieres usar como clave, utilicé un contador simple en el ejemplo.

Answer 8

Aquí es un tipo SizedStack que se extiende 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); 
    } 
} 

utilizar de esta manera: SizedStack<Float> mySizedStack = new SizedStack<Float>(10);. Aparte del tamaño, funciona como cualquier otro Stack.