Jimmy.Yang 通过本文主要向大家介绍了马桶c的个人空间,c站,欲情 c max,维生素c,奔驰c200等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
本文实例讲述了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();
}
}
</div>
下面是基于数组实现的示意图：
实现思路：用一个数组存放所有元素，同时设置二个关键变量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(',');
}
}
}
</div>
测试代码片段：
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); Con