java - 什么数据结构将在 LIFO 中保存有界的项目堆栈？

Question

我正在寻找一种基本上是有界堆栈的数据结构。

如果我声明堆栈最多可以容纳 3 个项目，并且我将另一个项目推入，则最旧的项目将被弹出。

Answer 1

您将能够使用双端队列 ( http://en.wikipedia.org/wiki/Deque ) 或双端队列上的包装器来实现这一点。如果达到堆栈大小，请确保在 offerFirst 方法中调用 pollLast 方法。

Answer 2

我会基于环形缓冲区编写自己的Deque实现。

Answer 3

你需要一个队列。记录第一项和最后一项的单链表。如果您想从 O(n) 更改为 O(1) 遍历以更新最后一项，则为双重链接。

您将对象推到队列的前面。如果长度大于 3，则弹回。

Answer 4

那么 LIFO（后进先出）结构被称为堆栈，这是您满足主要要求的部分所需要的

FIFO（先进先出）结构被称为队列，这是您将最旧的项目从后面弹出的能力所需要的。

这些的组合称为双端队列。您必须能够从任一端推动或弹出。

我不确定 Java 是否有内置的 Deque 数据结构，但如果有（或者你可以在 google 上找到一个实现），你可以放一些包装逻辑来确保如果你推到前面，并且deque.Count > 3，然后也从后面弹出。

Answer 5

这是在 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;
    }
}

Answer 6

Apache commons 有一些接近你需要的东西，除了它是 Fifo: CircularFifoBuffer。我认为您将被困在编写自定义包装器以制作类似 Lifo 的实现。

Answer 7

这是我的 LIFO 实施，灵感来自 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);
    }
}