C#泛型动态循环数组队列

时间:2022-05-23 Mib_D 人气:0

任务

循环数组

实现目标：（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());
            }
        }
    }
}

加载全部内容