C#数据结构练习——栈

记录数据结构的练习 强调：线程不安全

---

直接上代码

using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; /// <summary> /// 栈 后进先出 /// #入栈时先赋值再修改顶部索引 /// #出栈时先修改顶部索引再出值 /// # 线程不安全 /// </summary> /// <typeparam name="T"></typeparam> public class MyStack<T> : IEnumerator<T>,IEnumerable<T>, ICollection { /// <summary> /// 顶部索引 作为存取数据的唯一依据 /// </summary> private int top; /// <summary> /// 数据容器 /// </summary> private T[] datas; public int Top { get => top; } /// <summary> /// 数据量 /// </summary> public int Count { get => top; } /// <summary> /// 是否为空 /// </summary> public bool IsEmpty => top < 0; /// <summary> /// 默认容器容量 /// </summary> private const int DefaultCapacity = 4; #region Enumerator迭代器 /// <summary> /// 索引标识 /// </summary> private int currIndex = -1; /// <summary> /// 当前元素 /// </summary> public T Current => datas[currIndex]; object IEnumerator.Current => Current; private object syncRoot; public object SyncRoot { get { if (this.syncRoot == null) Interlocked.CompareExchange<object>(ref this.syncRoot, new object(), null); return this.syncRoot; } } public bool IsSynchronized => false; /// <summary> /// 判断是否继续遍历 /// </summary> /// <returns></returns> public bool MoveNext() { currIndex--; return currIndex >= 0; } /// <summary> /// 重置索引标识 /// </summary> public void Reset() { currIndex = top; } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<T> GetEnumerator() { Reset(); return this; } public void Dispose() { } #endregion /// <summary> /// 默认构造 容量为4 /// </summary> public MyStack() : this(DefaultCapacity) { } public MyStack(int cap) { if (cap <= 0) cap = DefaultCapacity; datas = new T[cap]; top = 0; } public void Add(T item) { Push(item); } public void Clear() { Array.Clear(datas, 0, datas.Length); top = 0; } /// <summary> /// 包含元素 /// </summary> /// <param name="item"></param> /// <returns></returns> public bool Contains(T item) { //从栈顶部开始查找 int size = Count; EqualityComparer<T> comparer = EqualityComparer<T>.Default; while (size-- > 0) { if (item == null) { if (datas[size] == null) return true; } else { if (datas[size] != null && comparer.Equals(datas[size], item)) return true; } } return false; } /// <summary> /// 把数据拷贝到给定集合 /// </summary> /// <param name="array">给定集合</param> /// <param name="arrayIndex">给定集合的起始位置</param> public void CopyTo(Array array, int arrayIndex) { if (array == null) throw new NullReferenceException("array 参数为空"); if (array.Rank != 1) throw new RankException("Rank Not Matching"); if (arrayIndex < 0 || arrayIndex >= array.Length) throw new IndexOutOfRangeException("下标越界"); //给定集合的容量去除起始位置后 剩余的容量要大于栈的数据量 if (Count > array.Length - arrayIndex) throw new Exception("给定集合和起始编号不合适"); try { Array.Copy(datas, 0, array, arrayIndex, Count); //因为栈是后进先出结构 所以目标集合起始处的元素应该是栈顶元素， //而数据容器存储的方式是先进先存且下标递增的方式 所以需要反转一下复制后的数组 Array.Reverse(array, arrayIndex, Count); } catch (Exception e) { Console.WriteLine(e.StackTrace); throw; } } /// <summary> /// 入栈 /// </summary> /// <param name="item"></param> public void Push(T item) { //数据集合饱和时 扩容 if (top == datas.Length) Resize(); datas[top] = item; Console.WriteLine($"数据入栈：{item},Top:{top}"); //移动栈顶 top++; } /// <summary> /// 把集合数据入栈 /// </summary> /// <param name="items"></param> public void Push(IEnumerable<T> items) { if (items == null) throw new ArgumentNullException("参数为空"); IEnumerator<T> enumerator = items.GetEnumerator(); if (enumerator == null) { throw new Exception("参数必须是集合或迭代器"); } while (enumerator.MoveNext()) { Push(enumerator.Current); } } /// <summary> /// 重新设置存储容量 扩大1.5倍 /// </summary> private void Resize() { int len = datas.Length; //增大1.5倍 可自定义 len = (int)(len * 1.5); T[] newArr = new T[len]; Array.Copy(datas, newArr, datas.Length); datas = newArr; Console.WriteLine($"重置容量：{len}"); } /// <summary> /// 出栈 /// </summary> /// <returns></returns> public T Pop() { //先移动栈顶 top--; if (IsEmpty) throw new Exception("空栈"); T item = datas[top]; Console.WriteLine($"数据出栈：{item}"); return item; } /// <summary> /// 取栈顶元素 但是不移动栈顶索引 /// </summary> /// <returns></returns> public T Peek() { if (IsEmpty) throw new Exception("空栈"); T item = datas[top - 1]; Console.WriteLine($"{top}***{item}"); return item; } /// <summary> /// 栈反转 /// </summary> public void Reverse() { Array.Reverse(datas, 0, Count); } }

---

要点分析

1.栈的特性是后进先出，只能在一端操作，所以只需要维护一个栈顶标记即可 2.要注意栈顶标记在不同地方操作时的数值调整（代码内有注解） 3.其他细节分析见代码内注释

欢迎留言交流 转载请注明出处