實驗一

題目要求

用C#構造一個隊列Queue。要求此隊列是循環(huán)隊列，并進行入隊、出隊的測試

題意分析

將循環(huán)隊列封裝為一個類，在類內部實現入隊、出隊、展示等操作

選擇數組作為存儲隊列的數據結構

在Main()方法內編寫測試用函數

數據結構

隊列

是一種先進先出（FIFO）的線性表，只允許在隊尾（rear）進行入隊操作（enqueue, push），在隊頭（front）進行出隊操作（dequeue, pop）。其中，初始化時rear == front，有元素之后rear指向尾元素的下一個位置。此時，當rear與隊列容量上限（MAX_SIZE）相同時，表示隊列達到上限。

在實際表示隊列中，往往采用數組或者是鏈表進行存儲。在使用數組，或是規(guī)定了隊列容量上限的時候，往往會出現以下問題：隊尾不斷向后（下標變大，下同）增加（enqueue），隊頭也會不斷向后增加（dequeue），然后：

同學們就會發(fā)現“呀這不浪費嗎，明明還有位置卻報告隊列裝不下了”。

有一個解決上述問題的方法：每次出隊之后，不斷將所有的元素向前挪。很容易得知這個方法的時間復雜度為O(n)，比較浪費時間。

于是有人就說：“我們可不可以在邏輯上把表頭表尾相接起來，變成一個循環(huán)的表，rear到頂了之后再從下標0開始存起。這樣，空間是不斷循環(huán)重復利用的，就不用擔心有剩余空間了?！?/span>

循環(huán)隊列

循環(huán)隊列應運而生！

這樣的數據結構很好地解決了空間時間浪費的問題，但是同時也帶來了新的問題：怎么樣判斷隊列是空還是滿？

在原有的樸素隊列中，判斷隊空只需要if (front == rear)，而判斷隊滿只需要if (rear - front == MAX_SIZE)，而在循環(huán)隊列中，隊頭和隊尾在隊空和隊滿的時候都會碰面，給大家造成困擾。有人提出了這樣的解決方法：新增一個位置表示隊列的元素個數。但是更加快捷，省空間的解決方法是：犧牲一個空間并用rear指向它。這樣子，隊空的判斷條件依然是if (front == rear)，而隊滿的條件變?yōu)?/span>if (rare + 1 == front)。

??

而隊滿的條件變?yōu)?/span>if (rare + 1 == front)

（有沒有感覺這話有點問題？）

我們說循環(huán)隊列只是邏輯上的循環(huán)隊列，物理上存儲依然是數組（一段連續(xù)的內存地址），所以完全有可能出現這樣的情況：front == 0而rear == MAX_SIZE，這時候就出問題了，rear+1依然是一個大的數，而非0。因此，我們需要將判斷語句稍加改動：

(rare +?1)?%?q.Length?==?front

這樣子，當rear達到或超過了數組的最大值時，就會通過取?；氐介_頭，從而達到了循環(huán)的效果。

完整代碼

using?System;
using?System.Collections.Generic;
using?System.Linq;
using?System.Text;
using?System.Threading.Tasks;

namespace?C_Sharp_test
{

????public?class?Queue
????{
????????// 宏定義
????????private?const?int?OVERFLOW =?-1;
????????private?const?int?QNULL =?-2;

????????// 私有成員定義
????????private?double[]?q;
????????private?uint?front =?0;
????????private?uint?rear =?0;

????????// 方法
????????public?Queue()?{?q =?new?double[100];?}????// 默認隊列大小為100
????????public?Queue(uint?size)
????????{
????????????while?(size ==?0)
????????????{
????????????????Console.WriteLine("隊列容量不可為0！");
????????????????Console.WriteLine("請輸入正確的隊列容量: ");
????????????????size =?Convert.ToUInt32(Console.ReadLine().Trim());
????????????}
????????????q =?new?double[size +?1];
????????}
????????public?int?enqueue(double?ele)
????????{
????????????if?((rear +?1)?%?q.Length?==?front)
????????????????return?OVERFLOW;
????????????q[rear]?=?ele;
????????????rear =?(uint)((rear +?1)?%?q.Length);
????????????return?1;
????????}
????????public?int?dequeue(ref?double?ele)
????????{
????????????if?(is_empty())
????????????????return?QNULL;
????????????ele =?q[front];
????????????front =?(uint)((front +?1)?%?q.Length);
????????????return?1;
????????}
????????public?void?show_queue()
????????{
????????????Console.WriteLine("Queue: ");
????????????if?(is_empty())
????????????{
????????????????Console.WriteLine("隊列已空！");
????????????????return;
????????????}
????????????uint?sub_rear =?(uint)((rear +?q.Length?-?1)?%?q.Length);
????????????while?(sub_rear !=?front)
????????????{
????????????????Console.Write("{0} ",?q[sub_rear]);
????????????????sub_rear =?(uint)((sub_rear +?q.Length?-?1)?%?q.Length);
????????????}
????????????Console.Write(q[sub_rear]);
????????????Console.WriteLine();
????????????return;
????????}
????????public?uint?get_len()
????????{
????????????return?(uint)((q.Length?+?rear -?front)?%?q.Length);
????????}
????????public?bool?is_empty()
????????{
????????????return?rear ==?front;
????????}
????}
????class?Program
????{
????????static?void?Main(string[]?args)
????????{
????????????Console.WriteLine("請輸入隊列容量: ");
????????????uint?size =?Convert.ToUInt32(Console.ReadLine().Trim());
????????????Queue q =?new?Queue(size);

????????????// 入隊測試
????????????Console.WriteLine("請輸入入隊數據: ");
????????????string[]?lst =?Console.ReadLine().Trim().Split(' ');
????????????if?(lst.Length?>?size)
????????????{
????????????????Console.WriteLine("超出隊列容量！");
????????????????goto?end;
????????????}
????????????for?(int?i =?0;?i <?lst.Length;?i++)
????????????????q.enqueue(Convert.ToDouble(lst[i]));
????????????q.show_queue();


????????????// 出隊測試
????????????double?element =?0;
????????????uint?len =?q.get_len();
????????????Console.WriteLine("出隊的數據: ");
????????????while?(len !=?0)
????????????{
????????????????q.dequeue(ref?element);
????????????????Console.Write("{0} ",?element);
????????????????len--;
????????????}
????????????Console.WriteLine();
????????????q.show_queue();

????????????// 循環(huán)性測試
????????????Console.WriteLine("隊列循環(huán)性測試: ");
????????????for?(int?i =?0;?i <?lst.Length;?i++)
????????????????q.enqueue(Convert.ToDouble(lst[i]));????// 隊列中先塞入一些元素
????????????q.show_queue();

????????????for?(int?i =?0;?i <?size *?2;?i +=?2)
????????????{
????????????????q.enqueue(i +?1);
????????????????q.enqueue(i +?2);
????????????????q.dequeue(ref?element);
????????????????q.dequeue(ref?element);
????????????????q.show_queue();
????????????}

????????// 結束
????????end:
????????????Console.WriteLine("請按任意鍵繼續(xù)...");
????????????Console.ReadLine();
????????}
????}
}

代碼片段分析

類Queue中

// 宏定義
private?const?int?OVERFLOW =?-1;
private?const?int?QNULL =?-2;

防止異常的出現，事先定義好錯誤的返回值(溢出為-1，隊空為-2)

C#是純面向對象編程的語言，所有的“宏定義”都要寫在類中。

size =?Convert.ToUInt32(Console.ReadLine().Trim());

Console類的ReadLine()方法返回一個字符串，而不是像C/C++中將讀入的數據直接賦給變量
String類中的Trim()方法表示將頭尾的空白字符刪去，它的兄弟有TrimStart()，TrimEnd()，分別表示刪去開頭的空白字符和刪去末尾的空白字符
Convert類中的ToUInt32()方法表示將一個字符串轉化為32位無符號整型（即uint）
這樣子，就通過一步代碼將讀入的字符串轉化為無符號整數。
學過Python的同學就會對以上的操作感覺到非常熟悉，行云流水。它等效于以下的python代碼：

size =?int(input().strip()) //?Python

我們接著往下看

q =?new?double[size +?1];

由于犧牲了一個空間，所以在開辟空間時多開辟一個元素的容量。

public?int?enqueue(double?ele)
{
????if?((rear +?1)?%?q.Length?==?front)
????????return?OVERFLOW;
????q[rear]?=?ele;
????rear =?(uint)((rear +?1)?%?q.Length);
????return?1;
}
public?int?dequeue(ref?double?ele)
{
if?(is_empty())
return?QNULL;
ele =?q[front];
front =?(uint)((front +?1)?%?q.Length);
return?1;
}

將上面說的數據結構翻譯成C#語言來表示，結果就是這樣了。

在C++中，會出現比如dequeue(double &ele)中double &這樣的類型，被稱為引用。在變量名前（或是類型之后，如果變量只有一個的話）加上&表示成引用類型，作用是給變量起一個別名，它和原變量指向同一塊內存地址。也就是說，更改了它的值就相當于更改了原有那個變量的值（因為是在對應的內存位置上直接改動）。

在C#中，也有稱為ref的關鍵字，作用和C++中的引用是一樣的，即將參數按引用傳值。只不過在C#中，調用參數含ref引用的方法時，必須將ref加上（如下所示），而在C++中沒有相應的要求。

q.dequeue(ref?element);

使用引用的原因是，需要將隊中要彈出的元素彈出給某個變量，否則它會丟失（當然，你也可以再寫一個get_front這樣的函數）。而使用return的話，則會將值和返回的錯誤信息混淆。

我們接著往下看

在方法show_queue()中：

uint?sub_rear =?(uint)((rear +?q.Length?-?1)?%?q.Length);

在實際測試中發(fā)現當q.Length和它右邊的-1位置對調之后程序會出bug，原因應該是rear為uint型，-1有可能會造成溢出問題，因而需要對調。

public?uint?get_len()
{
????return?(uint)((q.Length?+?rear -?front)?%?q.Length);
}

此方法的功能是返回隊列長度。筆者第一次在書寫這個程序的時候寫出來的是 return q.Length，千萬別犯這樣的錯誤。這里要返回的并不是隊列數組的容量，而是循環(huán)隊列的“長度”。

Main()方法中

// 入隊測試
Console.WriteLine("請輸入入隊數據: ");
string[]?lst =?Console.ReadLine().Trim().Split(' ');

Split()方法將字符串按照指定參數“分裂”，返回一個字符串數組，這個字符串數組的元素為為分裂過后的字符串
學過Python的同學依然會對以上的操作感覺到非常熟悉，行云流水。它等效于以下的python代碼：

lst =?input().strip().split() ?//?Python

我們接著往下看

// 循環(huán)性測試

這個測試就是測試隊列的循環(huán)功能是否正常，而非樸素的線性表就能達到的功能

// 結束
end:
Console.WriteLine("請按任意鍵繼續(xù)...");
Console.ReadLine();

在VS中按下F5或者是點擊上面的“啟動”時，VS會運行代碼，但是在運行之后他會直接退出程序，而不是像之前的C/C++一樣等待用戶按鍵。所以我們需要手動制造一個結束暫停，就像上面的代碼一樣。另外一種可行的方法是按下Ctrl+F5，這樣便會在程序運行之后等待用戶按鍵。

經過一系列辛苦的理解和編碼，我們的循環(huán)隊列終于做完了！

總結

通過實驗一的第一題，我們學習到了隊列這一種數據結構以及他的一種表示方法——循環(huán)隊列。當然，我們的隊列是通過數組存儲的，接下來還能繼續(xù)學習使用鏈表來表示的隊列。我們還學習到了C#的讀入和處理，Convert轉換臺，ref引用等知識點。

參考文獻

嚴蔚敏，吳偉民.數據結構（C語言版）：清華大學出版社，2012

李春葆，曾平，喻丹丹.C#程序設計教程（第3版）：清華大學出版社，2015

Copyright @ 2021, Bilibili: ForeverMeteor, all rights reserved.?

?