How to implement generic dynamic cyclic Array queue in C #

This article mainly introduces the relevant knowledge of "how to realize generic dynamic circular array queue in C#". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope this article "how to realize generic dynamic circular array queue in C#" can help you solve the problem.

Task loop array

Achieve the goal: (1) create a new array data structure

(2) the data structure is generic.

(3) you can expand and reduce capacity according to the number of elements.

(4) the time complexity of adding and deleting operation is less than O (n).

Advantage: fewer resources are consumed in the take-out and put-in operation

Disadvantages: the average resource consumed by a specific element or specific subscript element is the maximum of the average resource consumed by an ordinary array.

Cyclic array queue

To achieve the goal: (1) to build a cyclic queue data structure based on a circular array

Advantages: save resources and run fast

Disadvantage: unable to take it out flexibly

Key point: how to realize the loop calculation subscript statement.

Slogan sentence under the loop

Complete code:

Using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks Namespace DataStructrue {/ circular array / (1) add function / (2) delete function / (3) query (any, head and tail) function / (4) modify (any, first place) function / class Array2 {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 nodes 0 }} public E GetFirst () return data [first]; / add an element / public void Add (E) if (N==data.Length) {ResetCapacity (data.Length*2);} data [last] = e Last = (last + 1)% data.Length; Nationals; / / remove an element previously placed / public E RemoveLast () if (empty 0) throw new ArgumentException ("queue is empty"); if (N data.Length | | index

< 0 ||N==0) throw new ArgumentException("非法索引"); 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 = (iindex 1)% data.Length) data [I-1] = data [I]; last-- Return rd; / / remove a specific element public E Remove (E) for (int I = first; I! = last; I = (iDev 1)% data.Length) if (data [I] .equals (e)) return RemoveAt (I); return data [last] / / expand the array / private void ResetCapacity (int newcapacity) E [] data2 = new E [newcapacity]; for (int I = 0; I < N; iBev +) data2 [I] = data [first]; first = (first + 1)% data.Length; last = iArray 1; data = data2 Public override string ToString () / / instantiate StringBuilder res = new (); / / rewrite format 1: output array element number and length / / res.Append (string.Format ("Array1: count= {0} capacity= {1}\ n", NMagneData.Length)) Res.Append (string.Format ("A2Queue: Count = {0} Capacity = {1}\ n [", N, data.Length)); res.Append (data [(first+i)% data.Length]); if (iTunes Nmur1) res.Append (','); res.Append (']'+ "\ n") / / return return res.ToString ();}}

Add: C # uses arrays to implement generic queue Quque, using arrays in a circular manner to improve performance

Brief description of the queue

A FIFO data structure

The purpose of this article

Provides an implementation of a high-performance queue with a determined capacity

Furthermore, the queue can be expanded dynamically to increase the queue capacity every time the queue is full.

Queues can also be implemented using linked lists

The implementation code using System;namespace DataStructure {/ implements the queue with an array / starts and ends with two index tags / public class ArrayQueue {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) / / queue full of if (IsFull) throw new Exception ("queue is full"); mArray [mEndIndex] = e; mCount++ / / calculate the next location mEndIndex++; if (mEndIndex = = mCapicity) mEndIndex = 0; public T Dequeue () / queue empty if (IsEmpty) throw new Exception ("queue is empty"); var r = mArray [mStartIndex] / / calculate the index / / of the next fetch element, add start mStartIndex++; / / to the tail, start the loop, and next time fetch if (mStartIndex = = mCapicity) mStartIndex = 0; mCount--; return r;}}

Test code

Namespace DataStructure {public class ArrayQueueTest: BaseSolution {public void Test () {var queue = new ArrayQueue (4); queue.Enqueue (1); queue.Enqueue (2); queue.Enqueue (3); queue.Enqueue (4); / / println (queue.Capicity); / / println (queue.Count) Println (queue.Dequeue ()); queue.Enqueue (5); while (! queue.IsEmpty) {println (queue.Dequeue ());} that's all about how C # implements a generic dynamic circular array queue. Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.