《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; } } }