¿Qué estructura de datos contendrá una pila limitada de elementos en LIFO?

Question

Estoy buscando una estructura de datos que sea básicamente una pila limitada.

Si declaro que la pila puede contener a lo sumo 3 elementos, y presiono otro elemento, El elemento más antiguo es popping.

Answer 1

Bueno, una estructura LIFO (Last In First Out) se conoce como Stack, que es lo que necesita para la parte principal de su requisito

Una estructura FIFO (primero en entrar, primero en salir) se conoce como cola, que es lo que necesita para poder sacar los elementos más antiguos de la parte posterior.

Una combinación de estos se conoce como Deque. Donde tenga la capacidad de empujar o hacer estallar desde cualquier extremo.

No estoy seguro de si Java tiene una estructura de datos de Deque incorporada, pero si la tiene (o puede encontrar una implementación en Google), puede poner un poco de lógica de ajuste para asegurarse de que si empuja al frente y el deque.Count > 3, luego también emerge desde la parte posterior.

Answer 2

Podrá implementar esto utilizando un contenedor sobre un deque ( http: // en. wikipedia.org/wiki/Deque ), o cola de doble final. Solo asegúrese de llamar al método pollLast dentro del método offerFirst si se alcanza el tamaño de pila.

Answer 3

Escribiría mi propia Deque implementación basada en un anillo de búfer.

Answer 4

Necesitas una cola. Una lista vinculada individualmente que registra el primer y el último elemento. Uno doblemente vinculado si desea cambiar de O (n) a O (1) transversal para actualizar el último elemento.

Empujas objetos al frente de la cola. Y si la longitud es mayor que 3, se abre la espalda.

Answer 5

Esto está en C # porque no sé Java, me temo, pero la idea debería traducirse.

public class BoundedStack<T>
{
    private readonly int limit;
    private LinkedList<T> list;

    public BoundedStack(int limit)
    {
        this.limit = limit;
        list = new LinkedList<T>();
    }

    public void Push(T item)
    {
        if (list.Count == limit) list.RemoveFirst();
        list.AddLast(item);
    }

    public T Pop()
    {
        if (list.Count == 0) 
            throw new IndexOutOfRangeException("No items on the stack");

        var item = list.Last.Value;
        list.RemoveLast();

        return item;
    }

    public int Count()
    {
        return list.Count;
    }
}

Answer 6

Apache commons tiene algo parecido a lo que necesitas, excepto que es Fifo: CircularFifoBuffer . Creo que se quedará atrapado escribiendo un contenedor personalizado para hacer una implementación similar a Lifo.

Answer 7

Aquí está mi implementación LIFO, inspirada en la respuesta de Garry Shutler

public class BoundedStack<T> {

    private int limit;
    private LinkedList<T> list;

    public BoundedStack(int limit) {
        this.limit = limit;
        list = new LinkedList<>();
    }

    public void push(T item) {
        if (list. size() == limit) {
            list.removeLast();
        }
        list.addFirst(item);
    }

    public int size() {
        return list.size();
    }

    public List<T> getAll() {
        return list;
    }

    public T peek() {
        return list.get(0);
    }
}