C#实现泛型动态循环数组队列的方法
作者:Mib_D 发布时间:2022-11-03 05:05:42
标签: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());
}
}
}
}
来源:https://www.cnblogs.com/yotomib/p/15854490.html
0
投稿
猜你喜欢
- Android 消息机制1.概述Android应用启动时,会默认有一个主线程(UI线程),在这个线程中会关联一个消息队列(MessageQu
- 本文以一个C#的SQL数据库字串操作函数为例,说明如何实现对SQL字符串过滤、检测SQL是否有危险字符、修正sql语句中的转义字符,确保SQ
- 一、目的针对不同地区,设置不同的语言信息。SpringBoot国际化配置文件默认放在classpath:message.properties
- 第1部分 ArrayList介绍ArrayList简介ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量
- QR 二维码中插入图片二维码终于火了,现在大街小巷大小商品广告上的二维码标签都随处可见,而且大都不是简单的纯二维码,而是中间有个性图标的二维
- 我就废话不多说了,大家还是直接看代码吧~ public static void main(String[] args) { &n
- 1 使用阿里的FastJson1.1 项目的pom.xml依赖<dependency> <groupId>com.a
- 完成支付宝支付、查询的接口之后,我们应该还需要定时与支付宝进行对账,以确保商户系统的订单信息是正确的,想知道支付宝支付、查询接口实现过程的亲
- 我们都知道,当RecyclerView数据源更新后,还需要通过adapter调用对应的方法,从而让RecyclerView重新绘制页面本次也
- 本文为大家分享的java算法计算阶乘,在学习Java课程时经常会遇到求阶乘问题,今天接跟大家一起探讨一下代码如下:package com.x
- 刚开始学习C#的时候,就听说CLR对于String类有一种特别的内存管理机制:有时候,明明声明了两个String类的对象,但是他们偏偏却指向
- JAVA操作XML文档主要有四种方式,分别是DOM、SAX、JDOM和DOM4J,DOM和SAX是官方提供的,而JDOM和DOM4J则是引用
- 1.概述在本快速教程中,我们将学习如何设置Spring Security LDAP。在我们开始之前,了解一下LDAP是什么? - 它代表轻量
- 本文实例讲述了C#格式化json字符串的方法。分享给大家供大家参考,具体如下:将Json字符串转化成格式化表示的方法: 字符串反序列化为对象
- 调用SAP WebService服务需要转换操作1、通过浏览器访问SAP WebService地址,进行验证并生成wsdl文件地址并不是可以
- 井字棋游戏要求在3乘3棋盘上,每行都相同或者每列都相同再或者对角线相同,则胜出.因此我们可以使用一个二维数组来表示棋盘,判断胜负只需要判断数
- Idea中directory和package的区别,要是错了就右键,make directory as 目录或者源代码目录(Source R
- 1集合的概念把集合看做是一个容器,集合不是一个类,是一套集合框架,框架体系包含很多的集合类,java api提供了集合存储任意类型(基本包装
- SpringCloud简介Spring cloud是一个基于Spring Boot实现的服务治理工具包,在微服务架构中用于管理和协调服务的微
- static目的java中的static关键字主要用于内存管理。static范围使用范围:java static关键字可以用在变量、方法、代