快捷導(dǎo)航

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

更新時(shí)間：2016年09月27日 14:31:00 作者：獨(dú)孤飛

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

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

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

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

　1.保證元素是先進(jìn)先出的

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

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

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

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

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

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

看了一個(gè)數(shù)據(jù)結(jié)構(gòu)的教程，是用C++寫的，可自己C#還是一個(gè)菜鳥，更別說C++了，但還是大膽嘗試用C#將其中的環(huán)形隊(duì)列的實(shí)現(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}個(gè)");
   }
  }

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

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

1、簡單類型隊(duì)列

好了，測試下入隊(duì)：

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é)果：

再測試下出隊(duì)：

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("彈兩個(gè)出去");
   queue.DeQueue();
   queue.DeQueue();
   Console.WriteLine();
   queue.Traverse();
   Console.Read();
  }
 }

運(yùn)行結(jié)果：

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

之前也說了，這個(gè)隊(duì)列類是用的泛型寫的，對(duì)應(yīng)于C++的模板了，那就意味著任何類型都可以使用這個(gè)隊(duì)列類，來測試個(gè)自定義的類試試，如下先定義一個(gè)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();
  }
 }

然后進(jìn)行入隊(duì)，如下：

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();是通過索引來實(shí)現(xiàn)，所以我們得在隊(duì)列類中實(shí)現(xiàn)索引，添加如下代碼到MyQueue.cs類中，如下：

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

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

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

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

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

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