Альтернатива для стека

Question

Я работаю в среде .Net, используя C #. Мне нужна альтернатива для структуры данных стека. Какой-то связанный стек. Количество элементов в коллекции не должно превышать определенного фиксированного количества. И, если это число достигнуто и новый элемент помещен, то самый старый элемент должен быть удален. Мне это нужно для хранения команд для стратегий отмены / повторения.

Answer 1

A круговой буфер должен выполнять эту работу; достаточно просто обернуть список или массив, но ничего не встроено в AFAIK.

Answer 2

Джонни Кодер имеет здесь реализацию: http://johnnycoder.com/blog/2008/01/07/undo-functionality-with-a-limited-stack/

Answer 3

Это реализация стека с ограниченными возможностями. После достижения заданной емкости нижние элементы стека за пределами емкости отбрасываются. Можно выполнить итерацию по содержащимся объектам и установить индекс на определенную позицию (например, перемотку) для одновременного отбрасывания нескольких записей при загрузке нового элемента в стек.

Это собственная реализация с некоторыми вкусностями, которая не позволяет вам обрабатывать более одного списка, если вам нужно вернуться в историю и снова перейти вперед (встроено).

public class DiscardingStack<TObject> : IEnumerable<TObject>
{
    private readonly int capacity;

    private readonly List<TObject> items;

    private int index = -1;

    public DiscardingStack(int capacity)
    {
        this.capacity = capacity;
        items = new List<TObject>(capacity);
    }

    public DiscardingStack(int capacity, IEnumerable<TObject> collection)
        : this(capacity)
    {
        foreach (var o in collection)
        {
            Push(o);
        }
    }

    public DiscardingStack(ICollection<TObject> collection)
        : this(collection.Count, collection)
    {
    }

    public void Clear()
    {
        if (items.Count >= 0)
        {
            items.Clear();
            index = items.Count - 1;
        }
    }

    public int Index
    {
        get { return index; }
        set
        {
            if (index >= 0 && index < items.Count)
            {
                index = value;
            }
            else throw new InvalidOperationException();
        }
    }

    public int Count
    {
        get { return items.Count; }
    }

    public TObject Current
    {
        get { return items[index]; }
        set { index = items.IndexOf(value); }
    }

    public int Capacity
    {
        get { return capacity; }
    }

    public TObject Pop()
    {
        if (items.Count <= 0)
            throw new InvalidOperationException();

        var i = items.Count - 1;
        var removed = items[i];
        items.RemoveAt(i);

        if (index > i)
            index = i;

        return removed;
    }

    public void Push(TObject item)
    {
        if (index == capacity - 1)
        {
            items.RemoveAt(0);
            index--;
        }
        else if (index < items.Count - 1)
        {
            var removeAt = index + 1;
            var removeCount = items.Count - removeAt;
            items.RemoveRange(removeAt, removeCount);
        }

        items.Add(item);

        index = items.Count - 1;
    }

    public TObject Peek()
    {
        return items[items.Count-1];
    }

    public TObject this[int i]
    {
        get { return items[i]; }
    }

    public IEnumerator<TObject> GetEnumerator()
    {
        return items.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

В любом случае, создание стека, который отбрасывает элементы при достижении максимальной емкости, должно быть реализовано с использованием LinkedList (как предложено выше), если ваш список огромен (избегает копирования). Таким образом, идея LinkedList могла бы быть лучше в таком случае вместо переноса List, если максимум буфера является высоким значением.

Я бы также рекомендовал упаковать Push (), Pop () и т. Д. В интерфейс (например, IStack). К сожалению, нет интерфейса IStack, предопределенного в .Net (afaik).

Answer 4

.Net довольно несовершенный тип коллекций.Вы найдете библиотеку коллекций здесь .Используйте CircularQueue .

Answer 5

В Framework нет встроенного класса для этого.(мы не ожидаем автоматического удаления данных).Но вы можете очень хорошо расширить класс стека и переопределить push / pop и другие методы в соответствии с вашими потребностями.