【算法】Algorithms4 C#实现

《Algorithms Fourth Edition》中算法的C#实现

下压栈

public class ResizingStack<T> : IEnumerable<T>
{
    private T[] items;
    public int Capacity => items.Length;
    public int Count { get; private set; }

    public ResizingStack(int cap)
    {
        items = new T[cap];
        Count = 0;
    }

    private void Resize(int n)
    {
        T[] newItems = new T[n];
        for (int i = 0; i < Count; i++)
        {
            newItems[i] = items[i];
        }
        items = newItems;
    }

    public bool IsEmpty() => Count == 0;

    public void Push(T item)
    {
        items[Count++] = item;
        if (Count == items.Length)
        {
            Resize(items.Length * 2);
        }
    }

    public T Pop()
    {
        T item = items[--Count];
        items[Count] = default(T);
        if (Count > 0 && Count == items.Length / 4) Resize(items.Length / 2);
        return item;
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
        return new Enumerator(this);
    }

    public IEnumerator GetEnumerator()
    {
        return new Enumerator(this);
    }

    public struct Enumerator : IEnumerator<T>
    {
        static string ExpEnumNotStarted = "Enumerator has not started.";
        static string ExpEnumEnded = "Enumerator has ended."; 
        private readonly ResizingStack<T> _stack;
        private int _index;
        public T Current
        {
            get {
                if (_index < 0) throw new InvalidOperationException(_index == -2 ? ExpEnumNotStarted : ExpEnumEnded);
                return _stack.items[_index];
            }
        }

        object IEnumerator.Current => Current;

        internal Enumerator(ResizingStack<T> stack)
        {
            _stack = stack;
            _index = -2; //Not Started
        }

        public void Dispose()
        {
            _index = -1;
        }

        public bool MoveNext()
        {
            if (_index == -2) //First Call
            {
                _index = _stack.Count - 1;
                return _index >= 0;
            }
            if (_index == -1) // Ended
            {
                return false;
            }
            return --_index >= 0;
        }

        public void Reset()
        {
            _index = -2;
        }
    }
}