Quale struttura di dati conterrà una pila limitata di elementi in LIFO?

Question

Sto cercando una struttura di dati che è fondamentalmente uno stack limitato.

Se dichiaro che la pila può contenere al massimo 3 oggetti e inserisco un altro oggetto, l'oggetto più vecchio viene spuntato.

Answer 1

Bene, una struttura LIFO (Last In First Out) è nota come Stack, che è ciò di cui hai bisogno per la parte principale delle tue esigenze

Una struttura FIFO (First In First Out) è conosciuta come una Coda che è ciò di cui hai bisogno per poter estrarre gli oggetti più vecchi da dietro.

Una combinazione di questi è nota come Deque. Dove hai la possibilità di spingere o far scoppiare da entrambe le estremità.

Non sono sicuro che Java abbia una struttura dati Deque integrata, ma se lo fa (o puoi trovare un'implementazione su google), puoi semplicemente mettere in giro una logica di wrapping per assicurarti che se passi in primo piano e il deque.Count > 3, quindi anche pop dal retro.

Answer 2

Potrai implementarlo utilizzando un wrapper su un deque ( http: // it. wikipedia.org/wiki/Deque ) o coda doppia. Assicurati di chiamare il metodo pollLast all'interno del metodo offerFirst se viene raggiunta la dimensione dello stack.

Answer 3

Scriverei il mio Deque buffer buffer.

Answer 4

Hai bisogno di una coda. Un elenco collegato singolarmente che registra il primo e l'ultimo elemento. Doppiamente collegato se desideri passare da O (n) a O (1) traversal per aggiornare l'ultimo elemento.

Spingi oggetti nella parte anteriore della coda. E se la lunghezza è maggiore di 3, fai apparire la parte posteriore.

Answer 5

Questo è in C # poiché non conosco Java, temo, ma l'idea dovrebbe tradursi.

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

I comuni di Apache hanno qualcosa di simile a ciò di cui hai bisogno, tranne che per Fifo: CircularFifoBuffer . Penso che sarai bloccato a scrivere un wrapper personalizzato per realizzare un'implementazione simile a Lifo.

Answer 7

Ecco la mia implementazione LIFO, ispirata alla risposta di 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);
    }
}