1

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

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

4

7 に答える 7

3

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

于 2009-05-01T08:11:09.823 に答える
1

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

オブジェクトをキューの先頭にプッシュします。長さが 3 を超える場合は、背面をポップします。

于 2009-05-01T08:08:43.167 に答える
0

Apache commons には、必要なものに近いものがありますが、それは Fifo: CircularFifoBufferです。Lifo のような実装を作成するために、カスタム ラッパーを作成するのに行き詰まると思います。

于 2009-05-01T08:19:30.210 に答える
0

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);
    }
}
于 2016-02-25T09:28:43.533 に答える
0

LIFO (後入れ先出し) 構造はスタックとして知られています。これは、要件の主要部分に必要なものです。

FIFO (先入れ先出し) 構造はキューとして知られています。これは、最も古いアイテムを後ろからポップする機能に必要なものです。

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

Java に組み込みの Deque データ構造があるかどうかはわかりませんが、ある場合 (または Google で実装を見つけることができます)、いくつかのラッピング ロジックを配置して、前面にプッシュした場合に確実にすることができます。 deque.Count > 3 の場合、後ろからポップします。

于 2009-05-01T08:16:14.663 に答える
0

私はJavaを知らないので、これはC＃にありますが、アイデアは翻訳されるはずです。

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;
    }
}
于 2009-05-01T08:17:23.537 に答える