資料結構C#版筆記--隊列(Quene)

隊列(Quene)的特征就是“先進先出”，隊列把所有操作限制在"隻能線上性結構的兩端"進行，更具體一點：添加元素必須線上性表尾部進行，而删除元素隻能線上性表頭部進行。

先抽象接口IQuene<T>

下面是基于數組實作的示意圖：

實作思路：用一個數組存放所有元素，同時設定二個關鍵變量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時，隊列就已經滿了，雖然犧牲了一個元素的空間，但卻換來了邏輯的正确性，還是值得的。

完整實作如下：

測試代碼片段：

當然，隊列也可以用連結清單來實作，相對要容易很多。

先定義連結清單中的節點Node.cs

為了友善，定義了很多構造函數的重載版本，當然這些隻是浮雲，重點是了解結構：data用來儲存資料，next指出下一個節點是誰

鍊式隊列的完整實作LinkQueue.cs