C#怎么實現泛型動態循環數組隊列

這篇文章主要介紹“C#怎么實現泛型動態循環數組隊列”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C#怎么實現泛型動態循環數組隊列”文章能幫助大家解決問題。

任務

循環數組

實現目標：（1）創建一個新的數組數據結構;

　　　　　（2）該數據結構為泛型;

　　　　　（3）可以按照元素多少進行擴容縮容;

　　　　　（4）進行添加刪除操作的時間復雜度小于O(n);

優勢：在取出放入的操作中消耗的資源更少

劣勢：取出特定元素或特定下標元素平均消耗的資源為普通數組平均消耗資源的最大值

循環數組隊列

實現目標：（1）根據循環數組構建出循環的隊列數據結構

優勢：節省資源，運行速度快；

劣勢：不能靈活取出

重點：如何實現循環的計算下標語句。

循環下標語句

完整代碼：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructrue
{
    /// <summary>
    /// 循環數組
    /// （1）添加功能
    /// （2）刪除功能
    /// （3）查詢（任何、首尾處）功能
    /// （4）修改（任何，首位處）功能
    /// </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>
        /// 添加一個元素
        /// </summary>
        /// <param name="e"></param>
        public void Add(E e)
            if (N==data.Length)
            {
                ResetCapacity(data.Length*2);
            }
            data[last] = e;
            last = (last + 1) % data.Length;
            N++;
        /// 移除早放進的一個元素
        /// <returns></returns>
        public E RemoveLast()
            if (N==0)
                throw new ArgumentException("隊列已空");
            if (N<=(data.Length/4))
                ResetCapacity(data.Length / 2);
            E de = data[first];
            data[first] = default;
            first = (first + 1) % data.Length;
            N--;
            return de;
        /// 移除特定下標元素
        /// 消耗大，不建議使用
        /// <param name="index"></param>
        public E RemoveAt(int index)
            if (index > data.Length || index < 0 ||N==0)
                throw new ArgumentException("非法索引");
            if (first > last)
                if (index < first && index >= last)
                {
                    throw new ArgumentException("非法索引");
                }
            else if (last > first)
            E rd = data[index];
            for (int i = index+1; i !=last ; i=(i+1)%data.Length)
                data[i-1] = data[i];
            last--;
            return rd;
        /// 移除特定元素
        public E Remove(E e)
            for (int i = first; i !=last; i=(i+1)%data.Length)
                if (data[i].Equals(e))
                    return RemoveAt(i);
            return data[last];
        /// 對數組進行擴容操作
        /// <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) % data.Length;
                last = i+1;
            data = data2;
        public override string ToString()
            //實例化
            StringBuilder res = 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");
            //返回
            return res.ToString();
    }
}

補充：c#使用數組實現泛型隊列Quque<T>，以循環的方式使用數組提高性能

隊列簡述

一種先進先出的數據結構

本文主旨

• 提供一個確定容量的高性能隊列的實現

• 更進一步可以對隊列做動態擴容，每次隊列滿了的時候增加隊列容量

• 隊列也可以使用鏈表實現

實現代碼

using System;

namespace DataStructure
{
    /// <summary>
    /// 用數組實現隊列
    /// 用2個index標記開始合結束
    /// </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)
            //隊列滿了
            if (IsFull)
                throw new Exception("queue is full");
            mArray[mEndIndex] = e;
            mCount++;
            //計算下一個位置
            mEndIndex++;
            if (mEndIndex == mCapicity)
                mEndIndex = 0;
        public T Dequeue()
            //隊列空
            if (IsEmpty)
                throw new Exception("queue is empty");
            var r = mArray[mStartIndex];
            //計算下一次取元素的index
            //取出元素后增加start
            mStartIndex++;
            //到達尾部，開始循環，下一次從頭開始取
            if (mStartIndex == mCapicity)
                mStartIndex = 0;
            mCount--;
            return r;
    }
}

測試代碼

namespace DataStructure
{
    public class ArrayQueueTest : BaseSolution
    {
        public void Test()
        {
            var queue = new ArrayQueue<int>(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());
            }
        }
    }
}

關于“C#怎么實現泛型動態循環數組隊列”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。