我正在寻找一种基本上是有界堆栈的数据结构。
如果我声明堆栈最多可以容纳 3 个项目,并且我将另一个项目推入,则最旧的项目将被弹出。
我正在寻找一种基本上是有界堆栈的数据结构。
如果我声明堆栈最多可以容纳 3 个项目,并且我将另一个项目推入,则最旧的项目将被弹出。
您将能够使用双端队列 ( http://en.wikipedia.org/wiki/Deque ) 或双端队列上的包装器来实现这一点。如果达到堆栈大小,请确保在 offerFirst 方法中调用 pollLast 方法。
你需要一个队列。记录第一项和最后一项的单链表。如果您想从 O(n) 更改为 O(1) 遍历以更新最后一项,则为双重链接。
您将对象推到队列的前面。如果长度大于 3,则弹回。
那么 LIFO(后进先出)结构被称为堆栈,这是您满足主要要求的部分所需要的
FIFO(先进先出)结构被称为队列,这是您将最旧的项目从后面弹出的能力所需要的。
这些的组合称为双端队列。您必须能够从任一端推动或弹出。
我不确定 Java 是否有内置的 Deque 数据结构,但如果有(或者你可以在 google 上找到一个实现),你可以放一些包装逻辑来确保如果你推到前面,并且deque.Count > 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 的实现。
这是我的 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);
}
}