Welche Datenstruktur wird einen begrenzten Stapel von Gegenständen in LIFO halten?

Question

Ich bin für eine Datenstruktur, die im Grunde ein beschränktes Stapel ist.

Wenn ich erklären, dass der Stapel höchstens 3 Elemente halten kann, und ich schiebe ein anderes Element in, das älteste Stück ist aufgetaucht.

Answer 1

Nun ein LIFO (Last In First Out) Struktur wird als Stapel bekannt, das, was Sie für den Hauptteil Ihrer Anforderung benötigen, ist

Ein FIFO (First In First Out) Struktur wird als Queue bekannt, das ist, was Sie für die Fähigkeit benötigen, um die ältesten Gegenstände weg von der Rückseite Pop.

Eine Kombination von diesen ist als Deque bekannt. Wo haben Sie sich auf die Fähigkeit von jedem Ende zu drücken oder Pop.

Ich bin mir nicht sicher, ob Java verfügt über eine integrierte in Deque Datenstruktur, aber wenn es funktioniert (oder Sie können eine Implementierung auf Google finden), können Sie nur einige Verpackungs Logik setzen um, um sicherzustellen, wenn Sie nach vorne schieben und die deque.Count> 3, dann auch von der Rückseite Pop.

Answer 2

können Sie dies implementieren einen Wrapper über einen deque mit ( http: // en. wikipedia.org/wiki/Deque ) oder Deque. So stellen Sie sicher, dass die pollLast Methode innerhalb des offerFirst Methode aufrufen, wenn die Stapelgröße erreicht ist.

Answer 3

Ich würde meine eigene Deque Implementierung auf der Basis eines Ringpuffer.

Answer 4

Sie müssen eine Warteschlange. Eine einfach verkettete Liste, die die ersten und letzten Elemente aufzeichnet. Ein doppelt verkettete ein, wenn Sie möchten von O (n) bis O (1) Traversal ändern das letzte Element zu aktualisieren.

Sie sollten Gegenstände an der Spitze der Warteschlange. Und wenn die Länge größer als 3 ist, knallen Sie die Rückseite.

Answer 5

Dies ist in C #, wie ich Java weiß nicht, ich habe Angst, aber die Idee sollte übersetzen.

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 hat etwas in der Nähe, was Sie brauchen, außer es ist Fifo: CircularFifoBuffer . Ich glaube, Sie stecken werden eine benutzerdefinierte Wrapper zu schreiben, um eine Lifo wie Implementierung zu machen.

Answer 7

Hier ist meine LIFO Implementierung, inspiriert von Garry Shutler Antwort

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