C#数据结构之队列(Quene)实例详解
本文实例讲述了C#数据结构之队列(Quene)。分享给大家供大家参考,具体如下:
队列(Quene)的特征就是“先进先出”,队列把所有操作限制在"只能在线性结构的两端"进行,更具体一点:添加元素必须在线性表尾部进行,而删除元素只能在线性表头部进行。
先抽象接口IQuene<T>
namespace 栈与队列 { public interface IQuene<T> { /// <summary> /// 取得队列实际元素的个数 /// </summary> /// <returns></returns> public int Count(); /// <summary> /// 判断队列是否为空 /// </summary> /// <returns></returns> public bool IsEmpty(); /// <summary> /// 清空队列 /// </summary> public void Clear(); /// <summary> /// 入队(即向队列尾部添加一个元素) /// </summary> /// <param name="item"></param> public void Enquene(T item); /// <summary> /// 出队(即从队列头部删除一个元素) /// </summary> /// <returns></returns> public T Dequene(); /// <summary> /// 取得队列头部第一元素 /// </summary> /// <returns></returns> public T Peek(); } }
下面是基于数组实现的示意图:
实现思路:用一个数组存放所有元素,同时设置二个关键变量front与rear用于记录队列“头”与“尾”的元素下标,当有元素入列时rear加1,当有元素出队时front+1,而rear-front即为队列实际元素的总数.
但有一种“队列伪满”的特殊情况要注意,如下图:
这张图上面的部分:假设经过入队、出队一番折腾后,rear已经指向数组的下标最大值,而front指向在中间(即front之间的元素已经出队不用考虑了,相当于front下标前面的内存区域空闲),如果这时再有一个元素入列,rear+1就超出数组下标的最大值了,但是从图上一眼就能看出,实际上front前面还空着一堆位置可以重复利用,队列并非真正的“满”--这种情况称为伪满,为了解决这个问题,我们可以把数组想象为首尾相接的循环结构,即图中下面部分,这时候可以让rear重新指向到0,以便重复利用空闲的位置。
所以:入列时rear++的操作,应该稍做修正,当rear到数组下标最大值时,让它置0,以便能循环利用 (见后面的代码)
另外还有一个问题:最开始时front与rear都为-1,即front==rear时表示队列为空,改成循环以后,有可能会出现rear在循环过程中碰到front的情况,即真正意义的上"满"状态,这时rear也同样等于front,这样就无法单纯的用rear==front来判断是满,还是空?这时可以浪费一个元素的位置,认为当rear+1==front时,队列就已经满了,虽然牺牲了一个元素的空间,但却换来了逻辑的正确性,还是值得的。
完整实现如下:
using System; using System.Text; namespace 栈与队列 { /// <summary> /// 循环顺序队列 /// </summary> /// <typeparam name="T"></typeparam> public class CSeqQueue<T>:IQueue<T> { private int maxsize; private T[] data; private int front; private int rear; public CSeqQueue(int size) { data = new T[size]; maxsize = size; front = rear = -1; } public int Count() { if (rear > front) { return rear - front; } else { return (rear - front + maxsize) % maxsize; } } public void Clear() { front = rear = -1; } public bool IsEmpty() { return front == rear; } public bool IsFull() { if (front != -1) //如果已经有元素出队过 { return (rear + 1) % maxsize == front;//为了区分与IsEmpty的区别,有元素出队过以后,就只有浪费一个位置来保持逻辑正确性. } else { return rear == maxsize - 1; } } public void Enqueue(T item) { if (IsFull()) { Console.WriteLine("Queue is full"); return; } if (rear == maxsize - 1) //如果rear到头了,则循环重来(即解决伪满问题) { rear = 0; } else { rear++; } data[rear] = item; } public T Dequeue() { if (IsEmpty()) { Console.WriteLine("Queue is empty"); return default(T); } if (front == maxsize - 1) //如果front到头了,则重新置0 { front = 0; } else { front++; } return data[front]; } public T Peek() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } return data[(front + 1) % maxsize]; } public override string ToString() { if (IsEmpty()) { return "queue is empty."; } StringBuilder sb = new StringBuilder(); if (rear > front) { for (int i = front + 1; i <= rear; i++) { sb.Append(this.data[i].ToString() + ","); } } else { for (int i = front + 1; i < maxsize; i++) { sb.Append(this.data[i].ToString() + ","); } for (int i = 0; i <= rear; i++) { sb.Append(this.data[i].ToString() + ","); } } return "front = " + this.front + " \t rear = " + this.rear + "\t count = " + this.Count() + "\t data = " + sb.ToString().Trim(','); } } }
测试代码片段:
CSeqQueue<int> queue = new CSeqQueue<int>(5); queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); Console.WriteLine(queue);//front = -1 rear = 3 count = 4 data = 1,2,3,4 queue.Dequeue(); Console.WriteLine(queue);//front = 0 rear = 3 count = 3 data = 2,3,4 queue.Dequeue(); Console.WriteLine(queue);//front = 1 rear = 3 count = 2 data = 3,4 queue.Enqueue(5); Console.WriteLine(queue);//front = 1 rear = 4 count = 3 data = 3,4,5 queue.Enqueue(6); Console.WriteLine(queue);//front = 1 rear = 0 count = 4 data = 3,4,5,6 queue.Enqueue(7); //Queue is full Console.WriteLine(queue);//front = 1 rear = 0 count = 4 data = 3,4,5,6 queue.Dequeue(); queue.Enqueue(7); Console.WriteLine(queue);//front = 2 rear = 1 count = 4 data = 4,5,6,7 queue.Clear(); Console.WriteLine(queue);//queue is empty. queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); Console.WriteLine(queue);//front = -1 rear = 3 count = 4 data = 1,2,3,4 queue.Enqueue(5); Console.WriteLine(queue);//front = -1 rear = 4 count = 5 data = 1,2,3,4,5 queue.Enqueue(6); //Queue is full Console.WriteLine(queue);//front = -1 rear = 4 count = 5 data = 1,2,3,4,5 queue.Dequeue(); queue.Dequeue(); queue.Dequeue(); queue.Dequeue(); Console.WriteLine(queue);//front = 3 rear = 4 count = 1 data = 5 queue.Dequeue(); Console.WriteLine(queue);//queue is empty. queue.Enqueue(0); queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); //Queue is full Console.WriteLine(queue);//front = 4 rear = 3 count = 4 data = 0,1,2,3 Console.WriteLine(queue.Peek());//0 queue.Dequeue(); Console.WriteLine(queue);//front = 0 rear = 3 count = 3 data = 1,2,3 queue.Dequeue(); Console.WriteLine(queue);//front = 1 rear = 3 count = 2 data = 2,3 queue.Dequeue(); Console.WriteLine(queue);//front = 2 rear = 3 count = 1 data = 3 queue.Dequeue(); Console.WriteLine(queue);//queue is empty. queue.Enqueue(9); Console.WriteLine(queue);//front = 3 rear = 4 count = 1 data = 9 Console.ReadLine();
当然,队列也可以用链表来实现,相对要容易很多。
先定义链表中的节点Node.cs
namespace 栈与队列 { public class Node<T> { private T data; private Node<T> next; public Node(T data, Node<T> next) { this.data = data; this.next = next; } public Node(Node<T> next) { this.next = next; this.data = default(T); } public Node(T data) { this.data = data; this.next = null; } public Node() { this.data = default(T); this.next = null; } public T Data { get { return this.data; } set { this.data = value; } } public Node<T> Next { get { return next; } set { next = value; } } } }
为了方便,定义了很多构造函数的重载版本,当然这些只是浮云,重点是理解结构:data用来保存数据,next指出下一个节点是谁
链式队列的完整实现LinkQueue.cs
using System; using System.Text; namespace 栈与队列 { public class LinkQueue:IQueue { private Node front;//队列头 private Node rear;//队列尾 private int num;//队列元素个数 /// /// 构造器 /// public LinkQueue() { //初始时front,rear置为null,num置0 front = rear = null; num = 0; } public int Count() { return this.num; } public void Clear() { front = rear = null; num = 0; } public bool IsEmpty() { return (front == rear && num == 0); } //入队 public void Enqueue(T item) { Node q = new Node(item); if (rear == null)//第一个元素入列时 { front = rear = q; } else { //把新元素挂到链尾 rear.Next = q; //修正rear指向为最后一个元素 rear = q; } //元素总数+1 num++; } //出队 public T Dequeue() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } //取链首元素 Node p = front; //链头指向后移一位 front = front.Next; //如果此时链表为空,则同步修正rear if (front == null) { rear = null; } num--;//个数-1 return p.Data; } public T Peek() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } return front.Data; } public override string ToString() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); } StringBuilder sb = new StringBuilder(); Node node = front; sb.Append(node.Data.ToString()); while (node.Next!=null) { sb.Append("," + node.Next.Data.ToString()); node = node.Next; } return sb.ToString().Trim(','); } } }
希望本文所述对大家C#程序设计有所帮助。
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25