快捷導(dǎo)航

C#環(huán)形隊列的實現(xiàn)方法詳解

更新時間：2016年09月27日 14:31:00 作者：獨孤飛

這篇文章先是簡單的給大家介紹了什么是環(huán)形隊列和環(huán)形隊列的優(yōu)點，然后通過實例代碼給大家介紹C#如何實現(xiàn)環(huán)形隊列，有需要的朋友們可以參考借鑒，下面來一起看看吧。

一、環(huán)形隊列是什么

隊列是一種常用的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)保證了數(shù)據(jù)是按照“先進先出”的原則進行操作的，即最先進去的元素也是最先出來的元素.環(huán)形隊列是一種特殊的隊列結(jié)構(gòu)，保證了元素也是先進先出的，但與一般隊列的區(qū)別是，他們是環(huán)形的，即隊列頭部的上個元素是隊列尾部，通常是容納元素數(shù)固定的一個閉環(huán)。

二、環(huán)形隊列的優(yōu)點

　1.保證元素是先進先出的

是由隊列的性質(zhì)保證的，在環(huán)形隊列中通過對隊列的順序訪問保證。

　2.元素空間可以重復(fù)利用

因為一般的環(huán)形隊列都是一個元素數(shù)固定的一個閉環(huán)，可以在環(huán)形隊列初始化的時候分配好確定的內(nèi)存空間，當(dāng)進隊或出隊時只需要返回指定元素內(nèi)存空間的地址即可，這些內(nèi)存空間可以重復(fù)利用，避免頻繁內(nèi)存分配和釋放的開銷。

　3.為多線程數(shù)據(jù)通信提供了一種高效的機制。

在最典型的生產(chǎn)者消費者模型中，如果引入環(huán)形隊列，那么生成者只需要生成“東西”然后放到環(huán)形隊列中即可，而消費者只需要從環(huán)形隊列里取“東西”并且消費即可，沒有任何鎖或者等待，巧妙的高效實現(xiàn)了多線程數(shù)據(jù)通信。

三、C#環(huán)形隊列的實現(xiàn)

看了一個數(shù)據(jù)結(jié)構(gòu)的教程，是用C++寫的，可自己C#還是一個菜鳥，更別說C++了，但還是大膽嘗試用C#將其中的環(huán)形隊列的實現(xiàn)寫出來，先上代碼：

public class MyQueue<T> : IDisposable
 {
  private T[] queue;
  private int length;
  private int capacity;
  private int head = 0;
  private int tail = 0;

  public MyQueue(int capacity) {
   this.capacity = capacity;
   this.head = 0;
   this.tail = 0;
   this.length = 0;
   this.queue = new T[capacity];
  }

  public void Clear() {
   head = 0;
   tail = 0;
   length = 0;
  }

  public bool IsEmpty() {
   return length == 0;
  }

  public bool IsFull() {
   return length == capacity;
  }

  public int Length() {
   return length;
  }

  public bool EnQueue(T node) {
   if (!IsFull()) {
    queue[tail] = node;
    tail = (++tail) % capacity;
    length++;
    return true;
   }
   return false;
  }

  public T DeQueue() {
   T node = default(T);
   if (!IsEmpty()) {
    node = queue[head];
    head = (++head) % capacity;
    length--;
   }
   return node;
  }

  public void Traverse() {
   for (int i = head; i < length + head; i++) {
    Console.WriteLine(queue[i % capacity]);
    Console.WriteLine($"前面還有{i - head}個");
   }
  }

  public void Dispose() {
   queue = null;
  }
 }

為了能夠通用，所以用的是泛型來實現(xiàn)環(huán)形隊列類。這里最重要的是進隊(EnQueue)和出隊(DeQueue)兩個方法，進隊或出隊后頭和尾的位置都要通過取模運算來獲得，因為是環(huán)形隊列嘛，你懂的。

1、簡單類型隊列

好了，測試下入隊：

class Program
 {
  static void Main(string[] args) {
   MyQueue<int> queue = new MyQueue<int>(4);
   queue.EnQueue(10);
   queue.EnQueue(16);
   queue.EnQueue(18);
   queue.EnQueue(12);
   queue.Traverse();
   Console.Read();
  }
 }

顯示結(jié)果：

再測試下出隊：

class Program
 {
  static void Main(string[] args) {
   MyQueue<int> queue = new MyQueue<int>(4);
   queue.EnQueue(10);
   queue.EnQueue(16);
   queue.EnQueue(18);
   queue.EnQueue(12);
   queue.Traverse();

   Console.WriteLine("彈兩個出去");
   queue.DeQueue();
   queue.DeQueue();
   Console.WriteLine();
   queue.Traverse();
   Console.Read();
  }
 }

運行結(jié)果：

2、復(fù)雜類型隊列

之前也說了，這個隊列類是用的泛型寫的，對應(yīng)于C++的模板了，那就意味著任何類型都可以使用這個隊列類，來測試個自定義的類試試，如下先定義一個Customer類：

public class Customer
 {
  public string Name { get; set; }

  public int Age { get; set; }

  public void PringInfo() {
   Console.WriteLine("姓名:" + Name);
   Console.WriteLine("年齡:" + Age);
   Console.WriteLine();
  }
 }

然后進行入隊，如下：

class Program
 {
  static void Main(string[] args) {
   MyQueue<Customer> queue = new MyQueue<Customer>(5);
   queue.EnQueue(new Customer() { Name = "宋小二", Age = 29 });
   queue.EnQueue(new Customer() { Name = "陳小三", Age = 28 });
   queue.EnQueue(new Customer() { Name = "王小四", Age = 26 });
   queue.EnQueue(new Customer() { Name = "朱小五", Age = 48 });
   for (int i = 0; i < queue.Length(); i++) {
    queue[i].PringInfo();
   }
   Console.Read();
  }
 }

上面的代碼 queue[i].PringInfo();是通過索引來實現(xiàn)，所以我們得在隊列類中實現(xiàn)索引，添加如下代碼到MyQueue.cs類中，如下：

   public T this[int index] {
    get {
     return queue[index];
    }
   }

感覺用for循環(huán)來遍歷還是不夠好，想用foreach，那就給MyQueue類加個遍歷接口，如下：

然后實現(xiàn)這個接口，如下：

public IEnumerator<T> GetEnumerator() {
   foreach(T node in queue) {
    if(node != null) { 
     yield return node;
    }
   }
  }

  IEnumerator IEnumerable.GetEnumerator() {
   return GetEnumerator();
  }

這樣遍歷的地方就可以改成foreach了，如下：