C#資料結構－隊列

理論基礎：

           隊列(Queue)是插入操作限定在表的尾部而其它操作限定在表的頭部進行的線性表。把進行插入操作的表尾稱為隊尾(Rear)，把進行其它操作的頭部稱為隊頭(Front)。

           對列的操作是按照先進先出(First In First Out)或後進後出( Last In Last Out)的原則進行的，是以，隊列又稱為FIFO表或LILO表。

          與棧一樣，隊列的運算是定義在邏輯結構層次上的，而運算的具體實作是建立在實體存儲結構層次上的。是以，把隊列的操作作為邏輯結構的一部分，每個操作的具體實作隻有在确定了隊列的存儲結構之後才能完成。

          隊列可以區分為順序隊列，鍊隊列兩種。

          順序隊列類似于順序棧，用一維數組來存放順序隊列中的資料元素。鍊隊列同鍊棧一樣，鍊隊列通常用單連結清單來表示，它的實作是單連結清單的簡化。

          順序隊列在操作的過程中會出現“假溢出”。可以用循環順序隊列解決這種現象，是以，下面的代碼将會實作循環順序隊列的主要操作。

C#實作：

        1 接口定義

        C#語言的泛型接口來表示隊列，接口中的方法成員表示基本操作。為了表示的友善與簡潔，把泛型隊列接口取名為IQueue<T>（實際上，在C#中泛型隊列類是從IEnumerable<T>、ICollection和IEnumerable接口繼承而來，沒有IQueue<T>泛型接口）。

         隊列接口IQueue<T>的定義如下所示：

Code
 public interface IQueue<T>
    {
/// <summary>
/// 隊列長度
/// </summary>
/// <returns></returns>
        int GetLength();
/// <summary>
/// 判斷是否為空
/// </summary>
/// <returns></returns>
        bool IsEmpty();
/// <summary>
/// 是否已滿
/// </summary>
/// <returns></returns>
        bool Full();
/// <summary>
/// 清空隊列
/// </summary>
        void Clear();
/// <summary>
/// 入隊
/// </summary>
/// <param name="item"></param>
        void In(T item);
/// <summary>
/// 出隊
/// </summary>
/// <returns></returns>
        T Out();

    }      

        2 代碼實作

        實作提供的接口   

Code
 public class CSeqQueue<T> : IQueue<T>
    {
private int maxsize; //隊列最大容量
        private T[] data;//隊列資料
        private int front;//隊頭
        private int rear;//隊尾

public T this[int index]
        {
get {return data[index];  }
set{ data[index] = value; }
        }
public int MaxSize
        {
get { return maxsize; }
set {   maxsize = value; }
        }
public int Front
        { 
get {  return front; }
set {   front = value;  }

        }
public int Rear
        {
get  {  return rear; }
set {  rear = value; }
        }

public CSeqQueue(int size)
        {
            data =new T[size];
            maxsize = size;
            front = rear = -1;
        }

//隊列長度
        public int GetLength()
        {
return (rear - front + maxsize) % maxsize;
        }
//清空隊列
        public void Clear()
        {
            front = rear = -1;
        }
//判斷是否為空
        public bool IsEmpty()
        {
if (front == rear)
            {
return true;
            }
else
            {
return false;
            }
        }
//判斷是否已滿
        public bool IsFull()
        {
if (front == (rear+1)%maxsize)
            {
return true;
            }
else
            {
return false;
            }
        }
//入隊
        public void In(T item)
        {
if (IsFull())
            {
                Console.Write("Queue is full");
return;
            }

            data[++rear] = item;
        }
//出隊
        public T Out()
        {
if (IsEmpty())
            {
                Console.Write("Queue is empty");
return;
             }
return data[++front];
        }
    }      

C#中的隊列：

          C#2.0以下版本隻提供了非泛型的Queue類，該類繼承了ICollection、IEnumerable和ICloneable接口。

           C#2.0提供了泛型的Queue<T>類，該類繼承了IEnumerable<T>、ICollection和IEnumerable接口。

           以下程式說明了泛型Queue<T>類的主要方法，并對在我們自定義的隊列類中沒有出現的成員方法進行了注釋，

           關于泛型Queue<T>類的更具體的資訊，可參考.NET Framework的有關書籍。

Code
  public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable
    {
public void Clear();
//确定某元素是否在Queue<T>中。
//如果在Queue<T> 中找到 item，則為true；否則為false。
        public bool Contains(T item);//從指定數組索引開始将Queue<T>元素複制到現有一維Array 中。
        public void CopyTo(T[] array, int arrayIndex);
//移除并傳回位于Queue<T>開始處的對象。
//從Queue<T>的開頭移除的對象。
        public T Dequeue();
//傳回位于Queue<T>開始處的對象但不将其移除。
        public T Peek();
//将Queue<T>元素複制到新數組。
        public T[] ToArray();
//如果元素數小于目前容量的90%，
//将容量設定為Queue<T> 中的實際元素數。
        public void TrimExcess();
    }      

轉載于:https://www.cnblogs.com/Richet/archive/2008/10/20/1315192.html