队列是一个有序列表,可以用数组或是链表来实现。
遵循先入先出的原则,即:先存入队列的数据,要先取出。后存入的要后取出
2.图示
3.通过数组实现
public class CircleArrayQueue { /// <summary> /// 队列最大值 /// </summary> public int MaxSize { get; set; } /// <summary> /// 队列头部 /// </summary> public int Front { get; set; } /// <summary> /// 队列尾部 /// </summary> public int Rear { get; set; } /// <summary> /// 队列数组 /// </summary> public int[] Arr { get; set; } /// <summary> /// 构造函数初始化队列 /// </summary> /// <param></param> public CircleArrayQueue(int maxSize) { this.MaxSize = maxSize+1; Arr = new int[MaxSize]; //Front = 0; //Rear = 0; 默认值 } /// <summary> /// 判断队列是否为满;当尾索引的下一个为头索引时表示队列满,将队列容量空出一个作为约定 /// </summary> /// <returns></returns> public bool IsFull() => (Rear + 1) % MaxSize==Front; /// <summary> /// 判断队列是否为空;当队列首==队列尾 首尾相等 /// </summary> /// <returns></returns> public bool IsEmpty() => Front == Rear; public void AddQueue(int value) { if (IsFull()) Console.WriteLine("队列已满!不能再添加数据"); else { //直接将数据加入 Arr[Rear] = value; //将队列尾部后移一个位置,因为是环形数组队列要考虑取模 Rear = (Rear + 1) % MaxSize; } } public void ShowQueue() { if (IsEmpty()) Console.WriteLine("队列为空!没有数据"); else { //从Front开始遍历 for (int i = Front; i < Front+Size(); i++) { Console.WriteLine($"Arr[{i%MaxSize}]={Arr[i%MaxSize]}"); } } } /// <summary> /// 队列尾 + 最大值 - 队列首 % 最大值 /// </summary> /// <returns></returns> public int Size() => (Rear + MaxSize-Front) % MaxSize; /// <summary> /// 取出队列数据 /// </summary> /// <returns></returns> public int GetQueue() { if (IsEmpty()) throw new Exception("队列为空!没有数据"); //1.先把Front对应的值保留到一个临时变量 //2.重新分配Front的值,将Front后移,要考虑取模 //3.将临时变量返回 var val = Arr[Front]; Front = (Front + 1) % MaxSize; return val; } public int HeadQueue() { if (IsEmpty()) throw new Exception("队列为空!没有数据"); //直接返回头元素 return Arr[Front]; } public static void Test() { CircleArrayQueue queue = new CircleArrayQueue(3); string key = ""; bool loop = true; while (loop) { Console.WriteLine("s(show):显示队列"); Console.WriteLine("e(exit):退出程序"); Console.WriteLine("a(add):添加数据到队列队列"); Console.WriteLine("g(get):从队列中取出数据"); Console.WriteLine("h(head):查看队列头部的数据"); key = Console.ReadLine(); switch (key) { case "s": queue.ShowQueue(); break; case "a": Console.WriteLine("请输入一个值"); int.TryParse(Console.ReadLine(), out int value); queue.AddQueue(value); break; case "g": try { int reuslt = queue.GetQueue(); Console.WriteLine("取出来的数据:" + reuslt); } catch (Exception ex) { Console.WriteLine(ex.Message); } break; case "h": try { int reuslt = queue.HeadQueue(); Console.WriteLine("队列头的数据:" + reuslt); } catch (Exception ex) { Console.WriteLine(ex.Message); } break; case "e": loop = false; break; default: break; } } Console.WriteLine("程序退出"); } }