LIFOのアイテムの境界スタックを保持するデータ構造は何ですか？

StackOverflow https://stackoverflow.com/questions/810592

質問

基本的に境界スタックであるデータ構造を探しています。

スタックが最大3つのアイテムを保持できることを宣言し、別のアイテムをプッシュすると、 最も古いアイテムがポップされます。

役に立ちましたか？

解決

LIFO（Last In First Out）構造は、要件の主要部分に必要なスタックとして知られています

FIFO（先入れ先出し）構造は、最も古いアイテムを後ろからポップする機能に必要なキューと呼ばれます。

これらの組み合わせは、Dequeとして知られています。いずれかの端からプッシュまたはポップする機能が必要な場所。

JavaにDequeデータ構造が組み込まれているかどうかはわかりませんが、もしそれがあれば（またはGoogleで実装を見つけることができます）、ラップロジックを配置して、最前面にプッシュすることを確認できます、およびdeque.Count＆gt; 3、次に背面からもポップします。

他のヒント

dequeのラッパーを使用してこれを実装できます（ http：// en。 wikipedia.org/wiki/Deque ）、または両端キュー。スタックサイズに達した場合は、必ずofferFirstメソッド内でpollLastメソッドを呼び出してください。

キューが必要です。最初と最後のアイテムを記録する単一リンクリスト。 O（n）からO（1）トラバーサルに変更して最後のアイテムを更新する場合は、二重にリンクされたもの。

キューの先頭でオブジェクトをプッシュします。また、長さが3より大きい場合は、後ろに飛び出します。

これはC＃で、Javaがわからないので怖いですが、アイデアは翻訳する必要があります。

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

Apache commonsには、Fifo以外に必要なものに近いものがあります： CircularFifoBuffer 。 Lifoのような実装を行うためのカスタムラッパーの作成に追われていると思います。

これは、Garry Shutlerの答えに触発された、私のLIFOの実装です

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);
    }
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top