Task
Loop array
Achieve the goal: (1) Create a new array data structure;
(2) This data structure is a generic;
(3) The capacity can be expanded and reduced according to the number of elements;
(4) The time complexity of the addition and deletion operation is less than O(n);
Advantages: Less resources are consumed in the operation of taking out and putting in
Disadvantages: The average resource consumed by taking out a specific element or a specific subscript element is the maximum value of the average resource consumed by a normal array.
Loop array queue
Achieving the goal: (1) Construct a loop queue data structure based on the loop array
Advantages: Save resources and run fast;
Disadvantage: Not flexible to remove
Key point: How to implement loop calculation subscript statements.
Looping the slogan
Complete code:
using System;
using ;
using ;
using ;
using ;
namespace DataStructrue
{
/// <summary>
/// Loop array /// (1) Add function /// (2) Delete function /// (3) Query (any, beginning and end) function /// (4) Modify (any, first place) function /// </summary>
/// <typeparam name="E"></typeparam>
class Array2<E>
{
private E[] data;
private int N;
private int first;
private int last;
public Array2(int capacity)
{
data = new E[capacity];
N = 0;
first = 0;
last = 0;
}
public Array2() : this(10) { }
public int Count { get { return N; } }
public bool IsEmpty { get { return N==0; } }
public E GetFirst()
return data[first];
/// <summary>
/// Add an element /// </summary>
/// <param name="e"></param>
public void Add(E e)
if (N==)
{
ResetCapacity(*2);
}
data[last] = e;
last = (last + 1) % ;
N++;
/// Remove an element that was put in early /// <returns></returns>
public E RemoveLast()
if (N==0)
throw new ArgumentException("Quote is empty");
if (N<=(/4))
ResetCapacity( / 2);
E de = data[first];
data[first] = default;
first = (first + 1) % ;
N--;
return de;
/// Remove specific subscript elements /// It consumes a lot and is not recommended to use it /// <param name="index"></param>
public E RemoveAt(int index)
if (index > || index < 0 ||N==0)
throw new ArgumentException("Illegal Index");
if (first > last)
if (index < first && index >= last)
{
throw new ArgumentException("Illegal Index");
}
else if (last > first)
E rd = data[index];
for (int i = index+1; i !=last ; i=(i+1)%)
data[i-1] = data[i];
last--;
return rd;
/// Remove specific elements public E Remove(E e)
for (int i = first; i !=last; i=(i+1)%)
if (data[i].Equals(e))
return RemoveAt(i);
return data[last];
/// Extend the array /// <param name="newcapacity"></param>
private void ResetCapacity(int newcapacity)
E[] data2 = new E[newcapacity];
for (int i = 0; i < N; i++)
data2[i] = data[first];
first = (first + 1) % ;
last = i+1;
data = data2;
public override string ToString()
//Instantiation StringBuilder res = new();
//Rewrite format 1: Output the number and length of array elements //(("Array1: count={0} capacity={1}\n",N,));
(("A2Queue: Count = {0} Capacity = {1}\n[", N, ));
(data[(first+i)%]);
if (i!=N-1)
(',');
(']'+"\n");
//return return ();
}
}Supplement: c# uses arrays to implement generic queue Quque<T>, and uses arrays to improve performance in a loop
Queue brief description
A first-in-first-out data structure
The main theme of this article
- Provides an implementation of a high-performance queue with a determined capacity
- Going further, you can dynamically expand the queue and increase the queue capacity every time the queue is full.
- Queues can also be implemented using linked lists
Implement code
using System;
namespace DataStructure
{
/// <summary>
/// Implement queues with arrays /// Use 2 index marks to start and end /// </summary>
/// <typeparam name="T"></typeparam>
public class ArrayQueue<T>
{
private int mCapicity;
private int mStartIndex;
private int mEndIndex;
private int mCount;
private T[] mArray;
public ArrayQueue(int capicity)
{
mCapicity = capicity;
mArray = new T[capicity];
}
public int Count
get
{
return mCount;
}
public bool IsFull
return mCount == mCapicity;
public int Capicity
get { return mCapicity; }
public bool IsEmpty
return mCount == 0;
public void Clear()
mStartIndex = 0;
mEndIndex = 0;
mCount = 0;
mCapicity = 0;
mArray = null;
public void Enqueue(T e)
//The queue is full if (IsFull)
throw new Exception("queue is full");
mArray[mEndIndex] = e;
mCount++;
//Calculate the next position mEndIndex++;
if (mEndIndex == mCapicity)
mEndIndex = 0;
public T Dequeue()
//The queue is empty if (IsEmpty)
throw new Exception("queue is empty");
var r = mArray[mStartIndex];
// Calculate the index of the next element to be retrieved //Add start after removing the element mStartIndex++;
//Add to the tail, start the cycle, and start from the beginning next time if (mStartIndex == mCapicity)
mStartIndex = 0;
mCount--;
return r;
}
}Test code
namespace DataStructure
{
public class ArrayQueueTest : BaseSolution
{
public void Test()
{
var queue = new ArrayQueue<int>(4);
(1);
(2);
(3);
(4);
// println();
// println();
println(());
(5);
while (!)
{
println(());
}
}
}
}This is the end of this article about C# implementing generic dynamic loop array queues. For more related contents of C# generic dynamic loop array queues, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!