1、順序結構描述的隊列
在這一章中，我們選擇用Rear隊尾的指針來指示最后一個入隊的元素在隊列中的位置。我們選擇隊列內存儲的數組的Data[0]作為隊頭，每次取數據的時候，隊頭彈出(out)。具體的代碼如下所示：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure.Queue
{
class SeqQueue<T>: IQueue<T>
{
int Rear =-1;//隊尾
constint MaxSize=100;//隊列的最大容量
T[] Data =new T[MaxSize];//一個數組
public SeqQueue()
{
}
public SeqQueue(T[] data)
{
Array.Copy(data,this.Data,data.Length);
Rear = data.Length -1;
}
publicint GetLength(out States states)
{
if(Rear==-1)
{
states = States.Fail;
return0;
}
else
{
states = States.Success;
return Rear +1;
}
}
publicbool IsEmpty()
{
return Rear ==-1?true:false;
}
publicvoid Clear()
{
Rear =-1;
}
privatebool isFull(){
return Rear +1== MaxSize ?true:false;
}
publicvoid In(T item,out States states)
{
if(isFull())
{
states = States.Fail;
return;
}
this.Data[++Rear]= item;
states = States.Success;
}
public T Out(out States states)
{
//判斷隊列是否為空
if(IsEmpty())
{
states = States.Fail;
returndefault(T);
}
States mStates;
//當隊列中只有一個元素的時候
if(this.GetLength(out mStates)==1)
{
Rear--;
states = States.Success;
returnthis.Data[0];
}
//普通的情況
//(1)將所有元素往前移動一位
T DataToOut=this.Data[0];
for(int i =1; i <this.GetLength(out mStates); i++)
{
this.Data[i -1]=this.Data[i];
}
--Rear;
states = States.Success;
//(2)返回要彈出的值
return DataToOut;
}
public T GetFront(out States states)
{
if(this.IsEmpty()==true)
{
states = States.Fail;
returndefault(T);
}
else
{
states= States.Success;
return Data[0];//返回隊頭的元素
}
}
}
}
從代碼的實現上看，這種實現的方式有一種明顯缺點：那就是每次當我們出隊一個元素的時候，我們都需要將除隊頭外的元素全部往前移動一個，這樣子的時間復雜度為O(n)。我們將在循環隊列中討論相應的解決方案。
2、循環隊列
在循環隊列中，比較困難的地方就是在隊列長度和是否為滿的判斷。由于這方面的教程很多，大家可自行百度。另外，隊頭（Front）和隊尾（Rear）的初始化位置（比如以下代碼中是Front=0,Rear=0，如果改為Front=0,Rear=-1呢？）將會極大地影響代碼的書寫。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure.Queue
{
/// <summary>
/// 循環隊列
/// </summary>
class CSeqQueue<T>: IQueue<T>
{
int Front =0;//隊頭
int Rear =0;//隊尾
constint MaxSize =4;//隊列的最大容量
T[] Data =new T[MaxSize];//一個數組
public CSeqQueue()
{
}
public CSeqQueue(int[] data)
{
Array.Copy(data,this.Data, data.Length);
Rear = data.Length -1;
}
publicint GetLength()
{
return(Rear - Front + MaxSize)% MaxSize;
}
publicbool IsEmpty()
{
returnthis.GetLength()==0?true:false;
}
publicvoid Clear()
{
Front =0;//隊頭
Rear =0;//隊尾
}
publicbool isFull()
{
return(Rear +1)% MaxSize == Front ?true:false;
}
publicvoid In(T item,out States states)
{
if(isFull())
{
states = States.Fail;
return;
}
this.Data[Rear]= item;
Rear =(Rear +1)% MaxSize;
states = States.Success;
}
public T Out(out States states)
{
if(IsEmpty())
{
states = States.Fail;
returndefault(T);
}
T dataToOut =this.Data[Front];
Front =(Front +1)% MaxSize;
states = States.Success;
return dataToOut;
}
public T GetFront(out States states)
{
thrownew NotImplementedException();
}
}
}
2、鏈隊
由單鏈表的實現，我們可知單鏈表有一個Head字段，通過Head字段我們可以遍歷單鏈表。在鏈隊中，我們打算直接利用Head字段，只不過我們將其命名Front。通常當我們需要遍歷一個單鏈表時，我們得從鏈表頭遍歷都最后，才能找到鏈表尾。這樣操作的話，時間復雜度為O(n),我們打算引用Rear字段，用來指示每次新入隊的元素。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure.Queue
{
class LinkQueue<T>:IQueue<T>
{
class Node<T>
{
private T data;
/// <summary>
/// 數據域
/// </summary>
public T Data
{
get {return data;}
set { data = value;}
}
private Node<T> next;
/// <summary>
/// 引用域
/// </summary>
public Node<T> Next
{
get {return next;}
set { next = value;}
}
//頭結點構造函數
public Node(Node<T> node)
:this(default(T), node)
{
}
//普通結點構造函數
public Node(T data, Node<T> node)
{
this.Data = data;
this.Next = node;
}
/// <summary>
/// 空構造函數
/// </summary>
public Node()
:this(default(T),null)
{
}
//尾結點構造函數
public Node(T data)
:this(data,null)
{
}
}
private Node<T> Front;//隊頭
private Node<T> Rear;//隊尾
publicbool IsEmpty()
{
return Front ==null?true:false;
}
publicvoid Clear()
{
Front =null;
}
publicvoid In(T item,out States states)
{
if(IsEmpty())
{
Front =new Node<T>(item);
states = States.Success;
Rear = Front;
}
else
{
Node<T> newNode=new Node<T>(item);
Rear.Next = newNode;
Rear = newNode;
states = States.Success;
}
}
public T Out(out States states)
{
if(this.IsEmpty())
{
states = States.Fail;
returndefault(T);
}
else
{
states = States.Success;
T DataToOut =this.Front.Data;
Front = Front.Next;
return DataToOut;
}
}
public T GetFront(out States states)
{
if(this.IsEmpty())
{
states = States.Fail;
returndefault(T);
}
else
{
states = States.Success;
returnthis.Front.Data;
}
}
publicint GetLength()
{
if(IsEmpty())
{
return0;
}
int Lenth=0;//長度
for(Node<T> last = Front; last.Next !=null; last=last.Next)
{
Lenth++;
}
return Lenth;
}
}
}
文章列表
留言列表
