任务

循环数组

实现目标：（1）创建一个新的数组数据结构;

　　　　　（2）该数据结构为泛型;

　　　　　（3）可以按照元素多少进行扩容缩容;

　　　　　（4）进行添加删除操作的时间复杂度小于O(n);

优势：在取出放入的操作中消耗的资源更少

劣势：取出特定元素或特定下标元素平均消耗的资源为普通数组平均消耗资源的最大值

循环数组队列

实现目标：（1）根据循环数组构建出循环的队列数据结构

优势：节省资源，运行速度快；

劣势：不能灵活取出

重点：如何实现循环的计算下标语句。

n = (n+1)%array.Length

完整代码：

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace DataStructrue
  8 {
  9     /// 

 10     /// 循环数组
 11     /// （1）添加功能
 12     /// （2）删除功能
 13     /// （3）查询（任何、首尾处）功能
 14     /// （4）修改（任何，首位处）功能
 15     /// 
 16     /// 
 17     class Array2
 18     {
 19         private E[] data;
 20         private int N;
 21         private int first;
 22         private int last;
 23 
 24         public Array2(int capacity)
 25         {
 26             data = new E[capacity];
 27             N = 0;
 28             first = 0;
 29             last = 0;
 30         }
 31         public Array2() : this(10) { }
 32         public int Count { get { return N; } }
 33         public bool IsEmpty { get { return N==0; } }
 34         public E GetFirst()
 35         {
 36             return data[first];
 37         }
 38         /// 

 39         /// 添加一个元素
 40         /// 
 41         /// 
 42         public void Add(E e)
 43         {
 44             if (N==data.Length)
 45             {
 46                 ResetCapacity(data.Length*2);
 47             }
 48             data[last] = e;
 49             last = (last + 1) % data.Length;
 50             N++;
 51         }
 52         /// 

 53         /// 移除早放进的一个元素
 54         /// 
 55         /// 
 56         public E RemoveLast()
 57         {
 58             if (N==0)
 59             {
 60                 throw new ArgumentException("队列已空");
 61             }
 62             if (N<=(data.Length/4))
 63             {
 64                 ResetCapacity(data.Length / 2);
 65             }
 66             E de = data[first];
 67             data[first] = default;
 68             first = (first + 1) % data.Length;
 69             N--;
 70             return de;
 71         }
 72         /// 

 73         /// 移除特定下标元素
 74         /// 消耗大，不建议使用
 75         /// 
 76         /// 
 77         /// 
 78         public E RemoveAt(int index)
 79         {
 80             if (index > data.Length || index < 0 ||N==0)
 81             {
 82                 throw new ArgumentException("非法索引");
 83             }
 84             if (first > last)
 85             {
 86                 if (index < first && index >= last)
 87                 {
 88                     throw new ArgumentException("非法索引");
 89                 }
 90             }
 91             else if (last > first)
 92             {
 93                 if (index < first && index >= last)
 94                 {
 95                     throw new ArgumentException("非法索引");
 96                 }
 97             }
 98             E rd = data[index];
 99             for (int i = index+1; i !=last ; i=(i+1)%data.Length)
100             {
101                 data[i-1] = data[i];
102             }
103             last--;
104             N--;
105             return rd;
106         }
107         /// 

108         /// 移除特定元素
109         /// 消耗大，不建议使用
110         /// 
111         /// 
112         /// 
113         public E Remove(E e)
114         {
115             for (int i = first; i !=last; i=(i+1)%data.Length)
116             {
117                 if (data[i].Equals(e))
118                 {
119                     return RemoveAt(i);
120                 }
121             }
122             return data[last];
123         }
124         /// 

125         /// 对数组进行扩容操作
126         /// 
127         /// 
128         private void ResetCapacity(int newcapacity)
129         {
130             E[] data2 = new E[newcapacity];
131             for (int i = 0; i < N; i++)
132             {
133                 data2[i] = data[first];
134                 first = (first + 1) % data.Length;
135                 last = i+1;
136             }
137             first = 0;
138             data = data2;
139         }
140         public override string ToString()
141         {
142             //实例化
143             StringBuilder res = new();
144             //重写格式1：输出数组元素个数以及长度
145             //res.Append(string.Format("Array1:   count={0}    capacity={1}\n",N,data.Length));
146             res.Append(string.Format("A2Queue: Count = {0} Capacity = {1}\n[", N, data.Length));
147             for (int i = 0; i < N; i++)
148             {
149                 res.Append(data[(first+i)%data.Length]);
150                 if (i!=N-1)
151                 {
152                     res.Append(',');
153                 }
154             }
155             res.Append(']'+"\n");
156             //返回
157             return res.ToString();
158         }
159     }
160 }