C#環形隊列的實現方法詳解

2020-01-24 00:59:00

字體：大中小

來源：轉載

供稿：網友

一、環形隊列是什么

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

二、環形隊列的優點

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

是由隊列的性質保證的，在環形隊列中通過對隊列的順序訪問保證。

　2.元素空間可以重復利用

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

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

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

三、C#環形隊列的實現

看了一個數據結構的教程，是用C++寫的，可自己C#還是一個菜鳥，更別說C++了，但還是大膽嘗試用C#將其中的環形隊列的實現寫出來，先上代碼：

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;  } }

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

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();  } }

顯示結果：

再測試下出隊：

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();  } }

運行結果：

2、復雜類型隊列

之前也說了，這個隊列類是用的泛型寫的，對應于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();是通過索引來實現，所以我們得在隊列類中實現索引，添加如下代碼到MyQueue.cs類中，如下：

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

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

然后實現這個接口，如下：

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

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