欢迎光临
我的个人博客网站

C#数据结构-队列

队列作为线性表的另一个数据结构,只允许在表的前端进行删除操作,而在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。

先来看下用法:

            Queue queue = new Queue();             queue.Enqueue(1);             queue.Enqueue(2);             queue.Enqueue(3);             queue.Enqueue(4);             foreach (var r in queue)             {                 Console.Write($"data:{r} ");             }             Console.WriteLine();             Console.WriteLine($"peek:{queue.Peek()}");             queue.Dequeue();             queue.Enqueue(5);             queue.Enqueue(6);             Console.WriteLine();

打印结果:

C#数据结构-队列

 

 

    public class MyQueue     {         /// <summary>         /// 存储栈结构         /// </summary>         public object[] content { get; set; }         /// <summary>         /// 队列第一个节点         /// </summary>         public int head { get; set; }         /// <summary>         /// 对列最后一个节点         /// </summary>         public int tail { get; set; }         /// <summary>         /// 队列长度         /// </summary>         public int size { get; set; }         /// <summary>         /// 增长因子 100 == 1.0         /// </summary>         public int growFactor { get; set; }         /// <summary>         /// 最小增加量         /// </summary>         private const int minimumGrow = 4;         private const int _ShrinkThreshold = 32;         /// <summary>         /// 初始化         /// </summary>         public MyQueue()             : this(32, (float)2.0)         {         }         /// <summary>         ///         /// </summary>         /// <param name="capacity">队列长度</param>         /// <param name="growFactor">增长因子</param>         public MyQueue(int capacity, float _growFactor)         {             if (capacity < 0)                 throw new ArgumentOutOfRangeException("参数错误");             if (!(_growFactor >= 1.0 && _growFactor <= 10.0))                 throw new ArgumentOutOfRangeException("增长因子不在范围内");             content = new Object[capacity];             head = 0;             tail = 0;             size = 0;             growFactor = (int)(_growFactor * 100);         }         /// <summary>         /// 在队列尾处添加节点         /// </summary>         /// <param name="obj"></param>         public virtual void Enqueue(object obj)         {             if (size == content.Length)             {                 //计算扩展后的队列长度                 int newCapacity = (int)(content.Length * growFactor / 100);                 if (newCapacity < content.Length + newCapacity)                 {                     newCapacity = content.Length + minimumGrow;                 }                 SetCapacity(newCapacity);             }             content[tail] = obj;             tail = (tail + 1) % content.Length;             size++;         }         /// <summary>         /// 在队列头部出栈         /// </summary>         /// <returns></returns>         public virtual Object Dequeue()         {             if (size == 0)                 throw new IndexOutOfRangeException("空队列");             object rem = content[head];             content[head] = null;             head = (head + 1) % content.Length;             size--;             return rem;         }         public virtual Object Peek()         {             if (size == 0)                 throw new IndexOutOfRangeException("空队列");             return content[head];         }         /// <summary>         /// 扩展队列         /// </summary>         /// <param name="capacity"></param>         private void SetCapacity(int capacity)         {             object[] newArray = new object[capacity];             if (size > 0)             {                 if (head < tail)                 {                     Array.Copy(content, head, newArray, 0, size);                 }                 else                 {                     Array.Copy(content, head, newArray, 0, content.Length - head);                     Array.Copy(content, 0, newArray, content.Length - head, head);                 }             }             content = newArray;             head = 0;             tail = (size == capacity) ? 0 : size;         }         public void ShowAll()         {             for (int i = head; i < size; i++)             {                 Console.Write($"index:{i},data:{content[i]}    ");             }             Console.WriteLine("——————————————————————");         }     }

测试:

            MyQueue queue = new MyQueue();             queue.Enqueue(1);             queue.Enqueue(2);             queue.Enqueue(3);             queue.Enqueue(4);             queue.ShowAll();             Console.WriteLine($"peek:{queue.Peek()}");             queue.Dequeue();             queue.Enqueue(5);             queue.Enqueue(6);             queue.ShowAll();             Console.ReadLine();

实现方式:

通过object对象数组,存储队列中的节点数据,另外定义两个指针分别指向队列的头部节点以及尾部节点。

Enqueue入队时,(如果队列长度达到数组最大长度,则通过扩展数组(队列长度 * 增长因子)来增加数组长度)通过在对尾附加节点来实现的。

Dequeue出队时,通过头指针后移实现出队列。

另外未实现地方,为节省内存空间,数组中出队后的空间也要加入到后续入队时用到的闲置位置。

以上方法都是以虚方法的方式实现的,便于后续重写(例如线程安全队列)。

打印结果:

C#数据结构-队列

 

 


 

 C#数据结构-队列

 

赞(0) 打赏
未经允许不得转载:张拓的天空 » C#数据结构-队列
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏