C#数据结构-队列 - 张拓的天空

发表评论
323 次浏览

A+

所属分类：.NET技术

摘要

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

先来看下用法：

            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();