C#实现泛型动态循环数组队列的方法

第C#实现泛型动态循环数组队列的方法（3）可以按照元素多少进行扩容缩容;

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

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

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

循环数组队列

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

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

劣势：不能灵活取出

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

循环下标语句

完整代码：

usingSystem;

usingSystem.Collections.Generic;

usingSystem.Linq;

usingSystem.Text;

usingSystem.Threading.Tasks;

namespaceDataStructrue

///summary

///循环数组

///（1）添加功能

///（2）删除功能

///（3）查询（任何、首尾处）功能

///（4）修改（任何，首位处）功能

////summary

///typeparamname="E"/typeparam

classArray2E

privateE[]data;

privateintN;

privateintfirst;

privateintlast;

publicArray2(intcapacity)

data=newE[capacity];

N=0;

first=0;

last=0;

publicArray2():this(10){}

publicintCount{get{returnN;}}

publicboolIsEmpty{get{returnN==0;}}

publicEGetFirst()

returndata[first];

///summary

///添加一个元素

////summary

///paramname="e"/param

publicvoidAdd(Ee)

if(N==data.Length)

ResetCapacity(data.Length*2);

data[last]=e;

last=(last+1)%data.Length;

N++;

///移除早放进的一个元素

///returns/returns

publicERemoveLast()

if(N==0)

thrownewArgumentException("队列已空");

if(N=(data.Length/4))

ResetCapacity(data.Length/2);

Ede=data[first];

data[first]=default;

first=(first+1)%data.Length;

N--;

returnde;

///移除特定下标元素

///消耗大，不建议使用

///paramname="index"/param

publicERemoveAt(intindex)

if(indexdata.Length||index0||N==0)

thrownewArgumentException("非法索引");

if(firstlast)

if(indexfirstindex=last)

thrownewArgumentException("非法索引");

elseif(lastfirst)

Erd=data[index];

for(inti=index+1;i!=last;i=(i+1)%data.Length)

data[i-1]=data[i];

last--;

returnrd;

///移除特定元素

publicERemove(Ee)

for(inti=first;i!=last;i=(i+1)%data.Length)

if(data[i].Equals(e))

returnRemoveAt(i);

returndata[last];

///对数组进行扩容操作

///paramname="newcapacity"/param

privatevoidResetCapacity(intnewcapacity)

E[]data2=newE[newcapacity];

for(inti=0;ii++)

data2[i]=data[first];

first=(first+1)%data.Length;

last=i+1;

data=data2;

publicoverridestringToString()

//实例化

StringBuilderres=new();

//重写格式1：输出数组元素个数以及长度

//res.Append(string.Format("Array1:count={0}capacity={1}\n",N,data.Length));

res.Append(string.Format("A2Queue:Count={0}Capacity={1}\n[",N,data.Length));

res.Append(data[(first+i)%data.Length]);

if(i!=N-1)

res.Append(',');

res.Append(']'+"\n");

//返回

returnres.ToString();

}

补充：c#使用数组实现泛型队列QuqueT，以循环的方式使用数组提高性能

一种先进先出的数据结构

提供一个确定容量的高性能队列的实现更进一步可以对队列做动态扩容，每次队列满了的时候增加队列容量队列也可以使用链表实现

usingSystem;

namespaceDataStructure

///summary

///用数组实现队列

///用2个index标记开始合结束

////summary

///typeparamname="T"/typeparam

publicclassArrayQueueT

privateintmCapicity;

privateintmStartIndex;

privateintmEndIndex;

privateintmCount;

privateT[]mArray;

publicArrayQueue(intcapicity)

mCapicity=capicity;

mArray=newT[capicity];

publicintCount

returnmCount;

publicboolIsFull

returnmCount==mCapicity;

publicintCapicity

get{returnmCapicity;}

publicboolIsEmpty

returnmCount==0;

publicvoidClear()

mStartIndex=0;

mEndIndex=0;

mCount=0;

mCapicity=0;

mArray=null;

publicvoidEnqueue(Te)

//队列满了

if(IsFull)

thrownewException("queueisfull");

mArray[mEndIndex]=e;

mCount++;

//计算下一个位置

mEndIndex++;

if(mEndIndex==mCapicity)

mEndIndex=0;

publicTDequeue()

//队列空

if(IsEmpty)

thrownewException("queueisempty");

varr=mArray[mStartIndex];

//计算下一次取元素的index

//取出元素后增加start

mStartIndex++;

//到达尾部，开始循环，下一次从头开始取

if(mStartIndex==mCapicity)

mStartIndex=0;

mCount--;

returnr;

}

测试代码

namespaceDataStructure

publicclassArrayQueueTest:BaseSolution

publicvoidTest()

varqueue=newArrayQueueint

queue.Enqueue(1);

queue.En