Qual estrutura de dados irá realizar uma pilha limitada de itens em LIFO?

Question

Eu estou procurando uma estrutura de dados que é basicamente uma pilha limitada.

Se eu declarar que a pilha pode conter no máximo 3 itens, e eu empurro outro item, o item mais antigo é estalado.

Answer 1

Bem uma estrutura (Last In First Out) LIFO é conhecido como uma pilha que é o que você precisa para a parte principal da sua exigência

A FIFO (First In First Out) estrutura é conhecida como uma fila que é o que você precisa para a capacidade de estourar os itens mais antigos ao largo das costas.

Uma combinação deles é conhecido como um Deque. Onde você tem que a capacidade de empurrar ou pop de cada extremidade.

Eu não tenho certeza se o Java tem um built-in Deque datastructure, mas se isso acontecer (ou você pode encontrar uma implementação no Google), você pode simplesmente colocar alguma lógica envolvendo em torno para garantir que se você empurrar para a frente eo deque.Count> 3, então também pop da parte traseira.

Answer 2

Você será capaz de implementar isso usando um wrapper sobre um deque ( http: // en. wikipedia.org/wiki/Deque ), ou fila de dupla extremidade. Apenas certifique-se de chamar o método pollLast dentro do método offerFirst se o tamanho da pilha é atingido.

Answer 3

eu escrever meu próprio Deque execução com base em uma tampão anel.

Answer 4

Você precisa de uma fila. Uma lista vinculada isoladamente que registra os primeiros e últimos itens. A um duplamente ligada se você gostaria de mudar de O (n) O (1) transversal para atualizar o último item.

Você empurrar objetos na frente da fila. E se o comprimento for superior a 3, você pop costas.

Answer 5

Esta é em C #, como eu não sei Java Eu estou com medo, mas a idéia deve traduzir.

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 tem algo perto do que você precisa, exceto que é Fifo: CircularFifoBuffer . Eu acho que você vai ser preso escrevendo um wrapper personalizado para fazer um Lifo como implementação.

Answer 7

Aqui está minha implementação LIFO, inspirado pela resposta 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);
    }
}