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