与实现栈的方法类似,队列的实现也有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
方法一:数组实现 下图给出了一种最简单的实现方式,用front来记录队列首元素的位置,用rear来记录队列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置,同时rear++,出队列的时候只需要执行front++即可。
为了简化实现,下面代码定义的队列最大的空间为10,实现代码如下所示:
public class Test
{
public class MyQueue<T>
{
private T[] arr;
private int maxSize;//数组中存储元素的个数
private int front;
private int rear;
public MyQueue(int size)
{
maxSize=size; //初始化队列大小
arr=new T[size];
}
//判断队列是否为空
public bool IsEmpty()
{
return front==rear;
}
//判断队列是否已满
public bool IsFull()
{
if (front!=-1)//如果已经有元素出过队
{
//为了区分与IsEmpty的区别,有元素出过队以后,就只有浪费一个位置来保持逻辑正确性。
return (rear+1)%maxSize==front;
}
else
{
return rear==maxSize-1;
}
}
//返回队列的大小
public int Count()
{
if(rear>front)
{
return rear-front;
}
else
{
return (rear-front+maxSize)%maxSize;
}
}
//返回队列首元素
public T Peek()
{
if(IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}
return arr[(front+1)%maxSize];
}
//进队列
public void Enquene(T item)
{
if (IsFull())
{
Console.WriteLine("Queue is full");
return;
}
if (rear==maxSize-1)//如果rear到头了,则循环重来(即解决伪满问题)
{
rear=0;
}
else
{
rear++;
}
arr[rear]=item;
}
//出队列
public T Dequene()
{
if(IsEmpty())
{
Console.WriteLine("Queue is empty");
return default(T);
}
if(front==maxSize-1)//如果front到头了,则重新置0
{
front=0;
}
else
{
front++;
}
return arr[front];
}
}
public static void Main(String[] args)
{
MyQueue<int>queue=new MyQueue<int>(10);
queue.Enquene(1);
queue.Enquene(1);
Console.WriteLine("队首元素为: "+queue.Dequene());
Console.WriteLine("队列大小为: "+queue.Count());
queue.Peek();
Console.WriteLine("取队首成功");
queue.Peek();
Console,Read();
}
}
程序的运行结果为
队首元素为:1
队列大小为:1
取队首成功
以上这种实现方法最大的缺点为:出队列后数组前半部分的空间不能够充分的利用,解决这个问题的方法为把数组看成一个环状的空间(循环队列)。当数组最后一个位置被占用后,可以从数组首位置开始循环利用。
方法二:链表实现 采用链表实现队列的方法与实现栈的方法类似,分别用两个指针指向队列的首元素与尾元素,如下图所示。用pHead来指向队列的首元素,用pEnd来指向队列的尾元素。
在上图中,刚开始队列中只有元素1、2和3,当新元素4要进队列的时候,只需要上图中(1)和(2)两步,就可以把新结点连接到链表的尾部,同时修改pEnd指针指向新增加的结点。出队列的时候只需要(3)一步,改变pHead指针使其指向pHead->next,此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊操作,实现代码如下所示:
public class Test
{
public class MyQueue<T>
{
class LNode<T>
{
public T Data;
public LNode<T> Next;
public LNode(T data)
{
this.Data=data; //初始化队列大小
}
}
private LNode<T> front;//队列头
private LNode<T> rear;//队列尾
private int num;//队列元素个数
public MyQueue()
{
//初始时front,rear置为null, num置0
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)
{
LNode<T>q=new LNode<T>(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);
}
//取链首元素
LNode<T>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 static void Main(String[] args)
{
MyQueue<int> queue=new MyQueue<int>();
queue.Enqueue(1);
queue.Enqueue(1);
Console.WriteLine("队首元素为:"+queue.Dequeue());
Console.WriteLine("队列大小为:"+queue.Count());
queue.Peek();
Console.WriteLine("取队首成功");
queue.Peek();
Console.Read();
}
}
程序的运行结果为
队首元素为:1
队列大小为:1
取队首成功
显然用链表来实现队列有更好的灵活性,与数组的实现方法相比,它多了用来存储节点关系的指针空间。此外,也可以用循环链表来实现队列,这样只需要一个指向链表最后一个元素的指针即可,因为通过指向链表尾元素可以非常容易地找到链表的首结点。