佇列 - Queue

佇列與堆疊相反,是一種先進先出的線性排列資料結構,集合中的物件元素,依加入集合的順序,先進先出,如同排隊購票行為,愈早進入隊伍的人,愈早買到票離開隊伍,類別Queue實作了佇列資料結構。



元素 E 最後被放入佇列,當集合中的元素被取出時,第一個放入的元素 A 首先被取出,最後才是元素 E ,物件放入集合的順序與取出的順序完全相同。

佇列被應用的地方很多,例如訊息佇列的資料處理,你也可以利用佇列依序安排系統中數個正在進行的作業行程,類似的工作都可以藉由 Queue 類別建立的物件來處理。

佇列同 Stack 類別,是一個動態的集合陣列物件,實作 ICollection 、 IEnumerable 以及 ICloneable 等三個介面, Queue 物件的大小依加入的物件數目而動態擴充。

Queue 集合容量每一次遞增的量是根據等比級數因數所決定的,Queue物件預設容量的大小是32,而等比級數因數是 2.0,當加入的元素數量超過預設容量,則集合物件增加的容量為等比級數因數乘上目前的容量。

Queue 類別提供了幾個建構式,最簡單者沒有接受任何參數,利用這個版本的建構式建立的Queue 類別物件,其預設容量值為 32 而等比級數因數是 2.0 ,若是想指定這兩個值,則必須使用以下這個版本的建構式:
Public Queue(int capacity, float grow)
第一個參數 intCapacity 表示所要建立的集合物件容量,而 grow 則是每一次容量擴充的等比級數因數,如果沒有指定則使用預設的因數。

Queue類別定義的方法中,我們比較感興趣的是 Enqueue 以及 Dequeue ,還有在 Stack類別見到的 Peek ,以下列舉說明。

Enqueue

將一個物件加入到指定的Queue 集合物件,其形式如下:
void Enqueue(object obj)
其中的 obj 為加入到集合中的物件。

Dequeue

自集合中將元素取出,並且將其自集合中移除,其形式如下:
object Dequeue();
這個方法回傳一個 object 型別物件。

Peek

與 Stack 類別相同,它只是將得到的物件取回,並不會改變集合的內容。
接下來的程式碼,使用 Queue 類別重作上述示範堆疊的範例,藉以比較堆疊與佇列這兩種資料結構的差異。
class Program
{
    static void Main(string[] args)
    {
        int firstNumber = 10;
        int secondNumber = 20;
        int thirdNumber = 30;
        int forthNumber = 40;
        int fifthNumber = 50;

        Queue myQueue = new Queue();

        Console.WriteLine("使用方法Enqueue 將物件加入堆疊: \n");
        Console.WriteLine("加入第一個數值10: ");
        myQueue.Enqueue(firstNumber);
        Console.WriteLine("加入第二個數值20: ");
        myQueue.Enqueue(secondNumber);
        Console.WriteLine("加入第三個數值30: ");
        myQueue.Enqueue(thirdNumber);
        Console.WriteLine("加入第三個數值40: ");
        myQueue.Enqueue(forthNumber);
        Console.WriteLine("加入第三個數值50: ");
        myQueue.Enqueue(fifthNumber);
        Console.WriteLine("使用方法Peek 從堆疊取得物件: \n");

        for (int i = 0; i < 5; i++)
        {
            Console.WriteLine(myQueue.Peek());
        }
        Console.WriteLine("堆疊內目前的物件物件: {0}\n", myQueue.Count);

        Console.WriteLine("使用方法Dequeue 從堆疊取得物件,並且將其移走: \n");
        for (int i = 0; i < 5; i++)
        {
            Console.WriteLine(myQueue.Dequeue());
        }
        Console.WriteLine("堆疊內目前的物件物件: {0}\n", myQueue.Count);
        Console.ReadLine();
    }
}
首先建立一個 Queue 類別物件 queue ,並且引用其方法 Enqueue ,逐一將不同的整數加入集合物件,然後再依序取出。 第一組 for 迴圈引用方法 Peek 取出最先加入佇列的物件,第二組 for 迴圈引用方法 Dequeue 將物件從集合中移走。
使用方法 Enqueue 將物件加入堆疊 :

加入第一個數值 10:
加入第二個數值 20:
加入第三個數值 30:
加入第三個數值 40:
加入第三個數值 50:
使用方法 Peek 從堆疊取得物件 :

10
10
10
10
10
堆疊內目前的物件物件 : 5

使用方法 Dequeue 從堆疊取得物件,並且將其移走 :

10
20
30
40
50
堆疊內目前的物件物件 : 0
由於這是一個佇列類型的資料結構集合,因此連續引用 5 次 Dequeue 方法時,集合中的元素依放入的順序取出,從執行結果可以很清楚的看到,相較堆疊的差異。



沒有留言: