7

是否有内置方法来限制 System.Collection.Generics.Stack 的深度？因此，如果您处于最大容量，推送一个新元素会移除堆栈的底部？

我知道我可以通过转换为数组并重建堆栈来做到这一点，但我认为可能已经有一个方法了。

编辑：我写了一个扩展方法：

    public static void Trim<T> (this Stack<T> stack, int trimCount) 
    {
        if (stack.Count <= trimCount)
            return;

       stack = new 
            Stack<T>
            (
                stack
                    .ToArray()
                    .Take(trimCount)
            );           
    }

因此，它在修剪时返回一个新堆栈，但功能方式不是不变性=)

这样做的原因是我将应用程序的撤消步骤存储在堆栈中，并且我只想存储有限数量的步骤。

4

5 回答 5

23

您正在寻找的东西称为dropout stack。AFAIK，BCL 不包含一个，尽管它们实现起来很简单。通常，撤消和重做功能依赖于此类数据结构。

它们基本上是一个数组，当您压入堆栈时，堆栈的“顶部”会在数组周围移动。最终，当堆栈已满时，顶部将回到开头并替换堆栈的“底部”。

谷歌没有提供太多关于它的信息。这是我能找到的最好的：

（警告 PDF） http://courses.cs.vt.edu/~cs2704/spring04/projects/DropOutStack.pdf

这是一些样板代码，可以帮助您入门。我会让你填写其余的（完整性检查、计数、索引器等）

class DropOutStack<T>
{
    private T[] items;
    private int top = 0;
    public DropOutStack(int capacity)
    { 
        items = new T[capacity];
    }

    public void Push(T item)
    {
        items[top] = item;
        top = (top + 1) % items.Length;
    }
    public T Pop()
    {
        top = (items.Length + top - 1) % items.Length;
        return items[top];
    }
}
于 2008-12-21T04:37:15.270 回答
4

您实际上正在查看类似于循环列表实现的内容。PIEBALDconsult 在 CodeProject上有一个LimitedQueue实现。这与您的要求相似。您只需要像作者所做的那样包装 Stack 而不是 Queue 。另外作者还实现了索引器，如果您需要访问除顶部堆栈以外的任何其他内容（可能显示撤消列表），这很方便。

编辑：作者的实现还会在最后一个（首先，取决于它是队列还是堆栈）被删除时引发一个事件，这样你就可以知道什么时候被扔掉了。

于 2008-12-21T04:41:48.083 回答
2

我相信您正在寻找一个（可能已修改的）出队- 允许从任一端访问的数据结构。

于 2008-12-21T03:36:22.800 回答
2

我看不到方法。您可以从 继承Stack<T>，但似乎没有任何有用的东西可以覆盖。

简单（如果有点乏味）的方法是Stack<T>将LimitedStack<T>. 然后实现你想要的方法并传递给一个 internal ，同时在方法和其他任何你需要的地方Stack<T>包含你的限制逻辑。Push

编写所有这些传递成员是一件痛苦的事，特别是如果您要实现与Stack<T>...相同的所有接口，但另一方面，您只需执行一次然后就完成了。

于 2008-12-21T03:12:59.870 回答
1

By提供的解决方案Greg Dean => dropout stack非常好，但我认为主要问题是关于在堆栈溢出时移除堆栈底部但是提供的解决方案只是在堆栈被填满后替换堆栈的最后一项，所以你不会得到真实的历史，

但是要获得真实的历史记录，一旦列表达到您的特定容量，您需要移动列表，但这是一个扩展操作，

所以我认为最好的解决方案是链表

这是我解决问题的方法


public class HistoryStack<T>
{
    private LinkedList<T> items = new LinkedList<T>();
    public List<T> Items => items.ToList();
    public int Capacity { get;}
    public HistoryStack(int capacity)
    {
        Capacity = capacity;
    }

    public void Push(T item)
    {
        // full
        if (items.Count == Capacity)
        {
            // we should remove first, because some times, if we exceeded the size of the internal array
            // the system will allocate new array.
            items.RemoveFirst();
            items.AddLast(item);
        }
        else
        {
            items.AddLast(new LinkedListNode<T>(item));
        }
    }

    public T Pop()
    {
        if (items.Count == 0)
        {
            return default;
        }
        var ls = items.Last;
        items.RemoveLast();
        return ls == null ? default : ls.Value;
    }
}

测试一下


var hs = new HistoryStack<int>(5);
hs.Push(1);
hs.Push(2);
hs.Push(3);
hs.Push(4);
hs.Push(5);
hs.Push(6);
hs.Push(7);
hs.Push(8);

var ls = hs.Items;
Console.WriteLine(String.Join(",", ls));

Console.WriteLine(hs.Pop());
Console.WriteLine(hs.Pop());

hs.Push(9);


Console.WriteLine(hs.Pop());
Console.WriteLine(hs.Pop());
Console.WriteLine(hs.Pop());
Console.WriteLine(hs.Pop());
Console.WriteLine(hs.Pop()); // empty
Console.WriteLine(hs.Pop()); // empty

结果

4,5,6,7,8
8
7
9
6
5
4
0
0
于 2020-11-20T01:35:45.730 回答