首页 > 编程 > C# > 正文

C#数据结构之队列(Quene)实例详解

2020-01-24 01:21:28
字体:
来源:转载
供稿:网友

本文实例讲述了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,4queue.Dequeue();Console.WriteLine(queue);//front = 0    rear = 3    count = 3    data = 2,3,4queue.Dequeue();Console.WriteLine(queue);//front = 1    rear = 3    count = 2    data = 3,4queue.Enqueue(5);Console.WriteLine(queue);//front = 1    rear = 4    count = 3    data = 3,4,5queue.Enqueue(6);Console.WriteLine(queue);//front = 1    rear = 0    count = 4    data = 3,4,5,6queue.Enqueue(7);    //Queue is fullConsole.WriteLine(queue);//front = 1    rear = 0    count = 4    data = 3,4,5,6queue.Dequeue();queue.Enqueue(7);Console.WriteLine(queue);//front = 2    rear = 1    count = 4    data = 4,5,6,7queue.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,4queue.Enqueue(5);Console.WriteLine(queue);//front = -1    rear = 4    count = 5    data = 1,2,3,4,5queue.Enqueue(6);    //Queue is fullConsole.WriteLine(queue);//front = -1    rear = 4    count = 5    data = 1,2,3,4,5queue.Dequeue();queue.Dequeue();queue.Dequeue();queue.Dequeue();Console.WriteLine(queue);//front = 3    rear = 4    count = 1    data = 5queue.Dequeue();Console.WriteLine(queue);//queue is empty.queue.Enqueue(0);queue.Enqueue(1);queue.Enqueue(2);queue.Enqueue(3);queue.Enqueue(4);    //Queue is fullConsole.WriteLine(queue);//front = 4    rear = 3    count = 4    data = 0,1,2,3Console.WriteLine(queue.Peek());//0queue.Dequeue();Console.WriteLine(queue);//front = 0    rear = 3    count = 3    data = 1,2,3queue.Dequeue();Console.WriteLine(queue);//front = 1    rear = 3    count = 2    data = 2,3queue.Dequeue();Console.WriteLine(queue);//front = 2    rear = 3    count = 1    data = 3queue.Dequeue();Console.WriteLine(queue);//queue is empty.queue.Enqueue(9);Console.WriteLine(queue);//front = 3    rear = 4    count = 1    data = 9Console.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#程序设计有所帮助。

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表