C#数据结构练习——队列（包含迭代器和增加数据动态调整功能）

tech2026-04-07 1

C#数据结构练习——队列

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

直接上代码

using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; /// <summary> /// 队列先进先出 /// #线程不安全 /// </summary> public class MyQueue<T> : IEnumerator<T>,IEnumerable<T>, ICollection { /// <summary> /// 队首 /// </summary> private int head; /// <summary> /// 数据容器 /// </summary> private T[] datas; /// <summary> /// 数据量 /// </summary> private int size; /// <summary> /// 队尾 /// </summary> private int trail; public int Head => head; public int Trail => trail; public int Count => size; public bool IsEmpty => size <= 0; public MyQueue(int cap) { if (cap < 0) cap = 4; head = trail = 0; size = trail - head; datas = new T[cap]; } /// <summary> /// 默认数据容量时是 4 /// </summary> public MyQueue() : this(4) { } #region 迭代器 /// <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 (syncRoot == null) Interlocked.CompareExchange(ref syncRoot, new object(), null); return syncRoot; } } public bool IsSynchronized => false; public void Dispose() { } public IEnumerator GetEnumerator() { Reset(); return this; } IEnumerator<T> IEnumerable<T>.GetEnumerator() { return this; } /// <summary> /// 迭代器遍历条件 /// </summary> /// <returns></returns> public bool MoveNext() { currIndex++; //当前元素的编号必须小于尾编号否则可能会出现越界 return currIndex < trail; } public void Reset() { //重置时第一个元素（ <head -1> 操作是因为每次入队后首元素会 +1，便于后续的入队操作，所以不进行入队操作时需要 -1操作，来获取当前真正的首元素编号） currIndex = head - 1; } #endregion /// <summary> /// 入队 /// </summary> /// <param name="item">数据元素</param> public void Enqueue(T item) { //判断当前数据量进行容器调整 if (size == datas.Length) Resize(); //数据设置在尾部 datas[trail] = item; size++; Console.WriteLine($"数据入队：【{item}】，Head：【{head}】，Trail:【{trail}】，Size：【{size}】,Capacity:【{datas.Length}】"); Adjust(); //取模操作避免单纯自增出现的越界问题 trail = (trail + 1) % datas.Length; } /// <summary> /// 集合入队 /// </summary> /// <param name="collection"></param> public void Enqueue(IEnumerable<T> collection) { if (collection == null) throw new ArgumentNullException("参数为空"); IEnumerator<T> enumerator = collection.GetEnumerator(); if (enumerator == null) { throw new Exception("参数必须是集合或迭代器"); } //遍历给定集合的元素入队 while (enumerator.MoveNext()) { Enqueue(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; head = 0; trail = size; Console.WriteLine($"重置容量：{len}"); } /// <summary> /// 调整数据 /// </summary> private void Adjust() { //无数据或计数器小于设置的限制时不进行调整 if (size == 0) return; //1.尾标是容器的最后一位时且当前首标不是0 就是说当前容器内有元素且容器的前半部分有空余位置时 bool adjust = trail == datas.Length - 1 && head != 0; //2.容器容量大于10且数据量是容器的0.3倍时表示容器有很大的空间是闲置的，动态调整下数据位置，便于后续的数据存储和避免过度的扩容造成浪费空间的问题 adjust |= datas.Length > 10 && size < datas.Length * 0.3; //满足以上两个条件之一进行数据调整 if (adjust) { //把队首开始的数据复制到编号为0的地方 Array.Copy(datas, head, datas, 0, size); //清除其余的无用数据 Array.Clear(datas, size, datas.Length - size); Console.WriteLine($"调整数据位置前---Head:【{head}】---Trail：【{trail}】"); //重置尾标和首标 trail -= head; head = 0; Console.WriteLine($"调整数据位置后---Head:【{head}】---Trail：【{trail}】"); } } /// <summary> /// 出队 /// </summary> /// <returns></returns> public T Dequeue() { if (size == 0) { Console.WriteLine("空队"); return default(T); } T item = datas[head]; size--; head = (head + 1) % datas.Length; Console.WriteLine($"数据出队：【{item}】，Head:【{head}】，Trail：【{trail}】，Size：【{size}】,Capacity:【{datas.Length}】"); return item; } /// <summary> /// 复制 /// </summary> /// <param name="array"></param> /// <param name="index"></param> public void CopyTo(Array array, int index) { if (array == null) throw new ArgumentNullException("参数为空"); if (index < 0 || index > array.Length) throw new IndexOutOfRangeException("下标越界"); if (array.Rank != 1) throw new RankException("Rank not Match"); if (array.Length - index < Count) throw new ArgumentException("给定数组和编号不合适"); try { Array.Copy(datas, head, array, index, Count); } catch (Exception e) { throw e; } } /// <summary> /// 队列反转 /// </summary> public void Reverse() { Array.Reverse(datas, head, Count); } }

要点分析

1.队列的特性是先进先出，两端操作，需要维护队首和队尾两个标记 2.本文章内的首标必然是小于尾标 3.增加动态调整数据的功能，便于后续的数据存储和避免过度的扩容造成浪费空间的问题 4.其他细节分析见代码内注释

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

最新回复(0)