Могу ли я ограничить глубину общего стека?

Question

Есть ли встроенный способ ограничения глубины 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)
            );           
    }

Итак, он возвращает новый стек после обрезки, но не является неизменным функциональным способом =)

Причина этого в том, что я храню шаги отмены для приложения в стеке и хочу хранить только конечное количество шагов.

Answer 1

То, что вы ищете, называется выпадающим стеком . AFAIK, BCL не содержит ни одного, хотя они тривиальны для реализации. Обычно функции отмены и возврата основаны на таких структурах данных.

Они в основном массив, и когда вы помещаете в стек, «верх» стека перемещается вокруг массива. В конце концов вершина вернется к началу, когда стек заполнится, и заменит «низ» стека.

Google не предоставил много информации об этом. Это лучшее, что я смог найти:

(Предупреждение 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];
    }
}

Answer 2

Вы на самом деле смотрите на что-то похожее на реализацию кругового списка. Существует реализация LimitedQueue , выполненная PIEBALDconsult в CodeProject. Это похоже на ваше требование. Вам просто нужно обернуть Stack вместо Queue, как сделано автором. Кроме того, автор также реализовал индексатор, который удобен, если вам нужен доступ к чему-либо еще, кроме верхнего стека (возможно, для отображения списка отмен).

РЕДАКТИРОВАТЬ: Реализация автора также вызывает событие, когда удаляется последнее (во-первых, зависит от того, очередь это или стек), чтобы вы могли знать, когда что-то выбрасывается.

Answer 3

Для всех, кто сталкивался с этим вопросом, пытаясь ограничить размер стека отмены / повтора, вот лучшее решение (использует LinkedList):

Ограничение размера общей коллекции

Answer 4

Я полагаю, вы ищете (возможно, модифицированный) dequeue - структуру данных, которая разрешает доступ с любого конца.

Answer 5

Я не вижу пути. Вы можете наследовать от Stack<T>, но нет ничего полезного для переопределения.

Самый простой (хотя и немного утомительный) способ - обернуть Stack<T> в свой собственный, скажем, LimitedStack<T>. Затем реализуйте методы, которые вы хотите, и передайте во внутренний Stack<T>, включив вашу ограничивающую логику в метод Push и везде, где вам это нужно.

Трудно написать все эти сквозные члены, особенно если вы реализуете все те же интерфейсы, что и Stack<T> ... но, с другой стороны, вам нужно сделать это только один раз, и тогда это будет сделано.