本文實例講述了C#數據結構之隊列(Quene)。分享給大家供大家參考，具體如下：
隊列(Quene)的特征就是“先進先出”，隊列把所有操作限制在"只能在線性結構的兩端"進行，更具體一點：添加元素必須在線性表尾部進行，而刪除元素只能在線性表頭部進行。
先抽象接口IQuene<T>
namespace 棧與隊列{ public interface IQuene<T> { /// <summary> /// 取得隊列實際元素的個數 /// </summary> /// <returns></returns> public int Count(); /// <summary> /// 判斷隊列是否為空 /// </summary> /// <returns></returns> public bool IsEmpty(); /// <summary> /// 清空隊列 /// </summary> public void Clear(); /// <summary> /// 入隊（即向隊列尾部添加一個元素） /// </summary> /// <param name="item"></param> public void Enquene(T item); /// <summary> /// 出隊(即從隊列頭部刪除一個元素) /// </summary> /// <returns></returns> public T Dequene(); /// <summary> /// 取得隊列頭部第一元素 /// </summary> /// <returns></returns> public T Peek(); }}下面是基于數組實現的示意圖：
實現思路：用一個數組存放所有元素，同時設置二個關鍵變量front與rear用于記錄隊列“頭”與“尾”的元素下標，當有元素入列時rear加1，當有元素出隊時front+1，而rear-front即為隊列實際元素的總數.
但有一種“隊列偽滿”的特殊情況要注意，如下圖：
這張圖上面的部分：假設經過入隊、出隊一番折騰后，rear已經指向數組的下標最大值，而front指向在中間(即front之間的元素已經出隊不用考慮了，相當于front下標前面的內存區域空閑)，如果這時再有一個元素入列，rear+1就超出數組下標的最大值了，但是從圖上一眼就能看出，實際上front前面還空著一堆位置可以重復利用，隊列并非真正的“滿”--這種情況稱為偽滿，為了解決這個問題，我們可以把數組想象為首尾相接的循環結構，即圖中下面部分，這時候可以讓rear重新指向到0，以便重復利用空閑的位置。
所以：入列時rear++的操作，應該稍做修正，當rear到數組下標最大值時，讓它置0，以便能循環利用 (見后面的代碼)
另外還有一個問題：最開始時front與rear都為-1，即front==rear時表示隊列為空，改成循環以后，有可能會出現rear在循環過程中碰到front的情況，即真正意義的上"滿"狀態，這時rear也同樣等于front，這樣就無法單純的用rear==front來判斷是滿，還是空？這時可以浪費一個元素的位置，認為當rear+1==front時，隊列就已經滿了，雖然犧牲了一個元素的空間，但卻換來了邏輯的正確性，還是值得的。
完整實現如下：
using System;using System.Text;namespace 棧與隊列{ /// <summary> /// 循環順序隊列 /// </summary> /// <typeparam name="T"></typeparam> public class CSeqQueue<T>:IQueue<T> { private int maxsize; private T[] data; private int front; private int rear; public CSeqQueue(int size) { data = new T[size]; maxsize = size; front = rear = -1; } public int Count() { if (rear > front) { return rear - front; } else { return (rear - front + maxsize) % maxsize; } } public void Clear() { front = rear = -1; } public bool IsEmpty() { return front == rear; } public bool IsFull() { if (front != -1) //如果已經有元素出隊過 { return (rear + 1) % maxsize == front;//為了區分與IsEmpty的區別，有元素出隊過以后，就只有浪費一個位置來保持邏輯正確性. } else { return rear == maxsize - 1; } } public void Enqueue(T item) { if (IsFull()) { Console.WriteLine("Queue is full"); return; } if (rear == maxsize - 1) //如果rear到頭了，則循環重來（即解決偽滿問題） { rear = 0; } else { rear++; } data[rear] = item; } public T Dequeue() { if (IsEmpty()) { Console.WriteLine("Queue is empty"); return default(T); } if (front == maxsize - 1) //如果front到頭了，則重新置0 { front = 0; } else { front++; } return data[front]; } public T Peek() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } return data[(front + 1) % maxsize]; } public override string ToString() { if (IsEmpty()) { return "queue is empty."; } StringBuilder sb = new StringBuilder(); if (rear > front) { for (int i = front + 1; i <= rear; i++) { sb.Append(this.data[i].ToString() + ","); } } else { for (int i = front + 1; i < maxsize; i++) { sb.Append(this.data[i].ToString() + ","); } for (int i = 0; i <= rear; i++) { sb.Append(this.data[i].ToString() + ","); } } return "front = " + this.front + " /t rear = " + this.rear + "/t count = " + this.Count() + "/t data = " + sb.ToString().Trim(','); } }}測試代碼片段：
CSeqQueue<int> queue = new CSeqQueue<int>(5);queue.Enqueue(1);queue.Enqueue(2);queue.Enqueue(3);queue.Enqueue(4);Console.WriteLine(queue);//front = -1 rear = 3 count = 4 data = 1,2,3,4queue.Dequeue();Console.WriteLine(queue);//front = 0 rear = 3 count = 3 data = 2,3,4queue.Dequeue();Console.WriteLine(queue);//front = 1 rear = 3 count = 2 data = 3,4queue.Enqueue(5);Console.WriteLine(queue);//front = 1 rear = 4 count = 3 data = 3,4,5queue.Enqueue(6);Console.WriteLine(queue);//front = 1 rear = 0 count = 4 data = 3,4,5,6queue.Enqueue(7); //Queue is fullConsole.WriteLine(queue);//front = 1 rear = 0 count = 4 data = 3,4,5,6queue.Dequeue();queue.Enqueue(7);Console.WriteLine(queue);//front = 2 rear = 1 count = 4 data = 4,5,6,7queue.Clear();Console.WriteLine(queue);//queue is empty.queue.Enqueue(1);queue.Enqueue(2);queue.Enqueue(3);queue.Enqueue(4);Console.WriteLine(queue);//front = -1 rear = 3 count = 4 data = 1,2,3,4queue.Enqueue(5);Console.WriteLine(queue);//front = -1 rear = 4 count = 5 data = 1,2,3,4,5queue.Enqueue(6); //Queue is fullConsole.WriteLine(queue);//front = -1 rear = 4 count = 5 data = 1,2,3,4,5queue.Dequeue();queue.Dequeue();queue.Dequeue();queue.Dequeue();Console.WriteLine(queue);//front = 3 rear = 4 count = 1 data = 5queue.Dequeue();Console.WriteLine(queue);//queue is empty.queue.Enqueue(0);queue.Enqueue(1);queue.Enqueue(2);queue.Enqueue(3);queue.Enqueue(4); //Queue is fullConsole.WriteLine(queue);//front = 4 rear = 3 count = 4 data = 0,1,2,3Console.WriteLine(queue.Peek());//0queue.Dequeue();Console.WriteLine(queue);//front = 0 rear = 3 count = 3 data = 1,2,3queue.Dequeue();Console.WriteLine(queue);//front = 1 rear = 3 count = 2 data = 2,3queue.Dequeue();Console.WriteLine(queue);//front = 2 rear = 3 count = 1 data = 3queue.Dequeue();Console.WriteLine(queue);//queue is empty.queue.Enqueue(9);Console.WriteLine(queue);//front = 3 rear = 4 count = 1 data = 9Console.ReadLine();
當然，隊列也可以用鏈表來實現，相對要容易很多。
先定義鏈表中的節點Node.cs
namespace 棧與隊列{ public class Node<T> { private T data; private Node<T> next; public Node(T data, Node<T> next) { this.data = data; this.next = next; } public Node(Node<T> next) { this.next = next; this.data = default(T); } public Node(T data) { this.data = data; this.next = null; } public Node() { this.data = default(T); this.next = null; } public T Data { get { return this.data; } set { this.data = value; } } public Node<T> Next { get { return next; } set { next = value; } } }}為了方便，定義了很多構造函數的重載版本，當然這些只是浮云，重點是理解結構：data用來保存數據，next指出下一個節點是誰
鏈式隊列的完整實現LinkQueue.cs
using System;using System.Text;namespace 棧與隊列{ public class LinkQueue:IQueue { private Node front;//隊列頭 private Node rear;//隊列尾 private int num;//隊列元素個數 /// /// 構造器 /// public LinkQueue() { //初始時front,rear置為null，num置0 front = rear = null; num = 0; } public int Count() { return this.num; } public void Clear() { front = rear = null; num = 0; } public bool IsEmpty() { return (front == rear && num == 0); } //入隊 public void Enqueue(T item) { Node q = new Node(item); if (rear == null)//第一個元素入列時 { front = rear = q; } else { //把新元素掛到鏈尾 rear.Next = q; //修正rear指向為最后一個元素 rear = q; } //元素總數+1 num++; } //出隊 public T Dequeue() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } //取鏈首元素 Node p = front; //鏈頭指向后移一位 front = front.Next; //如果此時鏈表為空，則同步修正rear if (front == null) { rear = null; } num--;//個數-1 return p.Data; } public T Peek() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); return default(T); } return front.Data; } public override string ToString() { if (IsEmpty()) { Console.WriteLine("Queue is empty!"); } StringBuilder sb = new StringBuilder(); Node node = front; sb.Append(node.Data.ToString()); while (node.Next!=null) { sb.Append("," + node.Next.Data.ToString()); node = node.Next; } return sb.ToString().Trim(','); } }}希望本文所述對大家C#程序設計有所幫助。
新聞熱點
疑難解答
