C#环形队列的实现方法详解
作者:独孤飞 发布时间:2021-06-04 00:38:37
一、环形队列是什么
队列是一种常用的数据结构,这种结构保证了数据是按照“先进先出”的原则进行操作的,即最先进去的元素也是最先出来的元素.环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。
二、环形队列的优点
1.保证元素是先进先出的
是由队列的性质保证的,在环形队列中通过对队列的顺序访问保证。
2.元素空间可以重复利用
因为一般的环形队列都是一个元素数固定的一个闭环,可以在环形队列初始化的时候分配好确定的内存空间,当进队或出队时只需要返回指定元素内存空间的地址即可,这些内存空间可以重复利用,避免频繁内存分配和释放的开销。
3.为多线程数据通信提供了一种高效的机制。
在最典型的生产者消费者模型中,如果引入环形队列,那么生成者只需要生成“东西”然后放到环形队列中即可,而消费者只需要从环形队列里取“东西”并且消费即可,没有任何锁或者等待,巧妙的高效实现了多线程数据通信。
三、C#环形队列的实现
看了一个数据结构的教程,是用C++写的,可自己C#还是一个菜鸟,更别说C++了,但还是大胆尝试用C#将其中的环形队列的实现写出来,先上代码:
public class MyQueue<T> : IDisposable
{
private T[] queue;
private int length;
private int capacity;
private int head = 0;
private int tail = 0;
public MyQueue(int capacity) {
this.capacity = capacity;
this.head = 0;
this.tail = 0;
this.length = 0;
this.queue = new T[capacity];
}
public void Clear() {
head = 0;
tail = 0;
length = 0;
}
public bool IsEmpty() {
return length == 0;
}
public bool IsFull() {
return length == capacity;
}
public int Length() {
return length;
}
public bool EnQueue(T node) {
if (!IsFull()) {
queue[tail] = node;
tail = (++tail) % capacity;
length++;
return true;
}
return false;
}
public T DeQueue() {
T node = default(T);
if (!IsEmpty()) {
node = queue[head];
head = (++head) % capacity;
length--;
}
return node;
}
public void Traverse() {
for (int i = head; i < length + head; i++) {
Console.WriteLine(queue[i % capacity]);
Console.WriteLine($"前面还有{i - head}个");
}
}
public void Dispose() {
queue = null;
}
}
为了能够通用,所以用的是泛型来实现环形队列类。这里最重要的是进队(EnQueue
)和出队(DeQueue
)两个方法,进队或出队后头和尾的位置都要通过取模运算来获得,因为是环形队列嘛,你懂的。
1、简单类型队列
好了,测试下入队:
class Program
{
static void Main(string[] args) {
MyQueue<int> queue = new MyQueue<int>(4);
queue.EnQueue(10);
queue.EnQueue(16);
queue.EnQueue(18);
queue.EnQueue(12);
queue.Traverse();
Console.Read();
}
}
显示结果:
再测试下出队:
class Program
{
static void Main(string[] args) {
MyQueue<int> queue = new MyQueue<int>(4);
queue.EnQueue(10);
queue.EnQueue(16);
queue.EnQueue(18);
queue.EnQueue(12);
queue.Traverse();
Console.WriteLine("弹两个出去");
queue.DeQueue();
queue.DeQueue();
Console.WriteLine();
queue.Traverse();
Console.Read();
}
}
运行结果:
2、复杂类型队列
之前也说了,这个队列类是用的泛型写的,对应于C++的模板了,那就意味着任何类型都可以使用这个队列类,来测试个自定义的类试试,如下先定义一个Customer
类:
public class Customer
{
public string Name { get; set; }
public int Age { get; set; }
public void PringInfo() {
Console.WriteLine("姓名:" + Name);
Console.WriteLine("年龄:" + Age);
Console.WriteLine();
}
}
然后进行入队,如下:
class Program
{
static void Main(string[] args) {
MyQueue<Customer> queue = new MyQueue<Customer>(5);
queue.EnQueue(new Customer() { Name = "宋小二", Age = 29 });
queue.EnQueue(new Customer() { Name = "陈小三", Age = 28 });
queue.EnQueue(new Customer() { Name = "王小四", Age = 26 });
queue.EnQueue(new Customer() { Name = "朱小五", Age = 48 });
for (int i = 0; i < queue.Length(); i++) {
queue[i].PringInfo();
}
Console.Read();
}
}
上面的代码 queue[i].PringInfo();
是通过索引来实现,所以我们得在队列类中实现索引,添加如下代码到MyQueue.cs
类中,如下:
public T this[int index] {
get {
return queue[index];
}
}
感觉用for循环来遍历还是不够好,想用foreach
,那就给MyQueue
类加个遍历接口,如下:
然后实现这个接口,如下:
public IEnumerator<T> GetEnumerator() {
foreach(T node in queue) {
if(node != null) {
yield return node;
}
}
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
这样遍历的地方就可以改成foreach
了,如下:
执行结果:
总结:
编程的思想才是最重要的,无关语言。以上就是这篇文章的全部内容了,希望能对大家的学习或者工作带来一定的帮助,如果有疑问大家可以留言交流。
猜你喜欢
- 一、管理网络状态使用网络进行数据通信前,需要先获取网络状态。使用ConnectivityManager获取网络状态步骤:1.获取Connec
- Spring Security支持在响应中添加各种安全头默认相应安全头:Cache-Control: no-cache, no-store,
- 我们知道,Object类是所有类的父类,因此也被称为根类、祖先。那么,我们就来看一看Object类的最常用的两个方法是如何用的。1.toSt
- 在springboot中,默认继承好了一套完好的redis包,可以直接使用,但是如果使用中出了错不容易找到错误的原因,因此这里使用自己配置的
- 缓存可以说是加速服务响应速度的一种非常有效并且简单的方式。在缓存领域,有很多知名的框架,如EhCache 、Guava、HazelCast等
- 想必大家都知道,国内的Android应用基本都是免费的
- 什么是ServletContext?根据字面意思即Servlet上下文服务器会为每一个工程创建一个对象,这个对象就是ServletConte
- 本文实例为大家分享了Java实现人机猜拳游戏的具体代码,供大家参考,具体内容如下实现:User类public class User { pr
- Jmeter 执行Java 请求时,运行结束后报错,Tidying up remote @ Mon Feb 24 19:42:34 CST
- 这种属性应用方式是field_name=@field_value@。两个@符号是springboot为替代${}属性占位符产生,原因是${}
- 端口设置和contextpath的配置端口设置Spring boot 默认端口是8080,如果想要进行更改的话,只需要修改applicato
- 本文实例讲述了C#对图片文件的压缩、裁剪操作方法,在C#项目开发中非常有实用价值。分享给大家供大家参考。具体如下:一般在做项目时,对图片的处
- 概述最近项目上反馈某个重要的定时任务突然不执行了,很头疼,开发环境和测试环境都没有出现过这个问题。定时任务采用的是ScheduledThre
- java文字识别程序的关键是寻找一个可以调用的OCR引擎。tesseract-ocr就是一个这样的OCR引擎,在1985年到1995年由HP
- 为什么要给图片添加水印为图片添加水印的主要作用是保护图片版权,防止图片被未经授权的人使用或传播。通常情况下,图片水印会包含图片作者的名字、版
- 1, 泛型接口的协变如果泛型类型用out关键字标注,泛型接口就是协变的。这也意味着返回类型只能是T。泛型接口的抗变如果泛型类型用in关键字标
- 进行数据源或者 FTP 服务器等资源配置时,我们可以将这些配置信息放到一个独立的外部属性文件中,并在 Spring 配置文件中通过形如 ${
- 在C#中,可以使用一些第三方库或内置类库实现动态执行脚本的功能。以下是几个常用的方案:1.使用Roslyn编译器Roslyn是微软推出的一个
- 简介Springboot Admin是一个管理和监控Springboot项目的组件,分为服务端和客户端,两端通过http进行通信。由于其轻量
- 前言最近在开发一个IM项目的时候有一个需求就是,好友搜索功能。即在EditText中输入好友名字,ListView列表中动态展示刷选的好友列