C語言入門第23課：大家排排隊—

C語言入門第23課：大家排排隊——佇列

來源：讀職場釋出時間：2023-06-01 10:47

在上節課程當中，我們學習瞭如何使用結構體和動態記憶體治理來實現一個簡樸的連結串列資料結構。我們知道，連結串列是一種由多個節點組成的線性表，每個節點都包含兩部門：資料域和指標域。資料域儲存節點本身攜帶的資訊，指標域儲存下一個節點在記憶體中的地址。透過這種方式，連結串列可以動態地增加或刪除節點，並且不需要連續分配記憶體空間。但是，連結串列並不是獨一一種可以用結構體和動態記憶體治理來實現的資料結構。今天，我們將先容另一種常用的資料結構——佇列。

佇列是一種特殊的線性表，它只答應在一端（稱為隊尾）插入元素，在另一端（稱為隊頭）刪除元素。這種操縱方式也被稱為先進先出（FIFO），即最先進入佇列的元素最先被刪除。佇列是一種非常常見的資料結構，它可以用來模擬各種現實生活中的場景，好比排隊、緩衝、訊息傳遞等等。那麼，我們該如何用C語言來實現一個佇列呢？我們來看一些示例程式碼：

這個示例程式碼展示瞭如何對佇列進行入隊和出隊操縱，它們都涉及到了結構體和動態記憶體治理函式的使用。相信程式碼示例當中的註釋已經足夠清楚的解釋了程式碼的實現邏輯和對應的功能，我這裡就不再贅述了。透過結合使用結構體和動態記憶體治理函式，我們可以實現一種靈活而高效實現佇列操縱，但是，使用結構體和動態記憶體治理函式來實現佇列也有一些缺點。好比，每次入隊或出隊操縱都需要申請或開釋記憶體空間，這會增加程式執行時的開銷和複雜度。而且，假如頻繁地進行入隊或出隊操縱，可能會導致記憶體碎片的產生。那麼，有沒有一種更簡樸而高效地方法來實現一個固定大小的輪迴佇列呢？謎底是有的。我們可以使用一種叫做輪迴陣列的資料結構來實現一個固定大小的輪迴佇列。我們再來看一些示例程式碼：

這個示例程式碼展示瞭如何使用輪迴陣列來實現一個固定大小的輪迴佇列。輪迴陣列是一種特殊的陣列，它可以讓我們在使用陣列時不需要考慮陣列邊界的問題。我們可以用一個變數來記實陣列中有效元素的個數，或者用兩個變數來記實陣列中有效元素的起始和結束位置。這樣，我們就可以在陣列中實現類似於輪迴連結串列的效果，即當我們到達陣列末尾時，可以回到陣列開頭繼承操縱。透過使用輪迴陣列，我們可以實現一種簡樸而高效地資料結構——固定大小的輪迴佇列。

但是，使用輪迴陣列來實現固定大小的輪迴佇列也有一些缺點。好比，我們需要事先確定輪迴陣列的大小，並且不能超過這個大小。這樣，我們就不能靈活地根據程式執行時的需要動態地增加或減少佇列中的元素。而且，假如我們選擇了一個過大或過小的輪迴陣列大小，可能會導致記憶體空間的鋪張或不足。那麼，有沒有一種更靈活而高效地方法來實現一個不固定大小的輪迴佇列呢？謎底是有的。我們可以使用一種叫做連結串列的資料結構來實現一個不固定大小的輪迴佇列。這個實現就作為一個有趣而有挑戰性的任務留給同學們吧：使用連結串列來實現一個不固定大小的輪迴佇列。這裡給出一個簡樸的提示：

1. 定義一個表示連結串列節點的結構體型別，包含資料域和指標域。

2. 定義一個表示輪迴佇列的結構體型別，包含指向隊頭節點和隊尾節點的指標。

3. 定義一個建立連結串列節點的函式，返回一個指向新建立節點的指標。

4. 定義一個建立空輪迴佇列的函式，返回一個指向新建立輪迴佇列的指標。

5. 定義一個判定輪迴佇列是否為空的函式，返回一個布林值。

6. 定義一個在輪迴佇列尾部增加一個新節點的函式，返回新輪迴佇列頭部的指標。

7. 定義一個從輪迴佇列頭部刪除一個節點的函式，返回新輪迴佇列頭部的指標。

8. 定義一個列印輪迴佇列內容的函式，遍歷整個輪迴佇列，並列印每個節點攜帶的資訊。

9. 在main函式中測試你編寫的函式，並觀察輸出結果。

請在課後完成你的程式碼編寫，可以在評論區說說你使用了哪些思路和技巧。假如你碰到了任何難題或錯誤，請在評論區尋求匡助吧！祝大家學習舒暢！

好了，關於佇列的實現——入隊、出隊、遍歷，我們就先學習這麼多吧。更多關於這些操縱及其相關主題（好比優先佇列、雙端佇列、廣度優先搜尋等）的內容，請在以後的課程中繼承探索吧！

之前的課程請點選這裡：