当前位置: 移动技术网 > IT编程>开发语言>c# > C#数据结构之队列(Quene)实例详解

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

2019年07月18日  | 移动技术网IT编程  | 我要评论
本文实例讲述了c#数据结构之队列(quene)。分享给大家供大家参考,具体如下: 队列(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#程序设计有所帮助。

如您对本文有疑问或者有任何想说的,请点击进行留言回复,万千网友为您解惑!

相关文章:

验证码:
移动技术网